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

718 Views Asked by At

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

1

There are 1 best solutions below

0
On

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