Probability problem (throwing a coin n times)

  • Thread starter quasar987
  • Start date
  • Tags
    Probability
In summary, the number of ways to throw a coin n times without ever throwing tails two times in a row is given by the recursive formula f_n=f_{n-1}+f_{n-2}, where f_n represents the number of ways with n tails and f_{n-1} and f_{n-2} represent the number of ways with n-1 and n-2 tails respectively. This can be proven by considering the maximum amount of tails that can come out while respecting the condition, arranging the tails and heads in a specific order, and accounting for all possible numbers of tails that can come out. Another combinatorial proof involves considering the n-1'th length sequences and adding either a T or H to
  • #1
quasar987
Science Advisor
Homework Helper
Gold Member
4,807
32
Let us note [itex]f_n[/itex] the number of ways to throw a coin n times without ever throwing tails two times in a row. Show that [itex]f_n=f_{n-1}+f_{n-2}[/itex].

First of all, if the coin is thrown n times, then the maximum amount of tails that can come out while still respecting the 'no two tails in a row' condition is [itex]\left[ \frac{n+1}{2}\right] [/itex]. (For instance, if n=3, the maximum amount of tails that can come out is 2, and [itex]\left[ \frac{3+1}{2}\right]=[2]=2[/itex] as it should. If n=4, the maximum amount is 2 also and [itex]\left[ \frac{4+1}{2}\right]=[2.5]=2[/itex].)

Now, for a given number j of tails that come out, we can arrange the tails and heads in

[tex]\binom{n-j+1}{j}[/tex]

different ways. To get this result, I said "take the j tails, and j-1 heads and arrange them like so: T H T H ... H T. Now there are no two tails together and there remains n-j-(j-1)=n-2j+1 heads to distribute. The ways to distribute the remaining head can be seen as the number the ways to put n-2j+1 balls into j+1 baskets (there is one basket on each side of each T). This is known to be

[tex]\binom{(n-2j+1)+(j+1)-1}{(j+1)-1} = \binom{n-j+1}{j}[/tex]

And to account for all the possible numbers of tails that can come out, we sum over all j's:

[tex]f_n=\sum_{j=0}^{\left[ \frac{n+1}{2}\right]}\binom{n-j+1}{j}[/tex]

The problem is, I've shown that this does not satisfy the recurence relation! :frown: So, do you see something wrong with what's above?

Thanks!
 
Last edited:
Physics news on Phys.org
  • #2
You're right when you say you start with a string THTH...THT, of length 2j-1, and then you need to add the remaining n-2j+1 heads. Now you can add any number of heads in any of the j-1 positions between tails or at either end of the string. (Note that the basket on the right side of an interior tail is the same as the one to the left of the next tail, and this may be your problem.) In other words, you need to come up with a sequence of j+1 nonnegative integers that sum to n-2j+1. Do you know how many such sequences there are?
 
  • #3
But this is exactly what I did. Is there a problem with my number of baskets? (j+1) or with my "number of such sequences"?
 
  • #4
Ah, I found a mistake in my "counter-proof", let me retry.
 
  • #5
There is a more direct combinatorial proof:
Consider the n-1'th length sequences. If they end in H, then you can add a T or an H to generate an n-length sequence. If they end in T, then you can add an H to generate an n-length sequence. So,
fn = 2*(# of n-1th seq ending in H) + (# of n-1th seq ending in T)
With a little argument you can turn this into
fn = 2f(n-2) + f(n-3)
and you can derive the other recurrence from that.

Edit: actually you can't derive the other recurrence from that, without resorting to the initial conditions. A different way to break it down is:
fn = (# of nth seq ending in H) + (# of nth seq ending in T)
which gives you what you want
 
Last edited:
  • #6
More direct is good! I've managed to proove it for n=even and I suspect it will be similar for n=odd, but it was lenghty!

After reading your post 3 times, I still don't see what you're idea is!

One source of confusion for instance is whwn you say

"Consider the n-1'th length sequences. If they end in H, then you can add a T or an H to generate an n-length sequence. If they end in T, then you can add an H to generate an n-length sequence."

What makes you think you have a T or an H left in hand after placing all your T and H. And when in that, did you take care that there be no two T together? Plz explain, it's late here.
 
  • #7
I'll explain the first one in more detail because it's not quite what you want but it helps for the second one (which is exactly what you want).

What makes you think you have a T or an H left in hand after placing all your T and H. And when in that, did you take care that there be no two T together?
You have as many T's and H's as you want. The way that you ensure that there are no two T together is that:
1. If the n-1th seq (by this I mean, a sequence of H's and T's of length n-1 such that no two T's are adjacent) ends in H, then you can place an T or an H without causing two T's to be placed together
2. If the n-1th seq ends in T, then you can place only an H without causing two T's to be placed together.

Now for the first case, we want to count the number of n-1th seqs that ends in H. If we strip the H off then the remaining n-2th prefix can be any n-2th seq at all, so there are f(n-2) ways to form n-1th seqs ending in H. Then you add back a T or an H, multiplying this number by 2, so this enumeration contributes 2 * f(n-2) to fn

In the second case, if the n-1th seq ends in T, then if you strip the T off, the remaining n-2th seq must end in H. Strip THAT H off and you get an unrestricted n-3th seq. You add back HTH to that and get a nth seq, so this enumeration contributes f(n-3) to fn.

So fn = 2*f(n-2) + f(n-3)

Showing that fn = f(n-1) + f(n-2) is similar, only breaking it down as
fn = (# of nth seq ending in H) + (# of nth seq ending in T)
Think in terms of stripping the last letter off and considering what must remain.
 

1. What is the probability of getting heads on a single coin toss?

The probability of getting heads on a single coin toss is 1/2 or 50%. This is because there are only two possible outcomes - heads or tails - and they are equally likely to occur.

2. If I toss a coin 10 times, what is the probability of getting exactly 5 heads?

The probability of getting exactly 5 heads when tossing a coin 10 times is 0.246 or 24.6%. This can be calculated using the binomial distribution formula, which takes into account the number of trials, the probability of success, and the number of successes desired.

3. What is the probability of getting at least one head when tossing 3 coins?

The probability of getting at least one head when tossing 3 coins is 7/8 or 87.5%. This can be calculated by finding the probability of getting all tails (1/8) and then subtracting it from 1.

4. How many times do I need to toss a coin to have a 95% chance of getting at least one head?

You would need to toss a coin 60 times to have a 95% chance of getting at least one head. This can be calculated using the binomial distribution formula or by using a probability calculator.

5. Can the results of previous coin tosses affect the probability of the next toss?

No, the results of previous coin tosses do not affect the probability of the next toss. Each coin toss is an independent event and the probability of getting heads or tails remains the same regardless of previous outcomes.

Similar threads

  • Calculus and Beyond Homework Help
Replies
15
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
63
  • Calculus and Beyond Homework Help
Replies
9
Views
763
  • Calculus and Beyond Homework Help
2
Replies
37
Views
4K
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
12
Views
949
  • Calculus and Beyond Homework Help
Replies
4
Views
951
Back
Top