Probability of a winning consecutive $k$-subset out of $n$ coin flips Assume we flip a coin $n$ times. A $k$-sequence is defined as any consecutive sequence of coin flips of length $k$. Call a $k$-sequence "winning" if there are strictly more heads than tails. What is the probability of there being a winning consecutive $k$-sequence in $n$ tosses?

In order to clarify some of the definitions, here are some examples. Assume we have flipped the sequence $\rm HHTHT$.
$2$-sequences: $\rm \underbrace{HH}THT, H\underbrace{HT}HT, HH\underbrace{TH}T, HHT\underbrace{HT}$, so $\rm HH, HT, TH, HT$ are consecutive $2$-sequences.
Winning $2$-sequences: $\rm HH$.

All $4$-flips with winning $2$-sequences highlighted, if there are multiples, I have selected the first one:


*

*$\rm \underbrace{HH}HH $

*$\rm \underbrace{HH}HT $

*$\rm \underbrace{HH}TH $

*$\rm \underbrace{HH}TT $

*$\rm HT\underbrace{HH} $

*$\rm HTHT$ (no winning $2$-sequences)

*$\rm HTTH$ (no winning $2$-sequences)

*$\rm HTTT$ (no winning $2$-sequences)

*$\rm T\underbrace{HH}H$ 

*$\rm T\underbrace{HH}T$

*$\rm THTH$ (no winning $2$-sequences)

*$\rm THTT$ (no winning $2$-sequences)

*$\rm TT\underbrace{HH}$

*$\rm TTHT$ (no winning $2$-sequences)

*$\rm TTTH$ (no winning $2$-sequences)

*$\rm TTTT$ (no winning $2$-sequences)
Out of the $8$ combinations, there are $4$ which have winning $2$-sequences (we can choose $2$ consecutive flips from the sequence which have more heads than tails).  So $p(4, 2) = 8/16 = 1/2$.
 A: Throwing in some observations that could help someone go further. 


*

*Some notation, I use $N(k,n)$ for the number of length $n$ sequences that have at least one $k$ winning sequence. Define this to be $0$ when $k>n$.

*Remark that $N(n,n)=2^{n-1} - ((1+(-1)^n)/4){n\choose n/2}$. This is the number of binary sequence with more $1$ than $0$. See A058622

*Observe that $N(k,n)=2N(k,n-1)+ $Offset since any "good" sequence of length $n-1$ will be "good" at length $n$ whether we add $H$ or $T$. The problem is then to characterize the offset.

*Let's look at the offset for the case $k=2$


*

*First for $n=2$, we have
$$
\color{green}{HH}\\
HT\\
\color{blue}{TH}\\
TT
$$
The green one is a good one and the blue one is one that can become winnning at the next step.

*We keep going on with $n=3$
$$
\color{green}{HHH}\\
\color{green}{HHT}\\
\color{blue}{HTH}\\
HTT\\
\color{green}{THH}\\
THT\\
\color{blue}{TTH}\\
TTT
$$
Colors are as above. We have some sort of characterization of the offset for $N(k,n)$. It is the number of blue colored sequence in the sets of length $n-1$. Call this number $F(n-1)$, so that $N(2,n)=2N(2,n-1)+F(n-1)$. Black at time $n$ is blue at time $n-1$ plus black at time $n-1$ (Those that will add a $T$). Blue at time $n$ is black at time $n-1$ (Those that will ad a $H$). From this, we see that $F(n-1)$ is the (n-1)^{th} Fibonacci number.

*We finally get that $N(2,n)= 2N(2,n-1)+Fibo(n-1)$. This is A008466
I believe some similar offset exists for other $k$, but I haven't been able to figure it out. For $k=3$, I believe the formula is given by this sequence. It is not explicitely written as $N(3,n)=2N(3,n-1)+$ offset,however if we write it this way, the offset (the number of blue) seems to be this one. The reccurence relation for Blue and Black in this case seems to be
$$
Blue(n)=Black(n-1)+Black(n-2)\\
Black(n)=Black(n-2)+Blue(n-2)
$$
I conjectured that the blue/black reccurence for $k$ would be
$$
Blue(n)=\sum_{i=1}^{k-1} Black(n-i)\\
Black(n)=Black(n-(k-1))+Blue(n-(k-1))
$$
However both seems to fail for $k=4$. The number $N(4,n)$ is given by this, and the first Blue and Black numbers are, starting at Blue$(4)$ and Black$(4)$, Blue: $\{3,5,9,17,28,47,81,\cdots\}$ and the Black: $\{8,14,24,40,69,119,204\}$. Found no pattern on those yet.
