# Question on conditional expectation - "random walk on the integers"

This is the question:

An immortal drunk man wanders around randomly on the integers. He starts at the origin, and at each step he moves $$1$$ unit to the right or 1 unit to the left, with equal probabilities, independently of all his previous steps. Let $$b$$ be a googolplex (this is $$10^g$$, where $$g = 10^{100}$$ is a googol). Find the expected number of times that the immortal drunk visits $$b$$ before returning to the origin for the first time.

Here is the solution in the textbook:

Let $$N$$ be the number of visits to $$b$$ before returning to the origin for the first time, and let $$p = 1/(2b)$$ be the probability that the drunk visits $$b$$ before returning to the origin for the first time (Note, this is just a gambler's ruin problem). Then,

$$E(N)=E(N \mid N=0)P(N=0)+E(N \mid N \geq 1)P(N \geq 1)=pE(N \mid N \geq 1)$$

This formula seems to make sense because given that there are zero visits, the left term will be $$0$$. And for the right side, the probability of at least $$1$$ visits is just $$1-P(N=0)=p$$.

However, at this point, I am not sure what to do. In the solutions, they show that $$E(N \mid N \geq 1)=\frac{1}{p}$$ but I don't quite understand how they get this. As a result the final answer is $$E(N)=1$$.

Furthermore, how can the expected number of visits to $$b$$ which is a very large number be $$1$$? Intuitively, I expected the value to be close to $$0$$ because the probability of getting to the end is so small, ie. $$p=1/(2b)$$.

• But if you do visit $b$ at least once, the same intuitive argument might suggest you could visit it many times before returning to $0$ Jun 1, 2016 at 23:22
• Oh wow that's a genius way to think of it.
– jlcv
Jun 1, 2016 at 23:28
• Huh, so it looks like in the situation where we are given at least one visits to $b$, then we want to solve for the number of revisits to $b$ before going back to the origin. This would just be a geometric distribution. Hence, $E(N)=1+q/p=1/p$. Essentially what I wrote is given the first visit + all subsequent visits $q/p$. Is this correct?
– jlcv
Jun 1, 2016 at 23:32
• An immortal drunk man wanders around randomly on the integers. Guess Socrates was wrong, then... Jun 1, 2016 at 23:34
• How does one show $p=1/(2b)$? I realize this is not needed for your question, but I am curious. Jun 2, 2016 at 16:25

## 1 Answer

Assuming that $q=1-p$ in your comment, it sounds like you solved the problem yourself.

If you do reach $b$, the probability to reach the origin before you reach $b$ again is $p$. Thus, the number of expected visits to $b$ in this case is

$$1+(1-p)+(1-p)^2+\cdots=\frac1p\;.$$