Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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
add comment

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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