probability of reaching the end of an endless game

hamsterofdeath2

New member
Joined
Apr 30, 2018
Messages
9
i am trying to solve a math riddle (specifically this one https://projecteuler.net/problem=640 )
usually, i would just let my computer go through all possible paths and count how many options there are and how likely each one is. for other problems, this is fine.

here, however, it is possible the game never ends. it's not likely, but it can happen.
i don't want anyone to solve the problem for me, i just need a hint in the right direction (maybe)

i can simplify the problematic part into something like this:
you have a coin. you toss it. heads gives a point, tails subtracts one.
let's say the game ends at 10 (win) or -10 (loss) points. how would i calculate things like "what is the probability that the game never ends"?
if i were to ask "how likely is it that it ends with 100 moves or less", i could use brute force and count. for infinities, this takes too long.

has this been solved in general?
 
I have neither the time, nor in strictest honesty, the interest to think through this problem, BUT the issue of an infinite game is spurious. You are not asked to get an exact expected value. The sum of all the probabilities less than what is required to get your approximated value can be ignored.
 
Top