6

I start life at $0$, I aim to make it to $1$. I can take steps of $\dfrac{1}{2^k}, k>0$, and do so with probability $\dfrac{1}{2^k}$.

What is the expected number of steps to reach $1$ or beyond. What is the probability I will land on $1$?

APPENDUM:

$\begin{array} {c|c} values&expected\\ \hline 222&2\\ 22N&2\\ 2N2&3\\ N22&3\\ NN2&?\\ N2N&?\\ 2NN&?\\ NNN&? \end{array}$

Let $2$ be the event that we walk $\dfrac12$, and $N$ that we don't. We have $8$ outcomes, but we don't know the value of $?$, so let it be $5$ for those with one $2$, on the grounds that we will need on average $2$ more throws to 'guarantee' a $2$, and $7$ for $NNN$. So the expected value is $\dfrac{32}{8}=4$. This obviously needs some refinement.

JMP
  • 21,771
  • The average length of a step if $\sum_{k\geq 1}\frac{1}{4^k}=\frac{1}{3}$, hence, how many steps do you think we need to go past $1$? – Jack D'Aurizio Sep 18 '15 at 12:17
  • 1
    @coffeemath: I believe the intending meaning is: at any time, you take a step with length $\frac{1}{2}$ toward the right with probability $\frac{1}{2}$, a step with length $\frac{1}{4}$ toward the right with probability $\frac{1}{4}$ and so on. So the OP is asking for the stopping time of a (Poisson process)[https://en.wikipedia.org/wiki/Poisson_process]. – Jack D'Aurizio Sep 18 '15 at 12:22
  • @JackD'Aurizio: Please see my comment under karmanaut's answer. – joriki Sep 18 '15 at 16:37
  • 2
    Here's code to simulate this -- the result from ten billion trials is $3.37892\pm0.00001$ for the expected number of steps and $0.379407\pm0.000005$ for the probability. – joriki Sep 18 '15 at 17:20

1 Answers1

1

Let $X_i$ be the the distance travelled in the $i^{th}$ step. Then, $E(X_i)$ = ${1 \over {2^2}} + {1 \over {4^2}} + {1 \over {8^2}} + .. = {1 \over 3} $. The expected distance travelled in $n$ steps is $E(X) = \sum_{i=1}^{n} E(X_i) = {n \over 3}$. Can you take this hint and try to come up with the answer?

As for the probability of ever reaching exactly $1$, let us do it the traditional counting way. Let $P_i$ be the probability of reaching 1 in exactly $i$ steps. Then $P_1=0, P_2={1 \over 4}, P_3 = {3}{1 \over 2}{1 \over 4}{1 \over 4}, P_4 = {4.3}{1 \over 2}{1 \over 4}{1 \over 8}{1 \over 8} + {1 \over 4}{1 \over 4}{1 \over 4}{1 \over 4}$. So a good lower bound would be 0.25 but I can't think of a way to generate $P_i$ in the usual way. Maybe a recursive formulation can help.

karmanaut
  • 731
  • Still leaves the other question, about probability of ever landing on exactly 1. – coffeemath Sep 18 '15 at 15:31
  • The expected number of steps is not in general the reciprocal of the expected step length. Consider step $0$ with probability $0.999$ and step $1000$ with probability $.001$. The expected step length is $1$, but the expected number of steps is clearly greater than $1$. – joriki Sep 18 '15 at 16:36
  • @joriki Your example is a geometric distribution with p = 0.001. So expected number of steps should be ${1 \over p} = 1000$. But can we generalize this to the question OP discussed where state changes are mandatory? Because if yes, we can very easily model the problem as a recursive markov chain. – karmanaut Sep 18 '15 at 16:50
  • I don't understand what you mean by that last sentence. Are you disputing that my example invalidates your hint? – joriki Sep 18 '15 at 16:51
  • I am not contesting my hint. It is clearly wrong. Extending your example, if step 1 is with probability 0.999 and step 1000 with probability 0.001, then the expected step length is 1.999 ~ 2 but the expected number of steps is clearly 1. I wanted to ask in which situation we can say that expected number of steps is equal to reciprocal of the expected step length. – karmanaut Sep 18 '15 at 16:58
  • I don't actually know any way to characterize that situation. – joriki Sep 18 '15 at 17:31
  • In your $P_4$, the factor should be $4\cdot3$ instead of $4$, for $4$ choices to place $\frac12$ and then $3$ to place $\frac14$. – joriki Sep 18 '15 at 17:32
  • i think the problem with your hint is that the problem doesn't allow a 1/3rd of a step - it's like asking you to throw a 3.5 with a normal dice – JMP Sep 23 '15 at 23:07
  • @karmanaut; i think its compositions of 2^(k-1) into powers of two and k parts – JMP Sep 23 '15 at 23:34