2

You are above a pit of fire and the only way out is a $1000-$ rung escape ladder. You're on the first rung.

Every second a standard die rolls. If it's $1$ or $2$ you move down one rung. Otherwise you will move up by one rung. If you move down from the first rung you will fall into the fire! If you move up from the $1000th$ rung, you escape.

What is the probability that you escape?

Anurag Jain
  • 397
  • 4
  • 14
  • 2
    $0$, because you have no way to move up. – f'' Jun 19 '16 at 05:18
  • No, you can get out of that pit. What if u get $4$ on every roll of die ? – Anurag Jain Jun 19 '16 at 05:20
  • 1
    Then nothing happens, according to the problem. – Deusovi Jun 19 '16 at 05:21
  • Apologies. I have added that part. – Anurag Jain Jun 19 '16 at 05:23
  • Probability of escaping from the $k$th rung: $p(k)=\frac{1}{6}\left(2p(k-1)+4p(k+1)\right)$; solution is $p(k)=\beta_1+\beta_2 2^{-k}$; boundary conditions are $p(0)=0$ and $p(n+1)=1$; solving gives $\beta_2=2^{n+1}/(2^{n+1}-1)$, $\beta_1=-\beta_2$; therefore the answer is $p(1)=\left(2-2^{-n}\right)^{-1}\approx 1/2$. – 2012rcampion Jun 19 '16 at 05:45

1 Answers1

5

For the $n$th rung, assign a value of $2^{1001-n}$, with escape having a value of $1$ and death having a value of $2^{1001}$. Every second, you have $\frac23$ probability of halving your value and $\frac13$ probability of doubling it. $\frac23(\frac12)+\frac13(2)=1$, so your expected value stays the same.

You start with $2^{1000}$ value and escape with probability $p$. The expected value remains constant, so $2^{1000}=1(p)+2^{1001}(1-p)$. Solving for $p$ shows that it is $\frac{2^{1000}}{2^{1001}-1}$.

This is known as de Moivre's martingale.

f''
  • 33,665
  • 4
  • 120
  • 165
  • ^vote with a note: Any chance of spoiling us with a hint of how de Moivre or you figured this out? (Would be interesting, though this puzzle might be mathematically eliminated anyway.) – humn Jun 19 '16 at 07:05
  • 1
    @humn In a regular martingale, your average location stays the same (as in Ant walking on a number line). When the probabilities for up and down are not equal, this doesn't work. However, with the right choice of values, you can make the expected value constant. – f'' Jun 19 '16 at 14:41