Suppose we are tossing a banlanced coin, and we want to compute the expectation of the waiting time for the pattern HTHTH.
Kac's lemma is a result in ergodic theory which states that, for a ergodic transformation and a positive measurable set $A$, $$\int_A n_A d\mu =1$$ Here $n_A$ denote the first return time of the points in $A$ undet $T$.
I wonder how to use Kac's lemma to compute the waiting time, does anyone have an idea?
A little too long for a comment, but not an answer.
You can model this as a Markov Chain (in this case, a random walk on a directed graph) as follows. Intuitively, consider an infinite sequence of coin tosses, and take a sliding window of successive 5 outcomes. Suppose the first 5 tosses gave HHHHH. This is the starting state. Now suppose you get T. So the state is HHHHT. And now you get an H, so the state is HHHTH, etc.
Formally, consider all patterns on 5 coin tosses, so there are 32 of them. These are the states of the MC. Any state has two possible transitions of probability 1/2, obtained by appending either H or T to the end and removing the first coin toss. So HHTHT can transition to HTHTH or HTHTT with probability 1/2. So this gives the Markov Chain M. Think of the corresponding directed graph G, where each edge has the probability of transition. There are 32 vertices, 32 X 2 = 64 edges (two from each vertex), with each edge of probability 1/2. Each vertex also has two incoming edges.
Note that the uniform distribution is the stationary distribution.
So your question becomes: starting from the uniform distribution on (vertices of) G, what is the expected time to reach state HTHTH?
I don't see how Kac's lemma help. Kac's lemma tells us that if you started from HTHTH, then the expected return time is exactly 32 steps.
One can show: if we take 32 steps, then the expected number of occurrences of HTHTH is exactly 1. This is by linearity of expectation and the fact that the stationary distribution is uniform. If one starts from the uniform distribution, the probability of hitting HTHTH is 1/32. This is true for all steps, since the walk remains in the uniform distribution.
I do not know if this would qualify for you as a solution using Kac's lemma, but here it goes ...
The elementary version of Kac's lemma for an irreducible Markov chain with unique stationary distribution $\pi$ states that the expected return time of each state $a$ is $1/\pi(a)$. This follows from the ergodic theory version if you consider the (one-sided) Markov shift associated to the Markov chain and look at the return time of the cylinder set $\{(\omega_i)_{i\geq 0}: \omega_0=a\}$.
As Sesh mentioned, you can formulate your problem in terms of a Markov chain whose states are all the words of length $5$ on $\{\mathtt{H},\mathtt{T}\}$ with transitions $w_0w_1w_2w_3w_4\to w_1w_2w_3w_4\mathtt{H}$ and $w_0w_1w_2w_3w_4\to w_1w_2w_3w_4\mathtt{T}$ of equal probability from each state $w_0w_1w_2w_3w_4$. This is the $5$-bit shift register chain. The stationary distribution is uniform, so if $T_u$ denotes the first time $>0$ the shift register is in state $u:=\mathtt{HTHTH}$, we have $\mathbb{E}_u T_u=32$, where $\mathbb{E}_u$ is the expected value if the shift register is initialized with $u$.
However, you ask for $\mathbb{E}_\varnothing T_u$, where I am using $\mathbb{E}_\varnothing$ to to denote the expectation if the initial state has no overlap with $u$ (or if the shift register is empty, if you will).
Conditioning on the first two coin flips we get \begin{align} \mathbb{E}_uT_u &= \frac{1}{2}(1+\mathbb{E}_{\mathtt{H}}T_u) + \frac{1}{4}2 + \frac{1}{4}(2+\mathbb{E}_\varnothing T_u) \;. \end{align} The first term is for when the first flip comes up $\mathtt{H}$, the second for when the first two flips turn out $\mathtt{TH}$ (hence returning to $u$) and the third for if the first two flips are $\mathtt{TT}$. I am writing $\mathbb{E}_{\mathtt{H}}$ for the expectation if the initial state has the form $w_0w_1w_2w_3 \mathtt{H}$ and the only possible overlap with $u$ is with the last bit.
A similar equation can be written for $\mathbb{E}_\varnothing T_u$ by conditioning on the first flip: \begin{align} \mathbb{E}_\varnothing T_u &= \frac{1}{2}(1+\mathbb{E}_{\mathtt{H}}T_u) + \frac{1}{2}(1+\mathbb{E}_{\varnothing}T_u) \end{align}
Solving the two equations for $\mathbb{E}_\varnothing T_u$ we get \begin{align} \mathbb{E}_\varnothing T_u &= \frac{1}{3} (4\cdot \mathbb{E}_u T_u - 2) = \frac{4\times 32 - 2}{3} = 42 \;. \end{align}
However, I hesitate to call this a solution using Kac's lemma, because the proof of Kac's lemma (the elementary version) is as simple, and uses the same kind of conditioning.
