Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?

share|improve this question
1  
Supposing 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. –  Marc van Leeuwen Mar 5 '12 at 13:36
    
@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 –  Riccardo.Alestra Mar 5 '12 at 13:47
    
I 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)$ –  Henry Mar 5 '12 at 14:17

1 Answer 1

up vote 1 down vote accepted

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$$

share|improve this answer
1  
What 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. –  Did Mar 5 '12 at 15:19
1  
Also 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. –  Marc van Leeuwen Mar 5 '12 at 18:04
    
I wasn't able to find the probability to hit a power of two for the first time. Any Suggestion? –  Riccardo.Alestra Mar 5 '12 at 19:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.