HOW TO ADVANCE ON A STAIRWAY BY COIN FLIPPINGS

Helmut Prodinger

Department of Algebra and Discrete Mathematics Technical University of Vienna, Austria

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_{2} N and give a tutorial survey how to attack such problems. This problem is related to themes in Theoretical Computer Sciences, namely Approximate Counting and Tries.

Assume that N persons want to advance on a stairway. The rule is as follows: They start at level 1. The k ≥ 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?

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 Approximate counting [1], as was shown in [7]. If p = 1 the resulting recurrences (see the discussion below) resembles recurrences that are customary in the context of tries; see for instance the brandnew book of H.Mahmoud [5]. The idea of introducing a probability p of escaping the demon is borrowed from [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 ∑_{k=1}^{N} 2^{−N} \binom{N}{k}[qF_{k−1}(z) + pF_{k}(z)] + z2^{−N}, N ≥ 1, F_{0}(z) = z

To understand it, note that 2^{−N} \binom{N}{k} 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 ∑_{k=1}^{N} 2^{−N} \binom{N}{k}C_{k−1} + p ∑_{k=1}^{N} 2^{−N} \binom{N}{k}C_{k}, N ≥ 1, C_{0} = 1.

Now it is customary to study the exponential generating function

C(z) = ∑_{N≥0} C_{N} \frac{z^{N}}{N!} .

Multiplying the recursion by (2z)^{N}/N! and summing up we get

C(2z) = e^{2z} + pe^{z}C(z) − pe^{z} + q ∑_{N≥1} \frac{z^{N}}{N!} ∑_{k=1}^{N} \binom{N}{k}C_{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^{z}C(z) + pe^{z}C′(z) − pe^{z} + q ∑_{N≥1} \frac{z^{N−1}}{(N − 1)!} ∑_{k=1}^{N} \binom{N}{k}C_{k−1},

or

2C′(2z) − C(2z) = e^{2z} + pe^{z}C′(z) + qe^{z}C(z).

Here we have used that \binom{N+1}{k} − \binom{N}{k} = \binom{N}{k−1}. The next step is the introduction of the 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^{N}D_{N} = δ_{N,0} + pD_{N+1} + D_{N}, N ≥ 1, D_{0} = 1.

It means D_{0} = 1, D_{1} = \frac{1}{2−p} and for N ≥ 1

(1 − \frac{p}{2^{N+1}} ) D_{N+1} = −\frac{1}{2} (1 − \frac{p}{2^{N}} ) D_{N}.

We rewrite it as

D_{N} = −\frac{1}{2}D_{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{p}{2})}, N ≥ 1.

Here,

Q_{m}(a) = (1 − \frac{a}{2}) (1 − \frac{a}{2^{2}} ) … (1 − \frac{a}{2^{m}} )

and Q_{m} = Q_{m}(1). Since C(z) = e^{z}D(z), we have

C_{N} = ∑_{k=0}^{N} \binom{N}{k}D_{k}

= 1 + \frac{1}{2 − p} ∑_{k=1}^{N} \binom{N}{k}(−1)^{k−1}2^{1−k} \frac{Q_{k−1}}{Q_{k−1}(\frac{p}{2})}

= 1 − \frac{1}{2 − p} ∑_{k=1}^{N} \binom{N}{k}(−1)^{k}f(k)

with

f(k) = 2^{1−k} \frac{Q_{k−1}}{Q_{k−1}(\frac{p}{2})}.

The method to evaluate such an alternating sum is called Rice’s method, [2], [4], [5], [6] .

Lemma. Let C be a curve surrounding the points 1, 2, …, N in the complex plane and let f(z) be analytic inside C. Then

∑_{k=1}^{N} \binom{N}{k} (−1)^{k}f(k) = −\frac{1}{2πi} ∫_{C}[N; z]f(z)dz,

where

[N; z] = \frac{(−1)^{N−1}N!}{z(z − 1) … (z − N)} = \frac{Γ(N + 1)Γ(−z)}{Γ(N + 1 − z)}. □

Extending the contour of integration it turns out that under suitable growth conditions on f(z) (compare [8]) the asymptotic expansion of the alternating sum is given by

∑ Res([N; z]f(z)) + smaller order terms where the sum is taken over all poles z_{0} different from 1, …, N.

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{p}{2} )}. For this task it is convenient to introduce the infinite product

Q(x) = (1 − \frac{x}{2})(1 − \frac{x}{4})(1 − \frac{x}{8}) · · · .

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{p}{2})}

at z = 0 and then also at z = 2kπi/L, were we set here and later L = log 2. Also, the notion χ_{k} = 2kπ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}} · \frac{Q(1)}{Q(2^{−z})}.

Now

1 − 2^{−z} = 1 − e^{−Lz} ∼ 1 − (1 − Lz + \frac{L^{2}z^{2}}{2} ∓ …) ∼ Lz (1 − \frac{Lz}{2} )

and thus

\frac{1}{1 − 2^{−z}} ∼ \frac{1}{Lz} (1 + \frac{Lz}{2} ) .

Furthermore,

Q(2^{−z}) ∼ Q(1) + Q′(1) · (−L) · z,

and

Q′(x) = −Q(x) · ∑_{k≥1} \frac{1}{2^{k} − x},

so that

Q(2^{−z}) ∼ Q(1) · (1 + Lzα),

where we use the abbreviation

α = ∑_{k≥1} \frac{1}{2^{k} − 1}.

Alltogether we find

Q_{z−1} ∼ \frac{1}{Lz} (1 + \frac{Lz}{2} ) (1 − Lzα).

The computations for Q_{z−1}(\frac{p}{2}) are entirely similar, so that we just mention the result:

Q_{z−1}(\frac{p}{2}) ∼ \frac{1}{1 − \frac{p}{2}} · (1 − pα(p)Lz)

with

α(p) = ∑_{k≥1} \frac{1}{2^{k} − p}.

We need one more local expansion:

[N; z] ∼ −\frac{1}{z}(1 + zH_{N}),

with the N-th harmonic number

H_{N} = 1 + \frac{1}{2} + \frac{1}{3} + ⋯ + \frac{1}{N} ∼ log N + γ + ….

Plugging things together we have

f(z) ∼ 2(1 − Lz)\frac{1}{Lz} (1 + \frac{Lz}{2} ) (1 − Lzα)(1 − \frac{p}{2})(1 + pα(p)Lz)

∼ \frac{2 − p}{Lz}(1 + z( − \frac{L}{2} − αL + pα(p)L)).

Therefore the residue of [N; z]f(z) at z = 0 is

−\frac{2 − p}{L}(H_{N} − \frac{L}{2} − αL + pα(p)L).

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} · ( − \frac{2 − p}{L}( log N + γ − \frac{L}{2} − αL + pα(p)L)).

This readily simplifies to

log_{2} N + \frac{γ}{L} + \frac{1}{2} − α + pα(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 α-terms disappear.

Now we have to turn to the residues z = χ_{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}(\frac{p}{2})} :

2^{1−z} ∼ 2
Q_{z−1} ∼ \frac{1}{Lz}
\frac{1}{Q_{z−1}(\frac{p}{2})} ∼ \frac{Q(p)}{Q(\frac{p}{2})} = 1 − \frac{p}{2}
[N; z] ∼ N^{χ_{k}} · Γ(−χ_{k})

Here, we used the well-known fact that

\frac{Γ(N + a)}{Γ(N + b)} → N^{a−b}.

The residue of [N; z]f(z) at z = χ_{k} is thus

2 · \frac{1}{L} · (1 − \frac{p}{2}) · N^{χ_{k}}Γ(−χ_{k}) = (2 − p)\frac{1}{L}Γ(−χ_{k})N^{χ_{k}}.

It is now customary to collect all these contributions for k ∈ ℤ, k ≠ 0 in one function δ(x). Set

δ(x) = \frac{1}{L} ∑_{k≠0} Γ(−χ_{k})e^{2kπi·x},

then the periodic quantity of our desired quantity C_{N} is (don’t forget the factor −\frac{1}{2−p})

−δ( log_{2} N).

Observe that this quantity is independent of p. However, in the smaller order terms, the parameter p appears.

We summarize our results as follows:

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} ∼ log_{2} N + \frac{γ}{L} + \frac{1}{2} − α + pα(p) − δ( log_{2} N)

where

α(p) = ∑_{k≥1} \frac{1}{2^{k} − p}, α = α(1)

and

δ(x) = \frac{1}{L} ∑_{k≠0} Γ(−χ_{k})e^{2kπi·x}

is a periodic function of period 1, mean 0 and small amplitude (≈ 10^{−6}). It is given as a Fourier series.

References

1. P. Flajolet, Approximate Counting: A Detailed Analysis, BIT 25 (1985), 113–134.

2. P. Flajolet and R. Sedgewick, Digital Search Trees Revisited, SIAM J. Comput. 15 (1986), 748–767.

3. P. Kirschenhofer and H. Prodinger, Approximate Counting: An Alternative Approach, RAIRO Informatique Théorique et Applications 25 (1991), 43–48.

4. D.E. Knuth, The Art of Computer Science Vol.3, Addison-Wesley, Reading, MA, 1973.

5. H. M. Mahmoud, Evolution of Random Search Trees, Wiley-Interscience Series in Discrete Mathematics and Optimization, New York, 1992.

6. N. E. Nörlund, Vorlesungen über Differenzenrechnung, Chelsea, New York, 1954.

7. H. Prodinger, Hypothetic Analyses: Approximate Counting in the Style of Knuth, Path length in the Style of Flajolet, Theoret. Comput. Sci. (to appear).

8. U. Schmid, Analyse von Collision-Resolution Algorithmen in Random-Access Systemen mit dominanten Übertragungskanälen, Dissertation, TU Wien, 1986.

TU Vienna Wiedner Hauptstrasse 8-10 A-1040 Vienna Austria