chap8.tex

Concrete_Mathematics_2nd_Ed_TeX_Source_Code

Thus $F(z)$ is formally a binomial that corresponds to a coin for which
we get heads with ``probability'' equal to $-q/p$; and $G(z)$ is formally
\g The probability is negative that I'm getting younger.
\medskip Oh? Then it's ${>}\,1$ that you're getting older, or
staying the~same.\g
equivalent to flipping such a coin $-1$ times\kern1pt(!).
The negative binomial distribution
with parameters $(n,p)$ can therefore be regarded as the ordinary
binomial distribution with parameters $(n',p')=(-n,-q/p)$. Proceeding
formally, the mean must be $n'p'=(-n)(-q/p)=nq/p$, and the variance must
be $n'p'q'=(-n)(-q/p)(1+q/p)=nq/p^2$. This formal derivation involving
negative probabilities is valid, because our derivation for ordinary
binomials was based on identities between formal power series in which
the assumption $0\le p\le1$ was never used.

\unitlength=3pt
\def\domi{\beginpicture(0,2)(0,0) % identity
	\put(0,0){\line(0,1){2}}
	\endpicture}
\def\domv{\beginpicture(1,2)(0,0) % vertical without left edge
	\put(1,0){\line(0,1){2}}
	\put(0,0){\line(1,0){1}}
	\put(0,2){\line(1,0){1}}
	\endpicture}
\def\domhh{\beginpicture(2,2)(0,0) % two horizontals without left edge
	\put(2,0){\line(0,1){2}}
	\put(0,0){\line(1,0){2}}
	\put(0,1){\line(1,0){2}}
	\put(0,2){\line(1,0){2}}
	\endpicture}

\smallbreak
Let's move on to another example: How many times do we have to flip
a coin until we get heads twice in a row? The probability space now
consists of all sequences of $\tt H$'s and $\tt T$'s that end
with $\tt HH$ but have no consecutive $\tt H$'s until the final position:
\begindisplay
\Omega=\tt\{@ HH,THH,TTHH,HTHH,TTTHH,THTHH,HTTHH,\ldots\,\}\,.
\enddisplay
The probability of any given sequence is obtained by replacing $\tt H$
by $p$ and $\tt T$ by~$q$; for example, the sequence $\tt THTHH$
will occur with probability
\begindisplay
\Pr(@{\tt THTHH}@)=qpqpp=p^3q^2\,.
\enddisplay

We can now play with generating functions as we did at the beginning
of Chapter~7, letting $S$ be the infinite sum
\begindisplay
S=\tt  HH+THH+TTHH+HTHH+TTTHH+THTHH+HTTHH+\cdots
\enddisplay
of all the elements of $\Omega$. If we replace each $\tt H$ by $pz$
and each $\tt T$ by $qz$, we get the probability generating function
for the number of flips needed until two consecutive heads turn up.

There's a curious relation between $S$ and the sum of domino tilings
\begindisplay \postdisplaypenalty=1000
T	= \domi+
 \domi\domv+\domi\domv\domv + \domi\domhh
 + \domi\domv\domv\domv + \domi\domv\domhh + \domi\domhh\domv
 + \cdots
\enddisplay
in equation \equ(7.|t-sum|). Indeed, we obtain $S$ from $T$ if we
replace each $\domi\domv$ by $\tt T$ and each $\domi\domhh$ by $\tt HT$,
then tack on an $\tt HH$ at the end. This correspondence is easy
to prove because each element of~$\Omega$ has the form $({\tt T+HT})^n
\tt HH$ for some $n\ge0$, and each term of~$T$ has the
form $(@\domi\domv+\domi\domhh@)^n$.
Therefore by \equ(7.|t-fraction|) we have
\begindisplay
S=(1-{\tt T-HT})^{-1}{\tt HH}\,,
\enddisplay
and the probability generating function for our problem is
\begindisplay \openup6pt
G(z)&=\bigl(1-qz-(pz)(qz)\bigr)^{\!-1}(pz)^2\cr
&={p^2z^2\over1-qz-pqz^2}\,.
\eqno
\enddisplay

Our experience with the negative binomial distribution gives us a clue
that we can most easily calculate the mean and
variance of \thiseq\ by writing
\begindisplay
G(z)={z^2\over F(z)}\,,
\enddisplay
where
\begindisplay
F(z)={1-qz-pqz^2\over p^2}\,,
\enddisplay
and by calculating the ``mean'' and ``variance'' of this pseudo-pgf\/ $F(z)$.
(Once again we've introduced a function with $F(1)=1$.)
We have
\begindisplay
F'(1)&=(-q-2pq)/p^2=2-p^{-1}-p^{-2}\,;\cr
F''(1)&=-2pq/p^2=2-2p^{-1}\,.\cr
\enddisplay
Therefore, since $z^2=F(z)@G(z)$, \ $\Mean(z^2)=2$, and
$\Var(z^2)=0$, the mean and variance of distribution $G(z)$ are
\begindisplay
\Mean(G)&=2-\Mean(F)&=p^{-2}+p^{-1}\,;\eqno\cr
\Var(G)&=-\Var(F)&=p^{-4}+2p^{-3}-2p^{-2}-p^{-1}\,.\eqno\cr
\enddisplay
When $p=\half$ the mean and variance are $6$ and~$22$, respectively.
(Exercise~|divide-gfs| discusses the calculation of means and variances
by subtraction.)

%\smallbreak
\goodbreak
Now let's try a more intricate experiment: We will flip coins until the
pattern {\tt THTTH} is first obtained. The sum of winning positions
is now
\begindisplay
S&=\tt THTTH+HTHTTH+TTHTTH\cr
&\qquad\tt+HHTHTTH+HTTHTTH+THTHTTH+TTTHTTH+\cdots\,;
\enddisplay
this sum is more difficult to describe than the previous one. If we go
back to the method by which we solved the domino problems in Chapter~7,
we can obtain a formula for~$S$ by considering it as a ``"finite state
language"'' defined by the following ``"automaton"'':
\g\noindent\llap{``}\thinspace`You really are an automaton\dash---a calculating
machine,' I cried. `There is something positively inhuman in you at
times.'\thinspace''\par\hfill\dash---J.\thinspace H.
 "Watson"~[|holmes-four|]\g % chap2
\begindisplay
\unitlength=4pt
\beginpicture(60,10.5)(-8,-8.5)
\multiput(0,0)(10,0)6{\circle4}
\multiput(-8,0)(10,0)6{\vector(1,0)6}
\put(0,.1){\makebox(0,0){$0$}}
\put(10,.1){\makebox(0,0){$1$}}
\put(20,.1){\makebox(0,0){$2$}}
\put(30,.1){\makebox(0,0){$3$}}
\put(40,.1){\makebox(0,0){$4$}}
\put(50,.1){\makebox(0,0){$5$}}
\put(3.25,1.75){\makebox(0,0){\tt T}}
\put(13.25,1.75){\makebox(0,0){\tt H}}
\put(23.25,1.75){\makebox(0,0){\tt T}}
\put(33.25,1.75){\makebox(0,0){\tt T}}
\put(43.25,1.75){\makebox(0,0){\tt H}}
\put(1.5,-3.5){\makebox(0,0){\tt H}}
\put(11.5,-3.5){\makebox(0,0){\tt T}}
\put(21.5,-3.5){\makebox(0,0){\tt H}}
\put(31.5,-3.5){\makebox(0,0){\tt H}}
\put(41.5,-3.5){\makebox(0,0){\tt T}}
\ovaltlfalse
\ovaltrfalse
\put(-2,-2){\oval(4,8)}
\put(8,-2){\oval(4,8)}
\put(7.5,-5){\oval(25,4)}
\put(23,-3.5){\oval(14,4)}
\put(22.5,-6.5){\oval(35,4)}
\put(-5,-5){\vector(0,1)5}
\put(-4,-2){\vector(0,1)2}
\put(5,-6.5){\vector(0,1){6.5}}
\put(6,-2){\vector(0,1)2}
\put(16,-3.5){\vector(0,1){3.5}}
\put(20,-5){\line(0,1)3}
\put(30,-3.5){\line(0,1){1.5}}
\put(40,-6.5){\line(0,1){4.5}}
\endpicture
\enddisplay
The elementary events in the probability space are the sequences of
$\tt H$'s and $\tt T$'s that lead from state~$0$ to state~$5$. Suppose,
for example, that we have just seen {\tt THT}; then we are in state~$3$.
Flipping tails now takes us to state~$4$; flipping heads in state~$3$
would take us to
state~$2$ (not all the way back to state~$0$, since the {\tt TH} we've
just seen may be followed by {\tt TTH}).

In this formulation, we can let $S_k$ be the sum of all sequences
of {\tt H}'s and {\tt T}'s that lead to state~$k$; it follows that
\begindisplay   \openup3pt
S_0&=1+S_0\,{\tt H}+S_2\,{\tt H}\,,\cr
S_1&=S_0\,{\tt T}+S_1\,{\tt T}+S_4\,{\tt T}\,,\cr
S_2&=S_1\,{\tt H}+S_3\,{\tt H}\,,\cr
S_3&=S_2\,{\tt T}\,,\cr
S_4&=S_3\,{\tt T}\,,\cr
S_5&=S_4\,{\tt H}\,.\cr
\enddisplay
Now the sum $S$ in our problem is $S_5$; we can obtain it by solving
these six equations in the six unknowns $S_0$, $S_1$, \dots,~$S_5$.
Replacing $\tt H$ by~$pz$ and $\tt T$ by~$qz$ gives generating
functions where the coefficient of~$z^n$ in~$S_k$ is the probability
that we are in state~$k$ after $n$ flips.

In the same way, any diagram of transitions between states, where the
transition from state~$j$ to state~$k$ occurs with given probability~$p_{j,k}$,
leads to a set of simultaneous linear equations whose solutions are
generating functions for the state probabilities after $n$~transitions
have occurred. Systems of this kind are called {\it "Markov processes"},
and the theory of their behavior is intimately related to the theory
of linear equations.

But the coin-flipping problem can be solved in a much simpler way,
without the complexities of the general finite-state approach. Instead
of six equations in six unknowns $S_0$, $S_1$, \dots,~$S_5$, we can
characterize~$S$ with only two equations in two unknowns. The trick is
to consider the auxiliary sum $N=S_0+S_1+S_2+S_3+S_4$ of all flip
sequences that don't contain any occurrences of the given pattern
{\tt THTTH}:
\begindisplay
N=1+\tt H+T+HH+\cdots+THTHT+THTTT+\cdots\,.
\enddisplay
We have
\begindisplay
1+N(@{\tt H+T}@)=N+S\,,
\eqno\eqref|thtth-1|
\enddisplay
\looseness=-1
because every term on the left either ends with $\tt THTTH$ (and
belongs to~$S$) or doesn't (and belongs to~$N$); conversely, every
term on the right is either empty or belongs to $N\,\tt H$
or~$N\,\tt T$. And we also have the important additional equation
\begindisplay
N\,{\tt THTTH}=S+S\,{\tt TTH}\,,
\eqno\eqref|thtth-2|
\enddisplay
because every term on the left completes a term of~$S$ after either
the first~$\tt H$ or the second~$\tt H$, and because every 
term on the right belongs to the left.

The solution to these two simultaneous equations is easily obtained:
We have $N=(1-S)(1-{\tt H}-{\tt T})^{-1}$ from~\eq(|thtth-1|), hence
\begindisplay
(1-S)(1-{\tt T}-{\tt H})^{-1}\,{\tt THTTH}=S(1+{\tt TTH})\,.
\enddisplay
As before, we get the probability generating function $G(z)$ for
the number of flips if we replace $\tt H$ by~$pz$ and $\tt T$ by~$qz$.
A bit of simplification occurs since $p+q=1$, and we find
\begindisplay
{\bigl(1-G(z)\bigr)\,p^2q^3z^5\over1-z}=G(z)(1+pq^2z^3)\,;
\enddisplay
hence the solution is
\begindisplay
G(z)={p^2q^3z^5\over p^2q^3z^5+(1+pq^2z^3)(1-z)}\,.
\eqno
\enddisplay
Notice that $G(1)=1$, if $pq\ne0$; we do eventually encounter the
pattern $\tt THTTH$, with probability~$1$, unless the coin is rigged
so that it always comes up heads or always tails.

To get the mean and variance of the distribution \thiseq, we invert
$G(z)$ as we did in the previous problem, writing $G(z)=z^5\!/F(z)$
where $F$~is a polynomial:
\begindisplay
F(z)={p^2q^3z^5+(1+pq^2z^3)(1-z)\over p^2q^3}\,.
\eqno
\enddisplay
The relevant derivatives are
\begindisplay
F'(1)&=5-(1+pq^2)/p^2q^3\,,\cr
F''(1)&=20-6pq^2\!/p^2q^3\,;
\enddisplay
and if $X$ is the number of flips we get
\begindisplay
EX&=\Mean(G)=5-\Mean(F)=p^{-2}q^{-3}+p^{-1}q^{-1}\,;}\hidewidth{
 \eqno\eqref|thtth-e|\cr
VX&=\Var(G)&=-\Var(F)\cr
&&=-25+p^{-2}q^{-3}+7p^{-1}q^{-1}+\Mean(F)^2\cr
&&=(EX)^2-9p^{-2}q^{-3}-3p^{-1}q^{-1}\,.\eqno\eqref|thtth-v|
\enddisplay
When $p=\half$, the mean and variance are $36$ and $996$.

\smallbreak
Let's get general: The problem we have just solved was ``random'' enough
to show us how to analyze the case that we are waiting for the first
appearance of an
{\it arbitrary\/} pattern $A$ of heads and tails. Again we let $S$
be the sum of all winning sequences of $\tt H$'s and $\tt T$'s, and
we let~$N$ be the sum of all sequences that haven't encountered 
the pattern $A$~yet.
Equation \eq(|thtth-1|) will remain the same; equation \eq(|thtth-2|)
will become
\begindisplay \openup4pt
NA&=S\bigl(1+A^{(1)}\,\[A^{(m-1)}=A_{(m-1)}]+
A^{(2)}\,\[A^{(m-2)}=A_{(m-2)}]\cr
&\hskip7em+\cdots+
A^{(m-1)}\,\[A^{(1)}=A_{(1)}]\bigr)\,,
\eqno\eqref|general-solitaire|
\enddisplay
where $m$ is the length of~$A$, and where $A^{(k)}$ and $A_{(k)}$ denote
respectively
the last~$k$ characters and the first~$k$ characters of~$A$.
For example, if $A$ is the pattern $\tt THTTH$ we just studied, we have
\begindisplay
&A^{(1)}=\tt H\,,\quad&A^{(2)}=\tt TH\,,\quad&A^{(3)}=\tt TTH\,,\quad
 &A^{(4)}=\tt HTTH\,;\cr
&A_{(1)}=\tt T\,,\quad&A_{(2)}=\tt TH\,,\quad&A_{(3)}=\tt THT\,,\quad
 &A_{(4)}=\tt THTT\,.\cr
\enddisplay
Since the only perfect match is $A^{(2)}=A_{(2)}$, equation \thiseq\
reduces to~\eq(|thtth-2|).

Let $\widetilde A$ be the result of substituting $p^{-1}$ for $\tt H$
and $q^{-1}$ for~$\tt T$ in the pattern~$A$. Then it is not difficult to
generalize our derivation of \eq(|thtth-e|) and \eq(|thtth-v|) to
conclude (exercise~|prove-aflips|) that the general mean and variance are
\begindisplay \openup3pt
EX&=\sum_{k=1}^m{\widetilde A}_{(k)}\,\[A^{(k)}=A_{(k)}]\,;\eqno\eqref|aflip-e|\cr
VX&=(EX)^2-\sum_{k=1}^m\,(2k-1){\widetilde A}_{(k)}\,\[A^{(k)}=A_{(k)}]\,.
\eqno\eqref|aflip-v|\cr
\enddisplay

In the special case $p=\half$ we can interpret these formulas in a particularly
simple way. Given a pattern~$A$ of $m$~heads and tails, let
\begindisplay
A{:}A=\sum_{k=1}^m2^{k-1}\,\[A^{(k)}=A_{(k)}]\,.
\eqno\eqref|a:a|
\enddisplay
We can easily find the binary representation of this number by placing
a `$1$' under each position such that the string matches itself perfectly
when it is superimposed on a copy of itself that has been shifted to
start in this position:
\def\chek{\rlap{$\qquad\scriptstyle\sqrt{\vphantom2}$}}
\begindisplay \def\preamble{\hfill$##$&${}##$\hfi