1
$\begingroup$

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!

  • 0
    Your second option is the one I meant2012-11-11

2 Answers 2

1

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 and $P(H>n/2)=P(H.
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.

  • 0
    Ah of course! What a stupid mistake. Thank you!2012-11-12
1

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.