If an unbiased coin is tossed 100 times, what is the probability to find the a sequence of 5 or more continuous heads in the experiment? My Professor says there is no exact way (may be he meant easy method) to find it. Is that true? And I am confused with counting. I simulated this situation using MATLAB.
N=10000;
x=randi([0 1],N,100);
idx1=0;
for i=1:N
idx = findpattern(x(i,:), [1 1 1 1 1]);
%http://blogs.mathworks.com/loren/2008/09/08/finding-patterns-in-arrays/
if(isempty(idx) )
idx1=idx1+1;
end
end
p=1-(idx1/N)
p is around $80 \%$
EDIT : If there is an exact method to find this probability, then can someone do it?
Let $a_n$ be the number of $n$-letter binary words with no 5 consecutive zeroes.
Clearly $a_i=2^i$ for $i<5$.
Defining $b_n$ to be the words with no 5 consecutive zeroes and ending in $10000$, $c_n$ to be the words with no 5 consecutive zeroes and ending in $1000$, $d_n$ to be the words with no 5 consecutive zeroes and ending in $100$, $e_n$ to be the words with no 5 consecutive zeroes and ending in $10$ and $f_n$ to be the words with no 5 consecutive zeroes and ending in $1$, you get following recurrences:
$a_n=b_n+c_n+d_n+e_n+f_n$
$a_{n+1}=a_n+f_n+e_n+d_n+c_n$
$b_n=c_{n-1}$
$c_n=d_{n-1}$
$d_n=e_{n-1}$
$e_n=f_{n-1}$
$f_n=a_{n-1}$
This reduces to $a_{n+1}=a_n+a_{n-1}+a_{n-2}+a_{n-3}+a_{n-4}$.
Implementing this recurrence is totally trivial and computing $a_n$ for $n=100$ will be done in the blink of an eye.
Now subtract the result from $2^{100}$ and divide by $2^{100}$ and you have your (exact) probability.
A Java implementation finds that the number of 'good words' (at least 5 consecutive zeroes) is 1026935919671913581551557828400 (out of $1267650600228229401496703205376=2^{100}$), which indeed is slightly more than 80%.