Number of coin tosses required to get at least 60 heads in a 100 length sliding window I have been struggling with the below problem (not an assignment), that struck me as rather easy to state but difficult (for me) to solve.
Let's say you have a fair coin with 1/2 probability to get heads or tails, and you start a series of tosses. Given a number of heads (let's say 60 for example), what is the expectation of the number of tosses I will have to perform in order to get 60 heads/40 tails in a 100 tosses "sliding window".
i.e : if I write $S_n=(HHTHTTHT...H)_n=(u_{0}u_{1}...u_{n})$, what is the expected value for $T_{60}=\{min(k)$ such that $(u_{k}..u_{k+100})$ contains 60 heads}.
I tried reasoning with Markov Chains but $(u_{k}...u_{k+100})$ is clearly not a Markov chain as it has memory.
Another way to look at it, could have to compute the probability to reach 60 on the first 100 tosses, and then the following "sliding windows" of length 100 seem to almost follow a random walk, but this is not true as, for example, when you reach 100 heads, you cannot get more.
I think there are formulas to find the expected time of a given pattern, but it will tedious write for a chain of 100 length, and even if I have the expected time for all patterns containing 60 heads, I cannot deduce the expected time for the union of all patterns..
So, I think one method that could work is to explicitly write the probability $P_k$ of hitting 60 heads at time $k$, and not having hit 60 heads before. Then developping by conditioning => $P_k = P($hitting 60 heads at time k$|$we have not hit 60 heads at any time $k'<k)$*$P($we have not hit 60 heads at any time $k'<k)$
$P($we have not hit 60 heads at any time $k'<k)$ is computable by simple counting arguments (I count all coin toss series of length n containing at least one pattern of 60 heads).
$P($hitting 60 heads at time k$|$we have not hit 60 heads at any time $k'<k)$ depends only on the $k'\geq k-100$ (the overlapping sliding windows of length 100). So it looks computable, again by counting arguments but it looks very tedious...
So I am looking for insights on this one :

*

*Is my reasoning by counting arguments correct ?

*Is there another more elegant way to solve this problem ?

PS : I ran monte carlo simulations so that I can solve this problem numerically but I am interested in closed form solutions
 A: Using the fact that this is, indeed, a Markov chain. I can write the first passage times equations
$$k_i = 0, i \in A$$
$$k_i =1 + \sum_j{p_{ij}k_j}, i \in A^c$$
Which seems to be quite complex to resolve even if all equations only have 2 terms on the rhs.
My attempt at this :

*

*For a state $(HHT...THT)$ that I rewrite as $(a_0a_1...a_{99})$ with $a_k=1$ if the toss is Heads, and $a_k=0$ if the toss is Tails. I attribute the number $i=a_0+2*a_1+...+2^{99}*a_{99}$, so that all states are numbered from $0$ to $
2^{100}-1$

*Now my equations become :
$$k_i=0, \text{ if } \sum_k{a_k}\geq60$$
$$k_i=1+k_{\frac{i-a_0}{2}}*0.5+k_{\frac{i-a_0}{2}+2^{99}}*0.5, \text{ if } \sum_k{a_k}<60$$
This looks like something that is solvable, but in practice I am at a loss of writing explicitly the solutions (maybe by using a nicer numbering than the one I propose ?).

NB : I wrote down the equations for a lower dimensional problem (expected time to reach 2 heads out of a running series of 3 coin tosses), and I do find a solution, namely :
$$k_3=k_5=k_6=k_7=0$$
$$k_0=k_1=\frac{14}{3}$$
$$k_2=\frac{10}{3}$$
$$k_4=\frac{8}{3}$$
After that it is only a matter of probabilizing by the initial state being $i$, and they all have the same probability of $\frac{1}{8}$.
On the other hand, I don't manage to generalize to higher dimensions...
A: Following empy2 suggestion I try to simplify the problem by assuming that the sum of heads is a markov chain with "mean reverting" probabilities.
See below the results of simulations.
For $n = 3$ tosses and $k= 2$ heads I get :

*

*expected number of tosses = 4.914 through MCL simulations (10000 drawings) using the exact modelization

*expected number of tosses = 5.237 through MCL simulations (10000 drawings) using the sum of heads modelization

To be noted that 1) is in line with the exact solution I computed above ($=3+\frac{1}{8}×\frac{46}{3}$)
For $n = 100$ tosses and $k= 60$ heads I get :

*

*expected number of tosses = 848.705 through MCL simulations (10000 drawings) using the exact modelization

*expected number of tosses = 1062.42 through MCL simulations (10000 drawings) using the sum of heads modelization

So the simplified modelization does not seem to converge, even if it is "not too bad"
