Random walk and powers of 2

Question

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

Answer 1

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