I've seen a number of problems involving games with infinite moves and I'd like to learn how to solve them.

Here is an example: We have a marble placed on square 10 of an infinite strip of numbered squares. We have a 6-sided die which displays one of the numbers {-3, -2, -1, 1, 2, 3} with uniform probability when thrown. In each move we throw the die, and move the marble up or down by the amount shown. We keep doing this forever. If the marble ever reaches a negative square we lose. What is the probability of losing this game?

I don't know how to approach this, as the marble can go both ways so it doesn't seem like a simple recurrence relation would solve it.

I played around with limits, Markov chains, and tried to come up with some sort of recurrence relation, but I got nowhere. Any ideas?

  • $\begingroup$ There is no chance of winning the game. You haven't described a scenario in which the game could possibly be won. $\endgroup$
    – WW1
    Dec 19, 2015 at 2:09
  • $\begingroup$ Check out probabilitycourse.com/chapter14/Chapter_14.pdf - your game is basically the Gambler's Ruin against a bank with infinite funds. $\endgroup$
    – WW1
    Dec 19, 2015 at 2:15
  • $\begingroup$ No, it is different. $\endgroup$
    – Asinomás
    Dec 19, 2015 at 2:16
  • 2
    $\begingroup$ @dre When you add up a bunch of i.i.d variables with finite variance, their sum starts behaving like a standard diffusion/brownian motion/local discrete CLT so finer details no longer matter . All that matters for long-term behaviour is mean and variance. Transience depends on mean only. For zero mean every boundary will be crossed with probability $1$ but expected time to the first visit is infinite. $\endgroup$
    – A.S.
    Dec 19, 2015 at 6:05
  • 2
    $\begingroup$ If the drift is negative, you obviously lose with probability one. If the drift is positive, there is a positive probability of winning and it depends on details of your single step. For asymmetric random walk with steps $\pm 1$ with probabilities $p$ and $q$, you lose with probability $(\frac q p)^n$ starting at $n$ (assuming you lose when you reach $0$). $\endgroup$
    – A.S.
    Dec 19, 2015 at 9:18


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.