3
$\begingroup$

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

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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