\input amstex
\documentstyle{amsppt}
\magnification=\magstep1
\headline=
{\ifnum\pageno=1\hfil
\else\vbox{\line {\sl
Advancing by coin flippings
\hfil \folio}
\vskip 2pt\hrule}\fi}
\footline={\hfil}
\catcode`\@=11
\redefine\logo@{}
\firstpage@false
\catcode`\@=13
\topmatter
\title
How to advance on a stairway by coin flippings
\endtitle
\author Helmut Prodinger \endauthor
\affil
Department of Algebra and Discrete Mathematics
Technical University of Vienna, Austria
\endaffil
\address\flushpar
TU Vienna\newline
Wiedner Hauptstrasse 8-10\newline A-1040 Vienna\newline Austria
\endaddress
\abstract
Assume that $N$ players start at stair 1 and flip a fair coin to advance
one step. From the surviving people, a demon additionally kills one with
probability $1-p$, i.e. with probability $p$ he does not interfer. The average
level that such a party will reach is of interest. In this paper we show
that this quantity behaves like $\log_2N$ and give a tutorial survey
how to attack such problems. This problem is related to themes in
Theoretical Computer Sciences, namely {\sl Approximate Counting}
and {\sl Tries}.
\endabstract
\endtopmatter
\document
Assume that $N$ persons want to advance on a stairway.
The rule is as follows:
They start at level 1. The $k\ge 1$ persons who advanced to the level
$j$ flip a (fair) coin; the persons with the ``1'' advance; the others
(with a ``0'') die.
However, there is a demon supervising the game. Usually, he ``consumes''
one of the survivers. But, with a probability $p$, he resigns and
does not interfer. (The demon can only interfer at levels 2 of larger.)
The question is, how far can the party advance, on the
average?
\vskip 2cm
In this example the party gets to level 4; at one stage the demons resigns.
This recreational description has of course a serious background. If
$p=0$, the model is exactly equivalent to an algorithmic procedure called
{\sl Approximate counting\/} \cite1, as was shown in \cite 7.
If $p=1$ the resulting recurrences (see the discussion below)
resembles recurrences that are customary in the context of
{\sl tries}; see for instance the brandnew book of H.Mahmoud
\cite 5. The idea
of introducing a probability $p$ of escaping the demon is borrowed from
\cite 8; in this thesis U. Schmid studied the collision of $N$ transmitted
data. Usually they are all destroyed, but with a probability $p$ one
package survives.
In this paper we want to solve this problem. The main interest is not
so much in the actual answer that we will finally obtain; its main aim is
to give a rather tutorial introduction to the machinery that is usually
used within the context of such problems.
To simplify the notation, let, as usual, $q=1-p$. We introduce
probability generating functions $F_N(z)$. The coefficient of $z^k$
is the probability that $N$ persons came to level $k$ (and not farther).
There is a recursion relating these functions:
$$
F_N(z)=z\sum_{k=1}^N2^{-N}\binom Nk\Big[qF_{k-1}(z)+pF_k(z)\Big]
+z2^{-N},\quad N\ge 1,\ F_0(z)=z
$$
To understand it, note that $2^{-N}\binom Nk$ is the probability that
$k$ of $N$ have flipped a ``1''. With $z$ we mark a level that is already
passed. With probability $p$, $k$ people go on, with probability $q$,
only $k-1$. (If $k=1$, and the demon takes him, we nevertheless say that
the level was reached!) If $k=0$, the recursion stops.
The desired average $C_N$ may be obtained via $F'_N(1)$. By differentiation,
we get the recursion
$$
C_N=1+q\sum_{k=1}^N2^{-N}\binom NkC_{k-1}+p
\sum_{k=1}^N2^{-N}\binom NkC_{k}
,\quad N\ge 1,\ C_0=1.
$$
Now it is customary to study the exponential generating function
$$
C(z)=\sum_{N\ge 0}C_N\frac{z^N}{N!}.
$$
Multiplying the recursion by $(2z)^N/N!$ and summing up we get
$$
C(2z)=e^{2z}+pe^zC(z)-pe^z+q\sum_{N\ge 1}\frac{z^N}{N!}
\sum_{k=1}^N\binom NkC_{k-1}.
$$
To get rid of the unpleasant sum, we differentiate this equation
and consider the difference of the new and the old equation.
This gives us
$$
2C'(2z)=2e^{2z}+pe^zC(z)+pe^zC'(z)-pe^z+q\sum_{N\ge 1}\frac{z^{N-1}}{(N-1)!}
\sum_{k=1}^N\binom NkC_{k-1},
$$
or
$$
2C'(2z)-C(2z)=e^{2z}+pe^zC'(z)+qe^zC(z).
$$
Here we have used that $\binom {N+1}k-\binom Nk=\binom N{k-1}$.
The next step is the introduction of the {\sl Poisson transformed\/}
function $D(z)=e^{-z}C(z)$. Then $D'(z)+D(z)=e^{-z}C'(z)$, and
we obtain the easier equation
$$
2D'(2z)+D(2z)=1+pD'(z)+D(z).
$$
Now we consider the coefficients $D_N$ of this (exponential) generating
function. Equating the coefficients of $z^N/N!$, we find
$$
2^{N+1}D_{N+1}+2^ND_N=\delta_{N,0}+pD_{N+1}+D_N,\quad N\ge 1, D_0=1.
$$
It means $D_0=1$, $D_1=\frac{1}{2-p}$ and for $N\ge 1$
$$
\left(1-\frac{p}{2^{N+1}}\right)D_{N+1}
=-\frac 12\left(1-\frac{p}{2^{N}}\right)D_{N}.
$$
We rewrite it as
$$
D_N=-\frac 12D_{N-1}\frac{1-\frac{1}{2^{N-1}}}{1-\frac{p}{2^N}}
$$
and iterate it to get
$$
D_N=\frac{1}{2-p}(-1)^{N-1}2^{1-N}\frac{Q_{N-1}}{Q_{N-1}(\frac p2)},
\quad N\ge 1.
$$
Here,
$$
Q_m(a)=\left(1-\frac{a}{2}\right)\left(1-\frac{a}{2^{2}}\right)
\dots\left(1-\frac{a}{2^{m}}\right)
$$
and $Q_m=Q_m(1)$.
Since $C(z)=e^zD(z)$, we have
$$
\align
C_N&=\sum_{k=0}^N\binom NkD_k\\
&=1+\frac{1}{2-p}\sum_{k=1}^N\binom Nk
(-1)^{k-1}2^{1-k}\frac{Q_{k-1}}{Q_{k-1}(\frac p2)}\\
&=1-\frac{1}{2-p}\sum_{k=1}^N\binom Nk
(-1)^{k}f(k)
\endalign
$$
with
$$
f(k)=2^{1-k}\frac{Q_{k-1}}{Q_{k-1}(\frac p2)}.
$$
The method to evaluate such an alternating sum is called {\sl
Rice's method\/}, \cite 2, \cite 4, \cite 5, \cite 6 .
\bigskip
\proclaim{Lemma }
Let $\Cal C$ be a curve surrounding the points $1,2,\dots,N$
in the complex plane and let $f(z)$ be analytic inside $\Cal C$. Then
$$
\sum_{k=1}^N \binom Nk \, {(-1)}^k f(k)=
-\frac 1{2\pi i} \int_{\Cal C} [N;z] f(z) dz,
$$
where
$$
[N;z]=\frac{(-1)^{N-1} N!}{z(z-1)\dots(z-N)}=
\frac{\Gamma(N+1)\Gamma(-z)}{\Gamma(N+1-z)}.\qed
$$
\endproclaim
Extending the contour of integration it turns out that
under suitable growth conditions on $f(z)$ (compare \cite8)
the asymptotic expansion
of the alternating sum is given by
$$
\sum \text {Res} \big( [N;z] f(z)\big)+\text{smaller order terms}
$$
where the sum is taken over all poles $z_0$
different from $1,\dots,N$.
\bigskip
Thus we must find a complex function $f(z)$, such that $f(k)$ are the
numbers $2^{1-k}\frac{Q_{k-1}}{Q_{k-1}(\frac p2)}$.
For this task it is convenient to introduce the infinite product
$$
Q(x)=\big(1-\frac x2\big)\big(1-\frac x4\big)\big(1-\frac x8\big)\cdots.
$$
Then it is easy to see that
$$
Q_m=\frac{Q(1)}{Q(2^{-m})},
$$
and, more generally,
$$
Q_m(a)=\frac{Q(a)}{Q(a2^{-m})}.
$$
It makes sense to replace $m$ in the last equality by a complex
variable $z$. Now we have to consider the residues of
$$
[N;z]2^{1-z}\frac{Q_{z-1}}{Q_{z-1}(\frac p2)}
$$
at $z=0$ and then also at $z=2k\pi i/L$, were we set here and later
$L=\log2$. Also, the notion $\chi_k=2k\pi i/L$ is very useful.
The meaning of $Q_{z-1}$ etc. is as it was just described.
Let's start as follows:
$$
Q_{z-1}=\frac{Q(1)}{Q(2^{1-z})}=
\frac{1}{1-2^{-z}}\cdot\frac{Q(1)}{Q(2^{-z})}.
$$
Now
$$
1-2^{-z}=1-e^{-Lz}\sim 1-\left(1-Lz+\frac{L^2z^2}{2}\mp\dots\right)
\sim Lz\left(1-\frac{Lz}{2}\right)
$$
and thus
$$
\frac{1}{1-2^{-z}}\sim\frac{1}{Lz}\left(1+\frac{Lz}{2}\right).
$$
Furthermore,
$$
Q(2^{-z})\sim Q(1)+Q'(1)\cdot(-L)\cdot z,
$$
and
$$
Q'(x)=-Q(x)\cdot \sum_{k\ge 1}\frac{1}{2^k-x},
$$
so that
$$
Q(2^{-z})\sim Q(1)\cdot (1+Lz\alpha),
$$
where we use the abbreviation
$$
\alpha=\sum_{k\ge1 }\frac{1}{2^k-1}.
$$
Alltogether we find
$$
Q_{z-1}\sim \frac{1}{Lz}\left(1+\frac{Lz}{2}\right)(1-Lz\alpha).
$$
The computations for $Q_{z-1}(\frac p2)$ are entirely similar, so that
we just mention the result:
$$
Q_{z-1}(\frac p2)\sim \frac{1}{1-\frac p2}\cdot
\big(1-p\alpha(p)Lz\big)
$$
with
$$
\alpha(p)=\sum_{k\ge1}\frac{1}{2^k-p}.
$$
We need one more local expansion:
$$
[N;z]\sim -\frac 1z\big(1+zH_N\big),
$$
with the $N$-th {\sl harmonic number}
$$
H_N=1+\frac 12+\frac 13+\cdots+\frac 1N\sim \log N+\gamma+\dots\ .
$$
Plugging things together we have
$$
\align
f(z)&\sim 2\big(1-{Lz}\big)\frac{1}{Lz}
\left(1+\frac{Lz}{2}\right)(1-Lz\alpha)
\big({1-\frac p2}\big)
\big(1+p\alpha(p)Lz\big)\\
&\sim \frac{2-p}{Lz}\Big(1+z\big(-\frac L2-\alpha L+p\alpha(p)L\big)\Big).
\endalign
$$
Therefore the residue of $[N;z]f(z)$ at $z=0$ is
$$
-\frac{2-p}{L}\Big(H_N-\frac L2-\alpha L+p\alpha(p)L\Big).
$$
We can use the asymptotics for $H_N$ and then go back to the formula
for the average $C_N$ and get the main contribution
$$
1-\frac{1}{2-p}\cdot\bigg(
-\frac{2-p}{L}\Big(\log N+\gamma-\frac L2-\alpha L+p\alpha(p)L\Big)
\bigg).
$$
This readily simplifies to
$$
\log_2N+\frac{\gamma}{L}+\frac 12 -\alpha+p\alpha(p).
$$
From this we can easily see the dependency of $p$ as $p$ varies between
0 and 1. As was to be expected, this quantity increases monotonically
and for $p=1$ the $\alpha$-terms disappear.
Now we have to turn to the residues $z=\chi_k$. This time it is easier
because there is only a single pole, originating from $Q_{z-1}$. We list
the local expansions of the factors of
$$ f(z)=2^{1-z}\frac{Q_{z-1}}{Q_{z-1}\big(\frac p2\big)}:
$$
$$
\align
2^{1-z}&\sim 2\\
Q_{z-1}&\sim\frac{1}{Lz}\\
\frac{1}{Q_{z-1}\big(\frac p2\big)}&\sim \frac{Q(p)}{Q\big(\frac p2\big)}
=1-\frac p2\\
[N;z]&\sim N^{\chi_k}\cdot \Gamma(- \chi_k)
\endalign
$$
Here, we used the well-known fact that
$$
\frac{\Gamma(N+a)}{\Gamma(N+b)}\to N^{a-b}.
$$
The residue of $[N;z]f(z)$ at $z=\chi_k$ is thus
$$
2\cdot \frac{1}{L}\cdot\left(1-\frac p2\right)\cdot
N^{\chi_k} \Gamma(- \chi_k)=(2-p)\frac 1L
\Gamma(- \chi_k)N^{\chi_k}.
$$
It is now customary to collect all these contributions for $k\in\Bbb Z$,
$k\ne 0$ in {\sl one\/} function $\delta(x)$. Set
$$
\delta(x)=\frac 1L\sum_{k\ne 0} \Gamma(- \chi_k)e^{2k\pi i\cdot x},
$$
then the periodic quantity of our desired quantity $C_N$ is
(don't forget the factor $-\frac{1}{2-p}$)
$$
-\delta\big(\log_2N\big).
$$
Observe that this quantity is independent of $p$. However, in the smaller
order terms, the parameter $p$ appears.
We summarize our results as follows:
\proclaim{Theorem} Let $C_N$ be the average level that a random party
of $N$ people can reach in presence of a demon (as descibed in the
Introduction). Then we have the following asymptotic formula
$$
C_N\sim
\log_2N+\frac{\gamma}{L}+\frac 12 -\alpha+p\alpha(p)-\delta\big(\log_2N\big)
$$
where
$$
\alpha(p)=\sum_{k\ge 1}\frac{1}{2^k-p}, \quad \alpha=\alpha(1)
$$
and
$$
\delta(x)=\frac 1L\sum_{k\ne 0} \Gamma(- \chi_k)e^{2k\pi i\cdot x}
$$
is a periodic function of period 1, mean 0 and small amplitude ($\approx
10^{-6}$). It is given as a Fourier series.
\endproclaim
\Refs
\ref \no 1 \by P. Flajolet \pages 113--\-134 \paper Approximate Counting:
A Detailed Analysis \yr 1985 \vol 25 \jour BIT \endref
\ref \no 2 \by P. Flajolet and R. Sedgewick\paper Digital Search
Trees Revisited \jour SIAM J. Comput. \vol 15 \yr 1986 \pages 748--767
\endref
\ref \no 3 \by P. Kirschenhofer and H. Prodinger\paper Approximate
Counting: An Alternative Approach \jour RAIRO Informatique Th\'eorique
et Applications \vol 25 \yr 1991 \pages 43--48 \endref
\ref \no 4 \by D.E. Knuth \book The Art of Computer Science Vol.3\publ
Addison-Wesley \yr 1973 \publaddr Reading, MA \endref
\ref \no 5 \by H. M. Mahmoud \book Evolution of Random Search Trees
\publ Wiley-Interscience Series in Discrete Mathematics and Optimization
\publaddr New York \yr 1992
\endref
\ref \no 6 \by N. E. N\"orlund \book Vorlesungen \"uber Differenzenrechnung
\publ Chelsea \yr 1954 \publaddr New York \endref
\ref \no 7 \by H. Prodinger\paper Hypothetic Analyses: Approximate
Counting in the Style of Knuth, Path length
in the Style of Flajolet \jour Theoret. Comput. Sci. \toappear
\endref
\ref \no 8 \by U. Schmid \book Analyse von Collision-Resolution Algorithmen
in Random-Access Systemen mit dominanten \"Ubertragungskan\"alen
\publ Dissertation, TU Wien \yr 1986
\endref
\endRefs
\enddocument