1
   

Coin toss problem

 
 
Reply Fri 19 Aug, 2016 04:53 am
A coin is tossed m+n times, m>n, what is the probability of getting at least m consecutive heads?
  • Topic Stats
  • Top Replies
  • Link to this Topic
Type: Question • Score: 1 • Views: 657 • Replies: 11
No top replies

 
puzzledperson
 
  0  
Reply Sun 21 Aug, 2016 08:09 pm
@Officialmepiyush,
Assume that n is nonzero.

The probability is the number of permutations with at least one run of m or more heads ("qualifying permutations"), divided by the total number of permutations.

The total number of permutations is 2^(m+n).

The length of runs of heads in qualifying permutations ranges from m to m+n. Because m > n there is no qualifying permutation with two sets of m or longer runs separated by one or more tails. Each qualifying permutation therefore has just one qualifying run of heads, of length between m and m+ n (inclusive).

It's easy to see that there is just one qualifying permutation of length m+n, two of length m+n-1, and if applicable, three of length m+n-2, etc.

The number of qualifying permutations depends on the size of n.

If n =1 there are 1+2 = 3 qualifying permutations.

If n = 2 there are 1+2+3 = 6 qualifying permutations.

If n = 3 there are 1+2+3+4 = 10 qualifying permutations.

And so on, with this arithmetic progression.

Again, probability = qualifying permutations / total permutations.
engineer
 
  1  
Reply Tue 23 Aug, 2016 11:47 am
@puzzledperson,
This is not correct, but I can't come up with the right formula. Just as a check, for m=4, n=3, there are 128 permutations and 20 qualifying permutations. For m=5, n=2, there are 8 and for m=6, n=1 there are three.
puzzledperson
 
  -1  
Reply Tue 23 Aug, 2016 11:08 pm
@engineer,
I think it is right, and that you are in error.

For example, if m = 5 and n = 2, just draw seven hash marks (short vertical lines) in a row on a piece of ruled paper.

There is one qualifying permutation of length seven. There are two of length six, one of which includes the rightmost mark, and one of which includes the leftmost. Starting from the leftmost, there are three of length five (which is obvious if you move progressively right until you start counting on the third from the left and stop counting on the far right). That's six.

The other cases are also exactly as I said. Visual confirmation is a very easy way to see this. If I have made an error, point it out.
ekename
 
  1  
Reply Wed 24 Aug, 2016 12:46 am
@Officialmepiyush,
Quote:
A coin is tossed m+n times, m>n, what is the probability of getting at least m consecutive heads?


p = (n + 2) / [2 ^ (m+1)]
engineer
 
  2  
Reply Wed 24 Aug, 2016 06:31 am
@puzzledperson,
puzzledperson wrote:

I think it is right, and that you are in error...

The other cases are also exactly as I said. Visual confirmation is a very easy way to see this. If I have made an error, point it out.

For m=3, n=2, the eight permutations are:

HHHTT
HHHTH
THHHT
TTHHH
HTHHH
HHHHT
THHHH
HHHHH

Eight, not six. The two highlighted ones are the ones you missed in your answer. I made a spreadsheet with all permutations for n=3, the answer is 20. For n=4, the answer is 48.
engineer
 
  1  
Reply Wed 24 Aug, 2016 06:37 am
@ekename,
ekename wrote:

p = (n + 2) / [2 ^ (m+1)]

That seems to work, but how did you get that? That makes the number of permutations

[(n+2) * 2^n] / 2

That looks the form I expected but I can't quite get there.
puzzledperson
 
  1  
Reply Wed 24 Aug, 2016 10:33 pm
@engineer,
Doh!

OK, thanks for pointing that out.
0 Replies
 
ekename
 
  1  
Reply Wed 24 Aug, 2016 10:56 pm
@engineer,
A coin is tossed m+n times, m>n, what is the probability of getting at least m consecutive heads?

(1/2)^m + (1/2)^(m+1) + ... + (1/2)^(m+n)

(1/2)^m [ 1 + (1/2)n]

(1/2)^m [ ( 2 + n ) / 2]

( 2+ n ) / [ 2 ^ ( m + 1)]
ekename
 
  1  
Reply Thu 25 Aug, 2016 09:34 pm
@ekename,
A coin is tossed m+n times, m>n, what is the probability of getting at least m consecutive heads?

(1/2)^m + [(1/2)^(m+1) + ... + (1/2)^(m+1)]n

(1/2)^m [ 1 + (1/2)n]

(1/2)^m [ ( 2 + n ) / 2]

( 2+ n ) / [ 2 ^ ( m + 1)]
ekename
 
  1  
Reply Sat 27 Aug, 2016 03:26 am
@ekename,
A coin is tossed m+n times, m>n, what is the probability of getting at least m consecutive heads?

(1/2)^m + [(1/2)^(m+1) + ... + (1/2)^(m+1)] for n terms equal to (1/2)^(m+1)

(1/2)^m [ 1 + (1/2)n]

(1/2)^m [ ( 2 + n ) / 2]

( 2+ n ) / [ 2 ^ ( m + 1)]
engineer
 
  1  
Reply Mon 29 Aug, 2016 08:12 pm
@ekename,
I never understood your solution (although it is correct), but I came up with my own. There are (n+1) groupings of m consecutive objects in m+n positions. Since the other n coin tosses can be anything, you get (n+1)*2^n passing permutations. However, that overcounts because it is double counting runs of m+1 or more. The number double counted is n * 2^(n-1) or (n/2) * 2^n. So the total number of good permutations is (n+1)*2^n - (n/2)*2^n or (n+2)/2 * 2*n. Divide by 2^(m+n) and I get the same answer you did.
0 Replies
 
 

Related Topics

Probability of 11 cards - Question by ptkaisen
Probability - Question by sean2
Exercise in Probability!!! - Question by evinda
Winning chance - Question by ghodhereek
Family Wine Tasting - Question by mrmac
what is the probability of... #4 - Question by w0lfshad3
The chances of a higher power. - Question by ascribbler
 
  1. Forums
  2. » Coin toss problem
Copyright © 2020 MadLab, LLC :: Terms of Service :: Privacy Policy :: Page generated in 0.03 seconds on 07/08/2020 at 08:08:26