probability

[Random Variable]

You flip a coin n times. The probabilty of getting a head on any flip is p. What is the probability that after every flip the total number of heads flipped up to that point is greater than the total number of tails flipped up to that point?

if n=1, the only possibility is H
if n=2, the only possibility is HH
if n=3, the two possibilities are HHH or HHT
if n=4, the three possibilites are HHHH, HHHT, or HHTH
if n=5, the six possibilites are HHHHH, HHHHT, HHHTT, HHHTH, HHTHH, and HHTHT

Of course you could keep doing this until you notice a pattern, take a guess at the formula, and then try to prove that forumula by induction. (I tried that approach, but didn't get anywhere). But there must be something you can condition on to simply the problem. I'm stumped.

 

[nccr]

This is just the sum from i = m to n (where m = n/2 + 1 if n is even and (n+1)/2 if n is odd) of nCm * p^m * (1-p)^(n-m)

 

[TuxDave]

Break the problem down into (if n = even and if n = odd)

My first glance would go along the lines of:
If n = odd, 50%
If n = even, 0.5 * (1-probability that you get the same number of heads ands tails)

But those two above are just my intuitive guesses without any proof.

The odd case is a symmetry argument and the even case, you can create a formula to put in P(T=H) as a function of n. If you want to be super nerdish you can do....


Probability = 0.5 * [1 - P(T=H,n)*(n+1 MOD 2)] so you don't have to write the (if n is even or odd crap)

 

[nccr]

Originally posted by: TuxDave
Break the problem down into (if n = even and if n = odd)

My first glance would go along the lines of:
If n = odd, 50%
If n = even, 0.5 * (1-probability that you get the same number of heads ands tails)

But those two above are just my intuitive guesses without any proof.

The odd case is a symmetry argument and the even case, you can create a formula to put in P(T=H) as a function of n. If you want to be super nerdish you can do....


Probability = 0.5 * [1 - P(T=H,n)*(n+1 MOD 2)] so you don't have to write the (if n is even or odd crap)

The only problem here is that you assumed that p = 1/2.

Anyways, if n is even, the probability that the number of heads = the number of tails is given by nC(n/2) * 1/2^n.

 

[Random Variable]

but if n=3 (and you're using a fair coin) the probability is 1/4

 

[TuxDave]

Originally posted by: Random Variable
but if n=3 (and you're using a fair coin) the probability is 1/4

Is it (assuming fair coin)?

HHH
HHT,HTH,THH
HTT,THT,TTH
TTT

4/8 for more heads than tails. = 50%

 

[TuxDave]

Originally posted by: nccr

Originally posted by: TuxDave
Break the problem down into (if n = even and if n = odd)

My first glance would go along the lines of:
If n = odd, 50%
If n = even, 0.5 * (1-probability that you get the same number of heads ands tails)

But those two above are just my intuitive guesses without any proof.

The odd case is a symmetry argument and the even case, you can create a formula to put in P(T=H) as a function of n. If you want to be super nerdish you can do....


Probability = 0.5 * [1 - P(T=H,n)*(n+1 MOD 2)] so you don't have to write the (if n is even or odd crap)

The only problem here is that you assumed that p = 1/2.

Anyways, if n is even, the probability that the number of heads = the number of tails is given by nC(n/2) * 1/2^n.

Ah pfffft... wow that messes things up. Without any proof, I would guess
Probability = p * [1 - P(T=H,n)*(n+1 MOD 2)]

haha

 

[Random Variable]

Originally posted by: TuxDave

Originally posted by: Random Variable
but if n=3 (and you're using a fair coin) the probability is 1/4

Is it (assuming fair coin)?

HHH
HHT,HTH,THH
HTT,THT,TTH
TTT

4/8 for more heads than tails. = 50%

After every flip the total number of heads flipped up to that point must be greater than the total number of tails flipped. Let's why for n=3 above I have only two possibilites listed--HHH and HHT.

 

[TuxDave]

Originally posted by: Random Variable

Originally posted by: TuxDave

Originally posted by: Random Variable
but if n=3 (and you're using a fair coin) the probability is 1/4

Is it (assuming fair coin)?

HHH
HHT,HTH,THH
HTT,THT,TTH
TTT

4/8 for more heads than tails. = 50%

After every flip the total number of heads flipped up to that point must be greater than the total number of tails flipped. Let's why for n=3 above I have only two possibilites listed--HHH and HHT.

Oooo... well that changes the problem. One sec to think about it.

 

[nccr]

Ah, I misunderstood the problem as first. I'll think about this. In the mean time, I ran some simulations (10000 trials of n flips)

n=3, p=.2512 vs .25 actual
n=4, p=.1867 vs 0.1875 actual
n=5, p=.1881
n=6, p=.1604
n=7, p=.1561
...
n=10, p=.1249
...
n=20, p=.0915
...
n=100, p=.0403

 

[Random Variable]

The solution is probably based on the ballot problem, which states the following: Two candidates, A and B, are running for office. If candidate A received n votes and candidate B received m votes (n>m), the probabilty that candidate A is always ahead in the counting of the votes is n-m/(n+m).

 

[Random Variable]

Originally posted by: nccr
Ah, I misunderstood the problem as first. I'll think about this. In the mean time, I ran some simulations (10000 trials of n flips)

n=3, p=.2512 vs .25 actual
n=4, p=.1867 vs 0.1875 actual
n=5, p=.1881
n=6, p=.1604
n=7, p=.1561
...
n=10, p=.1249
...
n=20, p=.0915
...
n=100, p=.0403

If you used Maple, I'd love to see your program.

 

[nccr]

Nah, I used R. I didn't save the code, but it only took a few minutes to write. I just sampled with replacement multiple times from {-1,1}, took the cumulative sum, and counted a failure whenever it dropped below 1.

 

[TuxDave]

Originally posted by: nccr
Ah, I misunderstood the problem as first. I'll think about this. In the mean time, I ran some simulations (10000 trials of n flips)

n=3, p=.2512 vs 2/8
n=4, p=.1867 vs 3/16
n=5, p=.1881 vs 6/32
n=6, p=.1604 vs 10/64
n=7, p=.1561 vs 20/128
...
n=10, p=.1249 vs 126/1024
...
n=20, p=.0915
...
n=100, p=.0403

Filled in the rest for you up to n=10. I can easily calculate the probability using a program to simulate a tree but I have no idea how to collapse it into a single equation yet. (oh... assuming p=0.5 for now too)

 

[iCyborg]

You can collapse it in this way:
P(2n+1) = P(2n) = (1/2)*X/Y where X is the product of all the odd numbers up to 2n-1, and Y is the product of all the even numbers up to 2n.

You can get this by noticing two recursive relations:
1. P(n) = P(n-1) for n odd
2. P(n) = P(n-1)*(n-1)/n for n even

The first one is trivial to prove (notice that for even n, the difference in the number of heads and tails must be at least 2), but I didn't find any simple proof for the second one. It can be proved in the following nonelegant way:

For n=2k:
P(2k) = P(2k-1) - 0.5*(1/(2k-1))*(2k-1 choose k-1)*0.5^(2k-1).

You can get this formula by observing that the only situations in which you can't put anything in the last place is when the difference for the first 2k-1 flips was exactly 1. Half of those are OK - those when you get H in the last flip. Use the ballot problem for k,k-1 to obtain this expression.
You can prove this by induction that it has the form of that product of even/odd numbers. Let me know if you have trouble, because it's quite messy to prove this...

All of this assumes p=0.5. Relation 1) holds for any p, if there's some direct way of proving 2), it shouldn't be hard to generalize. Otherwise, you need to revise the above formula (the one with k's in it) and instead of 0.5^(2k-1) put (p^k) * (1-p)^(k-1). And then you'll have to guess the formula which to prove by induction...

 

[Random Variable]

This solution relies on the solution to the following problem:

Two candidates, A and B, are running for office. If candidate A received n votes and candidate B received m votes (n>m), the probabilty that candidate A is always ahead in the counting of the votes is n-m/(n+m).

now let H = the number of heads flipped
and let T = the number of tails flipped

and lets look at the case for n=5,

P(heads is always in the lead for n=5) = P(heads is always in the lead for n=5|H=5,T=0)*P(H=5,T=0) + P(heads is always in the lead for n=5|H=4,T=1)*P(H=4,T=4) + P(heads is always in the lead for n=5|H=3,T=2)*P(H=3,T=2)

for any other case, the probability heads is always in the lead is zero

= p^5 + (4-1)/(4+1)*5C4*p^4q + (3-2)/(3+2)*5C3*p^3*q^2
= p^5 + 3*p^4*q + 2*p^3*q^2 which is what you get if you do it by writing out the possibilities

so in general, it's the sum over H and T such that H>T and H+T=n of P(the number of heads is always in the lead|H=h, T=t)*P(H=h, T=t)

 

[iCyborg]

Hm, I thought that the problem was getting some nice form of that sum, as it's rather ugly. Like for p=1/2 the formula looks fairly simple. That's what I was doing up there...

And what's the problem if it relies on another problem? They are very similar, and that "other" problem is easy to prove by induction on n+m. It's not like it relies on Riemann's hypothesis.

 

[Random Variable]

Originally posted by: iCyborg
Hm, I thought that the problem was getting some nice form of that sum, as it's rather ugly. Like for p=1/2 the formula looks fairly simple. That's what I was doing up there...

And what's the problem if it relies on another problem? They are very similar, and that "other" problem is easy to prove by induction on n+m. It's not like it relies on Riemann's hypothesis.

There might very well be a better way to express the solution. That's just what I came up with.

 

[toslat]

nm misunderstood the problem

 

[suszterpatt]

Since the OP's question has been answered, allow me to ask a new question here so as to avoid two threads on the same topic.


Suppose that I roll n dice for a total sum of X, then I roll m dice for a total sum of Y. What's P(X>Y)?

At first I thought it's n/(n+m), but that doesn't add up. For example, if n=m, then n/(n+m) = 0.5 "=" P(X>Y) = P(Y>X), but since P(X=Y) is also an option, the sum of the three probabilities is greater than 1.

So it has to be something else, but since probability calculus and me keep a safe distance from each other, I'm not getting anywhere on my own.


Edit: I got so far that it's:

[Sum i=n..6n]( P(X=i)*[Sum j=m..i-1](P(Y=j)) )


The part I can't wrap my puny brain around is how you get P(X=i) for any given values of i and n.

So I guess my real question is: If you roll n dice for a total value of X, what's P(X=i) (where i is any fixed number)?