# Probability of landing in $\mathbb{N}\cup \{0\}$

Here's a question I'm struggling with:

A man is standing on $0 \in \mathbb{R}$. He tosses $n$ coins. For H he takes a right step and for T he takes a left step. What is the probability that at the end of the process he's standing on a non-negative integer?

Here's my attempt.

Let $P(n\text{ is odd}) = p$ and $P(n\text{ is even}) = 1-p$

If $n$ is odd we know that he can't go back to zero. The number of paths that ends at $\mathbb{R}^+$ is equal to those that ends at $\mathbb{R}^-$ so the probability in this case is $\dfrac{2^n}{2}$.

If $n$ is even we need to cound the number of string where $H \ge T$ and so the probability is $$\frac{\sum_{k=n/2}^{n}\binom{n}{k}}{2^n}$$

and so in general we get $$(1-p)\cdot \frac{2^n}{2} + p\cdot \frac{\sum_{k=n/2}^{n}\binom{n}{k}}{2^n}$$

Am I right? Thanks!

-
Do you mean $\mathbb{Z}$? That would make more sense. –  Daniel Littlewood Nov 11 '12 at 20:59
I corrected it to a non negative integer –  Yotam Nov 11 '12 at 20:59
Is $n$ a (random) variable, or is it a parameter of the problem? When I read this, I'm inclined to interpret the problem as asking for the probability of landing on a non-negative integer as a function of $n$, rather than assume that $n$ is going to be determined randomly and factor this into the probability. –  rayradjr Nov 11 '12 at 21:20
Your second option is the one I meant –  Yotam Nov 11 '12 at 21:25

Let $H$ be the random variable "number of heads after $n$ coin tosses. Let also $p$ equal the probability of landing on a non-negative integer. Obviously $X\sim B(n,\frac{1}{2})$. You are right to note that if $n$ is odd, we cannot go back to $0$. Thus, by symmetry, we can conclude that in this case the probability of being on the right of $0$ is $p=1/2$.
On the other hand, if $n$ is even, our symmetry corresponds to $P(H>n/2)+P(H<n/2)+P(H=n/2)=1$ and $P(H>n/2)=P(H<n/2)$.
Since $P(H=n/2)=$$n\choose n/2$$(1/2)^{n}$, we conclude that for even $n$, $$p=\left(1-\binom{n}{n/2}2^{-n}\right)/2+\binom{n}{n/2}2^{-n}=1/2+\binom{n}{n/2}2^{-n}/2$$ I'm struggling to work out whether or not our answers are the same - I'm not sure what you mean by $P(n$ is even$)$ etc.

-
Well, we don't know wethere n is even or not, but now that I think about it I think its a parameter –  Yotam Nov 11 '12 at 21:43
It should be $\binom{n}{n/2}2^{-n}/2$, not $\binom{n}{n/2}2^{-n/2}/2$. In the current form, the probability exceeds $1$ for even $n\ge 4$. –  rayradjr Nov 12 '12 at 20:04
Ah of course! What a stupid mistake. Thank you! –  Daniel Littlewood Nov 12 '12 at 20:27

At this point, I should probably be talking in an answer, instead of a comment.

We can't do the version where $n$ is to be determined randomly as part of the process because we don't have any well-defined probability distribution for $n$. If we did, we could sum over the possible values of $n$, taking for each term the probability of getting that $n$ times the probability of landing at $0$ or higher if we get that $n$, and that would get us the total probability of landing at $0$ or higher. However, we don't have a distribution like that, nor is there any "natural" choice for such a distribution, so the problem only makes sense if $n$ is a parameter, and that's how I'm going to approach it.

If $n$ is odd, then the probability is $\frac{1}{2}$, not $\frac{2^n}{2}$; the latter isn't even between $0$ and $1$ for $n>1$. For even $n=2m$, we can simplify your sum by realizing that

$$\binom{2m}{0}+\binom{2m}{1}+\dots+\binom{2m}{m-1}+\binom{2m}{m+1}+\dots+\binom{2m}{2m}=2^{2m}-\binom{2m}{m}$$

counts all of the possibilities for not landing on $0$, and that we need to include exactly the ones from $\binom{2m}{m+1}$ on, which make up exactly half of the total sum. The rest of the possibilities we need to include are the ones in which the man lands on $0$, and there are $\binom{2m}{m}$ of these, so our final probability should be

$$\frac{1}{2^{2m}}\cdot(2^{2m-1}+\frac{1}{2}\binom{2m}{m})=\frac{1}{2^n}\cdot(2^{n-1}+\frac{1}{2}\binom{n}{n/2})=\frac{1}{2}+\frac{1}{2^{n+1}}\binom{n}{n/2},$$

which is again equal to the formula you gave above.

-