An interesting probabiilty problem
Toss a fair coin n times, what is the probability of having at least k consecutive Heads (i.e., we could have more than k consecutive Heads).The problem looks simple but once you tried it, you will find that it is not very easy. It is a very good test for your understanding on Probability :), so I strongly encourage you to have a try! And you may encounter this in an interview!
I will try to post the solution later, if I can solve it.
---
Life is an opportunity to do something.
Labels: mathematics
5 Comments:
Should be a summation of the binomial distribution expression from k to n
P(k) = (n(choose)k)(.5)^k(.5)^n-k
P(n>=k) = summation of P(k) from k to n
I am not sure whether I will agree with this.
For example, let k = 2, n = 5, the binomial distribution also counts this case:
HTHTT,
which is not what we want.
Yes, I tried it for half an hour yesterday and it is indeed a bit tough.
Although currently I can tell nothing about the solution, the summation of binomial probability is surely incorrect.
I heard that it has no analytical solution. True?
The answer can be expressed in terms of the so-called Fibonacci k-step numbers. When k=2 you have the regular Fibonacci numbers, when k=3 you have the tribonacci numbers, when k=4 you have the tetranacci numbers, and so on. The trick is to count the unfavourable configurations, i.e., those sequences with at most k-1 consecutive heads. This can be done, e.g., by counting length-n paths in a particular directed graph with k vertices. (Label the vertices of the graph as 0, 1, 2, ..., k-1. Each vertex is connected to the 0 vertex by an edge labelled T, and vertex i is connected to vertex i+1 by an edge labelled H for i = 0, 1, ..., k-2. Directed paths of length n starting at vertex 0 correspond to unfavourable configurations of length n.) One can easily write a recursion for the number of length n sequences. See Math World for a discussion of these generalized Fibonacci numbers, as well as a mention of this very problem.
Post a Comment
<< Home