# 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$ – Henry Jun 1 '16 at 23:22
• Oh wow that's a genius way to think of it. – Zoom Bee Jun 1 '16 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? – Zoom Bee Jun 1 '16 at 23:32
• An immortal drunk man wanders around randomly on the integers. Guess Socrates was wrong, then... – Math1000 Jun 1 '16 at 23:34
• How does one show $p=1/(2b)$? I realize this is not needed for your question, but I am curious. – angryavian Jun 2 '16 at 16:25

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\;.$$