0
$\begingroup$

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.

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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)$? $\endgroup$
    – Milten
    Jun 30, 2020 at 21:03
  • $\begingroup$ @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$. $\endgroup$
    – Brian M. Scott
    Jun 30, 2020 at 21:09
  • $\begingroup$ 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... $\endgroup$
    – Milten
    Jun 30, 2020 at 21:16
  • $\begingroup$ @Milten: And that’s exactly what is happening: that assumption is built into the probabilities $\hat L_n\left(\frac12\right)^n$. $\endgroup$
    – Brian M. Scott
    Jun 30, 2020 at 21:18
  • $\begingroup$ Okay, it makes sense, thank you. I wonder when that convention is useful. $\endgroup$
    – Milten
    Jun 30, 2020 at 21:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .