# Expected waiting time in strings given by derivative of Generating Function

This is exercise I.33 from Analytic Combinatorics by Flajolet & Sedgewick, with the important bit in bold:

Waiting times in strings. Let $$\mathcal L \subset \mathrm{SEQ}\{a, b\}$$ be a language and $$S = \{a, b\}^\infty$$ be the set of infinite strings with the product probability induced by $$P(a) = P(b) = \frac12$$. The probability that a random string $$\omega \in S$$ starts with a word of $$\mathcal L$$ is $$\hat L(1/2)$$, where $$\hat L(z)$$ is the OGF of the "prefix language" of $$\mathcal L$$, that is, the set of words $$w \in \mathcal L$$ that have no strict prefix belonging to $$\mathcal L$$. The GF $$\hat L(z)$$ serves to express the expected time at which a word in $$\mathcal L$$ is first encountered: this is $$\frac12 \hat {L'} (\frac 12)$$. For a regular language, this quantity must be a rational number.

($$\mathrm{SEQ}\{a, b\}$$ is the set of all words over $$\{a,b\}$$, OGF and GF stand for (ordinary) gernarating function.) I can understand the first part: $$\omega$$ starts with a word in $$\mathcal L$$ iff it starts with a word in the prefix language $$\hat{\mathcal L}$$. Since the events in the sum below are disjoint by construction of $$\hat{\mathcal L}$$, the probability is $$\sum_{n=1}^\infty P(\textrm{\omega starts with w\in\hat{\mathcal L}, |w|=n}) = \sum_{n=1}^\infty \hat L_n \left(\frac 12\right)^n = \hat L\left(\frac12\right)$$ where $$\hat L_n = \#\{w\in\hat {\mathcal L}\mid |w|=n\}$$ are the coefficients of the generating function $$\hat L(z)$$.

But I am at a loss about the bolded part. We can write $$\frac12 \hat {L'} \left(\frac 12\right) = \sum_{n=1}^\infty n \hat L_n \left(\frac 12\right)^n$$ But I don't see how the claim can be right. Consider the simple case $$\mathcal L = \{a\}$$. Then $$\hat L(z) = z$$, so $$\frac12 \hat {L'} \left(\frac 12\right) = \frac12$$. But the first occurrence of $$w=a$$ should follow a geometric distribution with success probability $$\frac12$$, so the expected time should be $$2$$. More generally, the expected first occurrence of a given word $$w$$ of length $$k$$ should be given $$2^k c(1/2)$$, where $$c(z)$$ is the autocorrelation polynomial of $$w$$, but the expression $$\frac12 \hat {L'} \left(\frac 12\right)$$ does not depend on the autocorrelation at all.

Clearly I am missing or misinterpreting something here. Any help?

Note: The authors did define another GF $$L(z)$$ shortly above the exercise. It is the OGF for words containing a given pattern of length $$k$$, which on a binary alphabet is $$L(z) = \frac{z^k}{(1-2z)(z^k+(1-2z)c(z))}$$ But I don't think this has anything to do with the exercise. For one thing, it has a pole at $$z=1/2$$, so we couldn't even insert $$1/2$$ if we wanted to.

If makes sense once you realize that they’re talking about the expected time at which the initial segment of $$\omega$$ read so far is in $$\mathcal{L}$$. This is clear from the expression
$$\sum_{n\ge 1}n\hat L_n\left(\frac12\right)^n\;:$$
$$\hat L_n\left(\frac12\right)^n$$ is the probability that $$\omega$$ starts with an irreducible prefix of length $$n$$, and we’re multiplying it by the length, so we’re getting the expected length of the first irreducible prefix in $$\omega$$ and hence of the first member of $$\mathcal{L}$$ encountered.
• Is that under the assumption that $P(\omega \textrm{ starts with a word of }\mathcal L) = 1$? If there is a positive probability that $\omega$ does not start with a word of $\mathcal L$, then the expected time you describe should be $\infty$, or maybe undefined, right? Is it perhaps the conditional expectation $E(\textrm{waiting time} \mid \omega \textrm{ starts with a word of }\mathcal L)$? Jun 30, 2020 at 21:03
• @Milten: Isn’t it just the usual definition of expected value? In your example, for instance, all of the probabilities are $0$ except the $\frac12$ for $n=1$, so the usual definition does yield an expected value of $\frac12$. Jun 30, 2020 at 21:09
• If an expected value of $1/2$ is to make sense, it must mean that the case where [$\omega$ does not start with a word of $\mathcal L$] is counted with a value of $0$. I.e. let $X = \begin{cases}\textrm{waiting time} & \textrm{if$\omega$starts with a word of$\mathcal L$} \\ 0 & \textrm{otherwise} \end{cases}$. Then $E[X] = \frac12 \hat {L'}(\frac12)$. That would make it all work out, but it's a little counterintuitive to me... Jun 30, 2020 at 21:16
• @Milten: And that’s exactly what is happening: that assumption is built into the probabilities $\hat L_n\left(\frac12\right)^n$. Jun 30, 2020 at 21:18