I'm in trouble on the following problem: given a random walk starting at point N on the integer number line, how many steps should I wait before the walk hits a power of two at least once, with probability $P$ with $P\gt 0$?
Random walk and powers of 2
-
1Supposing you're taking unit steps, take the length of the walk equal to the distance from $N$ to the nearest power of two. It will then be possible to reach that power of two, and it will happen with a positive probability. Maybe this is not what you wanted to ask, but your question isn't clearly formulated. – 2012-03-05
-
0@Marc van Leeuwen: I take unit step. $N$ is a positive integer number $N\ge{0}$ What is the formula of the probability $P(N)$ to hit a power of two at least once, assuming I am interested only in the first power of two before N and the next after N – 2012-03-05
-
0I am not sure whether this has much to do with powers of 2. Note that with $A \lt N \lt B$, the expected time to hit either of boundary is $(B-N)(N-A)$ – 2012-03-05
1 Answers
Given an integer number N, the first power of two before N is given by: $$2^{Int\left(ln(N)/ln(2)\right)}$$ and the first power of two following N is: $$2^{Int\left(ln(N)/ln(2)+1\right)}$$ where $Int$ is the 'integer part of' operator. So we have $$l=N-2^{Int\left(ln(N)/ln(2)\right)}$$ steps on the left and $$r=2^{Int\left(ln(N)/ln(2)+1\right)}-N$$ on the right. Then, the probability to hit the power of two on the left after $n$ steps is: $$\left( \begin{array}{c} n \\ l \end{array}\right)\left(\frac{1}{2}\right)^n$$ and the probability to hit the power of two immediately after N is: $$\left( \begin{array}{c} n \\ r \end{array}\right)\left(\frac{1}{2}\right)^n$$ so $P$ is given by: $$P=\left( \begin{array}{c} n \\ N-2^{Int\left(ln(N)/ln(2)\right)} \end{array}\right)\left(\frac{1}{2}\right)^n+\left( \begin{array}{c} n \\ 2^{Int\left(ln(N)/ln(2)+1\right)}-N \end{array}\right)\left(\frac{1}{2}\right)^n$$
-
1What you call *the probability to hit the power of two on the left after $n$ steps* is the probability to be there after $n$ steps, but not necessarily for the first time. – 2012-03-05
-
1Also the answer glosses over a parity issue: one cannot move $l$ places left in $n$ steps unless $n$ and $l$ have the same parity. In fact to do so requires making $\frac{n+l}2$ left steps and $\frac{n-l}2$ right steps. So you binomial coefficients should be $\binom n{\frac{n+l}2}$ and $\binom n{\frac{n+r}2}$. And the question is about the expected time for the first hit, not the probability of a hit after some number of steps. – 2012-03-05
-
0I wasn't able to find the probability to hit a power of two for the first time. Any Suggestion? – 2012-03-05