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
-
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$
-
0I wasn't able to find the probability to hit a power of two for the first time. Any Suggestion? – 2012-03-05