Probability of getting 6 heads in a row from 200 flips and intuition about this high value A few days ago I had an argument with a friend about this question :

What is the probability of getting 6 heads in a row from 200 flips ?

I argued it is high probability (significantly bigger than a half) while he argued it is low probability.
When I tried to give exact formula I failed, so we checked the web were the answer was about 84%, yet he is still not convinced so from this I have two questions:

*

*What is the exact formula for $k$ Heads in a row (consecutive) out of $n$ coin flips?


*(Not a mathematical) How to convince my friend that 6 in a row have high probability? Meaning what is the intuition behind the question ?

All the possible different results of $n$ flips of a (fair) coin correspond to all possible
binary strings of length $n$, which clearly are $2^n$.
So let's talk of binary strings, with $1=H, \; 0=T$.
a) Exact formula
Partition the $2^n$ strings into those containing $s$ ones and $m=s-n$ zeros.
Each partition will contain $\binom{n}{s} =\binom{n}{m} $ strings.
Now
the number of strings  with $s$ "$1$" and $m$ "$0$",  having runs of at most $r$ consecutive ones
is given by
$$
N_b (s,r,m + 1)\quad \left| {\;0 \leqslant \text{integers  }s,m,r} \right.\quad  = \sum\limits_{\left( {0\, \leqslant } \right)\,\,k\,\,\left( { \leqslant \,\frac{s}
{r}\, \leqslant \,m + 1} \right)} {\left( { - 1} \right)^k \left( \begin{gathered}
  m + 1 \\ 
  k \\ 
\end{gathered}  \right)\left( \begin{gathered}
  s + m - k\left( {r + 1} \right) \\ 
  s - k\left( {r + 1} \right) \\ 
\end{gathered}  \right)} 
$$
whose generating function in $s$ is
$$
F_b (x,r,m + 1) = \sum\limits_{0\,\, \leqslant \,\,s\,\,\left( { \leqslant \,\,r\,\left( {m + 1} \right)} \right)} {N_b (s,r,m + 1)\;x^{\,s} }  = \left( {\frac{{1 - x^{\,r + 1} }}
{{1 - x}}} \right)^{m + 1} 
$$
as explained in this related post
Therefore
the number of binary strings  with $n$ bits,  having runs of at most $r$ consecutive ones
is
$$ \bbox[lightyellow] {  
\eqalign{
  & C(n,r) = \sum\limits_{\left( {0\, \le } \right)\,\,m\,\,\left( { \le \,n} \right)} {
N_b (n - m,r,m + 1)}  =   \cr 
  &  = \sum\limits_{\left( {0\, \le } \right)\,\,m\,\,\left( { \le \,n} \right)} {
\sum\limits_{\left( {0\, \le } \right)\,\,k\,\,\left( { \le \,{s \over {r + 1}}\, \le \,m + 1} \right)} {\left( { - 1} \right)^k \binom{m+1}{k}
 \binom{
  n - k\left( {r + 1} \right)}
  {n - m - k\left( {r + 1} \right) } } }  \cr} 
 } \tag{1}$$
whose generating function in $n$ is
$$
G(z,r) = \sum\limits_{0\, \le \,n} {C(n,r)z^{\,n} }  = {{1 - z^{\,r + 1} } \over {1 - 2z + z^{\,r + 2} }}
$$
This is interesting because from it it is possible to demonstrate that the above approach
coincides with the Markovian approach proposed by @kimchi lover.
We conclude that the probability you are looking for is
$$ \bbox[lightyellow] {  
P_{\,200,\,6}  = 1 - {{C(200,5)} \over {2^{\,200} }} = 0.8009 \ldots 
 } \tag{2}$$
b) * Asymptotics*
For large $n$ the exact formula (1) would become quite "heavy", and we need an asymptotic formula.
A very interesting fact is that $C(n,r)$ are just the $(r+1)$-nacci numbers,
apart from a shift in $n$ depending on their definition.
So $C(n,5)$ corresponds to the Hexa-nacci numbers
$$
C(n,5) = F_{n + 6}^{\left( 6 \right)} 
$$
as defined in Wikipedia.
In this paper "A Simpliﬁed Binet Formula for k-Generalized Fibonacci Numbers" - G.P.B. Dresden, Z. Du
you can find interesting asymptotic formulas to approximate the Hexa-nacci with a Binet-like formula.
c) Convincing your friend
This is clearly .. the most difficult part.
But you can try via .. [Entropy](https://en.wikipedia.org/wiki/Entropy:
the strings in which $r$ is allowed to go from $6$ up to $200$ are far more "chaotic"
than the strings where $r$ is constrained not to overcome $5$.
