Probability question on coin flipping

tongzilla · 2009-05-26 14:06:28

Hi guys, please help me with this problem (not homework, just wondering myself...)

What's the probability that I will flip 10 heads in a row exactly once if I flip a coin 1000 times. What about 10,000 times? Also, what's the probability that I will flip 10 heads in a row once or more if I flip the coin 10,000 times?

I know the probability that I will flip 10 heads in a row if I flip 10 times is 0.5^10=0.000977

But then I'm stuck after this...

Thanks!

Last edited by tongzilla (2009-05-26 14:07:46)

tongzilla · 2009-05-27 00:11:05

no one?

bobbym · 2009-05-27 08:02:34

Hi tongzilla;

Also, what's the probability that I will flip 10 heads in a row once or more if I flip the coin 10,000 times?

This is the recurrence that solves your problem.

To get a closed form is all but impossible but luckily we don't need to.

These are the initial conditions.

Each one of the initial values represents the number of ways that 10 or more in a row cannot occur for each number of flips. For example in 10 flips a[10]=1023 which means there are 1023 ways for 10 in a row not to occur. Now we just run the recurrence forward to 10000.

There are

ways where there are no 10 or more in a row.

The total number of ways to flip a coin 10000 times is

.

So the answer is

The chance that in 10000 flips of a coin that there is 1 or more runs of 10 or more heads in a row is .99258

Last edited by bobbym (2009-11-21 10:06:57)

tongzilla · 2009-05-27 13:53:38

wow that's some high level mathematics (for me). Never done this in high school. Thanks for taking the time to do this. If the coin was biased (e.g. 70% chance tails; 30% chance heads), how do i take that into account?

bobbym · 2009-08-26 21:07:39

Hi;

tongzilla wrote:

Also, what's the probability that I will flip 10 heads in a row once or more if I flip the coin 10,000 times?

For numerical work like this. A good rule of thumb is a problem has to solved in 2 different ways. Then there is some confidence in the result.
So here is another method to do the problem: It uses an absorbing markov chain:

Here is the state matrix called A.

The initial state vector b is:

The last answer is the absorbing state we are interested in.

So P(1 or more runs of 10 or more heads in a row in 10000 coin tosses) = .99258
This is in agreement with the answer of post #3.

Last edited by bobbym (2009-08-31 23:54:19)

tongzilla · 2009-08-27 00:40:46

wow thanks!

bobbym · 2009-08-27 10:26:52

Hi tongzilla;

tongzilla wrote:

wow thanks!

I suppose thank you is the correct and polite reply to a compliment no matter how undeserved it is. Please keep in mind that if I understand it, it is trivial. I have only answered the easiest part of your original query.

tongzilla wrote:

If the coin was biased (e.g. 70% chance tails; 30% chance heads), how do i take that into account?

The markov chain approach allows the solution of your next question:

Same explanation as above.

Yields:

The last one is again the absorbing state we are interested in.

So P(1 or more runs of 10 or more heads in a row in 10000 coin tosses) = .04045

Notice with the biased coin the event is now rare, only 4%. With an unbiased coin it was more than 99%.

Last edited by bobbym (2009-08-27 10:27:42)

bobbym · 2009-09-01 00:03:55

Hi tongzilla

tongzilla wrote:

Also, what's the probability that I will flip 10 heads in a row once or more if I flip the coin 10,000 times?

Here is a third way to get the answer. This one uses a formula derived by Feller.

r = how many in a row = 10
p = probability of a single head= 1/2
n = number of flips = 10000

So we have the same answer derived in 3 different ways. See post#3 and post #5.

tongzilla wrote:

If the coin was biased (e.g. 70% chance tails; 30% chance heads), how do i take that into account?

Here is a second way to get that answer.

r=how many in a row = 10
p=probability of a single head= 3/10
n=number of flips = 10000

We have derived the same answer in 2 different ways, see post #7

tongzilla wrote:

What's the probability that I will flip 10 heads in a row exactly once if I flip a coin 1000 times? 10000 times?

This is the toughest part of your question.

Here is a generating function that I came up with for this problem:

See that 12 x^13 term, that says there are 12 ways to get 10 heads in a row once in 13 flips of a coin. The coefficient of x^1000 is the the number of ways to get 1 case of 10 heads in a row in a thousand flips of a coin. A combinatorics problem has been reduced to the expansion of a rational function.

Here is a recurrence form that I also came up with. It solves the same problem.

with:

I expanded the GF using a computer and ran the recurrence to 991 to get the same answer namely:

Now you divide by the total number of ways which is 2^1000

So there is a 15% chance that I will flip exactly 1 case of 10 heads in a row in a thousand flips of a coin.

For 10000 flips the probablity is only .018271 or about 1.8%. This makes sense, for more flips it is much harder to have only one run of 10 in a row heads. This completes your question.

Last edited by bobbym (2009-09-01 01:48:07)

Seattle_MathMan · 2009-10-17 11:27:01

FANTASTIC! Three different methods is GREAT. I get what's going on in post #3, and in post #5. I'm having a hard time making it through post #8. bobbym, could you either write a bit more about how this third method is working, or maybe LINK to a page (or suggest a TEXT) that might help explain the details of this third method.

I enjoyed the time I spent with the first two methods. I hadn't seen either of these techniques before I found this page while trying to answer a question similar to tongzilla's. I'm looking forward to understanding the post #8 method, but, for the moment, I'm stuck.

Thanks for your help!!

bobbym · 2009-10-17 11:35:04

Hi Seattle_MathMan;

Can you please indicate where you are stuck and I will try to help.

Seattle_MathMan · 2009-10-17 12:01:51

NPI, but I can't make Heads or Tails of the formula. I see your key for r, p and n. I'm wondering if there are words to use in talking about "x"?

Where I'm stuck is really at the beginning. Is there a TEXT or WEBPAGE that explores how this formula from Feller is derived?

Thanks a lot!

bobbym · 2009-10-17 12:16:52

Hi;

NPI,

Please tell me what NPI means, I am stuck.

but I can't make Heads or Tails of the formula.

This is also a difficult part. It is supposedly from "An Introduction to Probability Theory and its Applications v1,v2 v3" by William Feller. He devoted 24 pages to the derivation of this formula. I am not totally through all 3 volumes. It is a tough read and probability and combinatorics are my favorites.

Seattle_MathMan wrote:

(or suggest a TEXT)

This is what I read to start.

My understanding of generating functions began with "Generatingfunctionology" , Herbert S. Wilf (The greatest all around mathematician alive). Also Riordans book on combinatorics.

The methods to create recurrence formulae from generating functions are covered in a Combinatorics book by the soviet, Villenkin.

Absorbing chains and stochastic matrices from "Finite Mathematics 4th ed.", by Mizrahi and Sullivan and the books by James T. Sandefur.

Last edited by bobbym (2009-11-15 09:51:04)

Seattle_MathMan · 2009-10-17 13:43:25

Thanks for the book recommendations! is the 4th ed. better than the later editions of the Mizrahi and Sullivan? Amazon has third-parties selling used copies of the 9th edition for a buck.

I didn't have any experience with the methods you used in post #3 and #5. I sat down with them both in a morning, and made sense of each. I find them both kinda elegant. the method in post #8 I trust, but to my eyes right now, it looks UGLY.

I've been talking my friends through the first two methods, and they get them, but then ask: "can't you just do it with BINOMIALS, or nCr, or Pascal's triangle.....or something simple like that". I tell them that my sense of Probability is that it gets DIFFICULT QUICKLY, and that while this problem is SIMPLE TO POSE it's a little harder to crack than some High-School level Probability questions that might seem somewhat similar on the surface.

.....but here's my question: would you use any of these terms:
>> BINOMIALS, or nCr, or Pascal's triangle
in connection with what you've done in Post #8?

And.....is there any way to "talk around" the idea of what x represents/relates to in this formula?

Also, could you tell me which vol. of the Feller has the 24 pages I'm looking for?

Thanks, bobbym!

NPI = No Pun Intended.

bobbym · 2009-10-17 18:41:23

Hi Seattle_MathMan;

FANTASTIC!

Thanks, but not true. All solved problems are trivial and the ones solved by me beyond trivial.

Get the 9th edition! I picked mine up at a library sale for 50 cents. Mine is only the 4th ed. and it is the business and social science version so it is not as advanced as it could be.

I've been talking my friends through the first two methods, and they get them, but then ask: "can't you just do it with BINOMIALS, or nCr, or Pascal's triangle.....or something simple like that". I tell them that my sense of Probability is that it gets DIFFICULT QUICKLY, and that while this problem is SIMPLE TO POSE it's a little harder to crack than some High-School level Probability questions that might seem somewhat similar on the surface.

I don't think there is any simple way to do any part of that problem. Don't get me wrong, I am sure that someone like Feller,Wilf, Zeilberger, Riordan etc. could dust it off easily. That is only because they know deeper math. Intermediate Counting & Probability by David Patrick says that if an answer isn't simple then the problem probably doesn't have an simple binomial solution.

the method in post #8 I trust, but to my eyes right now, it looks UGLY.

Don't trust it! Verify it for yourself! There is no place in math for trust or faith. Check everything by everybody.

The formula by Feller is derived by deep concepts. The generating function and the recurrence are of necessity long. There beauty is that they are amenable to computer solution. To me the changing of a probability or combinatorics problem to a mere matrix multiplication or the expansion of a rational functional or polynomial is beautiful.

As problems grow in length and complexity (beyond book problems) you will find that the generic approach is to think of formulating them in terms of sums, integrals, trees,graphs, generating functions, markov chains, random walks, lattices and recurrences. This is because all of those are well implemented in computer algebra systems. In other words computer methods not hand methods. It is a tremendous advantage for your computer to be able to assist you.

Also, could you tell me which vol. of the Feller has the 24 pages I'm looking for?

Yes, volume 1 Chapter 13 Recurrent Events p 312. It is extremely difficult. As far as I can tell the formula for x is a truncation of 4.11 or 7.11, I am not sure.

The x here is just an approximation. It is the truncated form of some series. I don't even know what the next terms are. I could only surmise what they are. Fortunately, you don't have to understand a formula to use it!

Last edited by bobbym (2009-11-15 09:55:37)

bobbym · 2009-11-14 13:06:42

Hi Seattle_MathMan;

If you get to see this:

Seattle_MathMan wrote:

I've been talking my friends through the first two methods, and they get them, but then ask: "can't you just do it with BINOMIALS, or nCr, or Pascal's triangle.....

I don't think about this set of problems often but looking around I came across a forum with a similar problem. WARNING - similar problems does not imply similar solutions. I don't think they can get very far with those approaches. But there is an interesting idea there.

http://www.mymathforum.com/viewtopic.php?f=24&t=9688

Last edited by bobbym (2009-11-14 13:11:21)

bobbym · 2009-11-21 09:46:31

Hi;

Also, what's the probability that I will flip 10 heads in a row once or more if I flip the coin 10,000 times?

I have come up with a better way to do this recurrence:

Based on a method by Uspensky:

This is a little easier to compute and much easier on the eyes but not easier to get a closed form for.

Running the recurrence forward we of course get. .992583, same as above.

Last edited by bobbym (2009-11-21 09:54:26)

Seattle_MathMan · 2009-11-30 06:40:42

Hi Bobbym (or anyone else reading this). I had a question come up about this problem that I didn't know how to answer, and I was wondering if you could help. (Re: the transition or state matrix that you have in post #5) is this matrix Diagonalizable? Since we get two different results (depending on the order of multiplication) when multiplying this matrix by its transpose, we know that it can't be converted to a diagonal matrix by a unitary transform -- but I don't know whether this means the matrix is NOT Diagonalizable. What might it mean to say or show that it is or isn't Diagonalizable?

I'm way out of my field with this question. Thanks so much for your help!

bobbym · 2009-11-30 11:41:45

Hi Seattle_MathMan;
I understand where you are going with this. If you could diagonalize A then A^10000 would be easy to compute. To diagonalize a matrix A you need to find some P where P^-1 * A * P is a diagonal matrix. If you cannot find such a P then A is not diagonizable.

Since A in this case is a 10 x 10 matrix if we get 10 different eigenvalues we can diagonalize the matrix. But this is not the case. Also some of the eigenvalues are complex so we cannot diagonalize A over the reals but it may be diagonalizable over C.

Seattle_MathMan · 2009-11-30 12:08:25

Sorry about that -
the main question is just
1) Is the matrix listed in post #5 DIAGONALIZABLE?

the other two related questions are:

2) Does the fact that this is the 'transistion' or 'state' matrix for an absorbing Markov Chain tell us anything about whether it IS or ISN"T Diagonalizable?

and

3) (again taking into consideration the context -- that this is a 'transistion' or 'state' matrix for an absorbing Markov Chain). Would there be any special significance in knowing that this matrix IS or ISN'T diagonalizable?

Hope this helps.

Thanks much!!

bobbym · 2009-11-30 12:14:22

Hi;

Would there be any special significance in knowing that this matrix IS or ISN'T diagonalizable?

Yes, If you could diagonalize A then A^10000 would be easy to compute.

Is the matrix listed in post #5 DIAGONALIZABLE?

I don't think so.
Since A in this case is a 10 x 10 matrix if we had 10 different eigenvalues we could diagonalize A. But this is not the case. Also some of the eigenvalues are complex so we cannot diagonalize A over the reals.

2) Does the fact that this is the 'transistion' or 'state' matrix for an absorbing Markov Chain tell us anything about whether it IS or ISN"T Diagonalizable?

I would think, no. At least I am not aware of any relationship between a transition matrix and whether or not it is possible to have

P^-1 * A * P = D

Seattle_MathMan · 2009-11-30 12:35:27

Thanks Much!!

bobbym · 2009-11-30 12:50:10

Hi Seattle_MathMan'

Wait, we are not done yet!

I wrote:

I don't think so.
Since A in this case is a 10 x 10 matrix if we had 10 different eigenvalues we could diagonalize A. But this is not the case. Also some of the eigenvalues are complex so we cannot diagonalize A over the reals.

I am relying on the theorem that says If A is an n x n matrix and A has n real and different eigenvalues then A is diagonalizable.

I have not proven that it is not diagonalizable over C. Trouble is in the examples in my reference books and notes, I never came across a diagonalizable matrix that didn't conform to the theorem above. Unfortunately, this page is muddying up the waters.

http://www.ltcconline.net/greenl/course … zation.htm

I have a strong feeling it is not diagonalizable because when I computed P^-1 * A * P using a method much like this page:

http://www.ma.iup.edu/projects/CalcDEMma/JCF/jcf2.html

I did not get a diagonal matrix.

You guys are having some interesting thoughts about these problems, how about posting your guesses as well as your conclusions. I would like to see them, if I may.

bobbym · 2013-12-26 22:05:37

Hi tongzilla;

It seems when I posted here so long ago I was unfamiliar with some of the literature. The great De Moivre a friend of Newton knocked this off a long time ago.

Thanks to him we have another approach. I will use it for:

n = 10000
H = 10

running it off I get 0.9925838943865506 which agrees nicely with the other methods.

Math Is Fun Forum

#1 2009-05-26 14:06:28

Probability question on coin flipping

#2 2009-05-27 00:11:05

Re: Probability question on coin flipping

#3 2009-05-27 08:02:34

Re: Probability question on coin flipping

#4 2009-05-27 13:53:38

Re: Probability question on coin flipping

#5 2009-08-26 21:07:39

Re: Probability question on coin flipping

#6 2009-08-27 00:40:46

Re: Probability question on coin flipping

#7 2009-08-27 10:26:52

Re: Probability question on coin flipping

#8 2009-09-01 00:03:55

Re: Probability question on coin flipping

#9 2009-10-17 11:27:01

Re: Probability question on coin flipping

#10 2009-10-17 11:35:04

Re: Probability question on coin flipping

#11 2009-10-17 12:01:51

Re: Probability question on coin flipping

#12 2009-10-17 12:16:52

Re: Probability question on coin flipping

#13 2009-10-17 13:43:25

Re: Probability question on coin flipping

#14 2009-10-17 18:41:23

Re: Probability question on coin flipping

#15 2009-11-14 13:06:42

Re: Probability question on coin flipping

#16 2009-11-21 09:46:31

Re: Probability question on coin flipping

#17 2009-11-30 06:40:42

Re: Probability question on coin flipping

#18 2009-11-30 11:41:45

Re: Probability question on coin flipping

#19 2009-11-30 12:08:25

Re: Probability question on coin flipping

#20 2009-11-30 12:14:22

Re: Probability question on coin flipping

#21 2009-11-30 12:35:27

Re: Probability question on coin flipping

#22 2009-11-30 12:50:10

Re: Probability question on coin flipping

#23 2013-12-26 22:05:37

Re: Probability question on coin flipping

Board footer