A COIN TOSSING ALGORITHM FOR

COUNTING LARGE NUMBERS OF EVENTS

Peter Kirschenhofer and Helmut Prodinger

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

1. Introduction

“Approximate counters” are realized by probabilistic algorithms that maintain an approximate count in the interval 1 to n using only about log_{2} log_{2} n bits. The algorithmic principle was proposed by R. Morris [7]:

Starting with counter C = 1, after n increments C should contain a good approximation to log_{2} n. Thus C should be increased by 1 after another n increments approximately. Since only C is known the algorithm has to base its decision on the content of C alone.

The principle to increment the counter is now

C := C + \{ \begin{matrix}0 with probability 1 − 2^{−C} \\ 1 with probability 2^{−C} \end{matrix}  (*)

Flajolet [2] has analyzed this algorithm in detail; another method of analysis has been proposed by the authors [4]. In [2; p.127ff] Flajolet also discusses variants of the incremental procedure (*), essentially replacing base 2 by base a. For a < 2 a smoother behaviour of the counter is obtained.

The aim of this paper is twofold.

(i) On the one hand we substitute (*) by an incremental process that adds \frac{1}{b} to the counter with suitable probability. For a = 2^{1/b} the resulting “automaton” (compare Fig. 1) is closely related to Flajolet’s smoothing procedure just described. Nevertheless we point out that our algorithm is slightly more general and flexible enough to deal with a related problem described below.

(ii) On the other hand we describe a simple coin tossing algorithm that simulates the probabilities in (*). We compare the results on this algorithm with another one whose analysis is closely related to a problem studied by Knuth in the context of binary addition [6]. It turns out that the variance in our instance is significantly smaller.

1991 Mathematics Subject Classification. 68Q25.

Key words and phrases. Probabilistic Algorithms, Analysis of Algorithms, Asymptotic Expansions.

In Section 2 of this paper we present the analysis of the general incremental principle mentioned in (i) above.

Section 3 refers to the coin tossing problems mentioned in (ii). It turns out that the analysis of the behaviour of these algorithms is essentially (i.e. with neglectible error terms) covered by the analysis of Section 2.

2. A general incremental procedure

We consider the following incremental procedure. Starting with C′ = 1 we increment as follows (b is a fixed natural number, 0 < d < 2^{1/b}).

C′ := C′ + \{ \begin{matrix}0 with probability 1 − d · 2^{−C′/b} \\ 1 with probability d · 2^{−C′/b} \end{matrix}

(The constant d will be chosen appropiately later on.) To get a good approximation for log_{2} n it is meaningful to rescale the countervalues of counter C′ by considering

C = 1 + \frac{C′ − 1}{b}.

A reformulation of the incremental procedure in terms of C reads

C := C + \{ \begin{matrix}0 with probability 1 − d · 2^{−C− \frac{1}{b} +1} \\ \frac{1}{b} with probability d · 2^{−C− \frac{1}{b} +1} \end{matrix}  (**)

We denote for abbreviation the possible counter values of C by

c_{j} = 1 + \frac{j − 1}{b}, j = 1, 2, 3, · · · .

Then we have for the transition c_{j} ⟶ c_{j+1} the probability d·2^{−j/b}. In the following we set

a = 2^{1/b}.

In order to illustrate the above concept we may use the following “automaton”:

Fig. 1

The reader might observe that the instance d = 1 is the instance studied by Flajolet in [2;p.127ff]. In the following derivation we digress from Flajolet’s analysis after having established the probabilities as in formula (6). Instead of Flajolet’s Mellin-type analysis we use a contour integral representation for the alternating sums coming up (compare Lemma 1).

Let p_{n,l} denote the probability to reach “state” c_{l} in n steps and H_{l}(z) the corresponding probability generating function, i.e.

H_{l}(z) = ∑_{n≥0} p_{n,l}z^{n}.  (1)

With α_{i} = 1 − da^{−i} it follows immediately from Figure 1 that

\begin{aligned}H_{l}(z) & = \frac{1}{1 − α_{1}z} · da^{−1}z · \frac{1}{1 − α_{2}z} · da^{−2}z … \frac{1}{1 − α_{l}z} \\ & = d^{l−1}a^{−\binom{l}{2}}z^{l−1} ∏_{i=1}^{l} \frac{1}{1 − α_{i}z} . \end{aligned}  (2)

Let

H_{l}(z) = ∑_{j=1}^{l} \frac{A_{l,j}}{1 − α_{j}z}  (3)

denote the partial fraction decomposition of H_{l}(z). It is a straightforward computation to derive

A_{l,j} = \frac{(−1)^{l−j}a^{−\binom{l−j}{2}}}{Q_{j−1}(a)Q_{l−j}(a)},  (4)

where

Q_{i}(a) = (1 − \frac{1}{a})(1 − \frac{1}{a^{2}} ) … (1 − \frac{1}{a^{i}} ).  (5)

From (3) and (4) we find (interchanging j and l − j)

p_{n,l} = ∑_{j=0}^{l−1} \frac{(−1)^{j} a^{−\binom{j}{2}}}{Q_{j}(a) Q_{l−1−j}(a)} (1 − da^{j−l})^{n} .  (6)

By the binomial theorem we may express p_{n,l} by an alternating sum:

p_{n,l} = ∑_{k=0}^{n} \binom{n}{k}(−1)^{k}d^{k} ∑_{j=0}^{l−1} \frac{(−1)^{j}}{Q_{j}(a)Q_{l−1−j}(a)} · a^{−\binom{j}{2}+(j−l)k}

Using Euler’s famous partition identities [1]

∑_{j≥0} \frac{(−1)^{j}a^{−\binom{j}{2}}t^{j}}{Q_{j}(a)} = ∏_{m≥0} (1 − \frac{t}{a^{m}} )  (7)

and

∑_{j≥0} \frac{t^{j}}{Q_{j}(a)} = ∏_{m≥0} (1 − \frac{t}{a^{m}} )^{−1} ,  (8)

the second sum in p_{n,l} may be associated to a product.

p_{n,l} = ∑_{k=0}^{n} \binom{n}{k}(−1)^{k}(\frac{d}{a})^{k} [t^{l−1}] ∏_{m=0}^{k−1} (1 − \frac{t}{a^{m}} )  (9)

For the expectation E_{n} of the value of the counter C after n steps we find

E_{n} = ∑_{l≥1} p_{n,l} · c_{l} = 1 + \frac{1}{b} ∑_{k=0}^{n} \binom{n}{k}(−1)^{k} (\frac{d}{a})^{k} ∑_{l≥0} l [t^{l}] ∏_{m=0}^{k−1} (1 − \frac{t}{a^{m}} )

Now ∑_{l≥0} l[t^{l}]f(t) = f′(1), so that

E_{n} = 1 − \frac{1}{b} ∑_{k=1}^{n} \binom{n}{k}(−1)^{k} (\frac{d}{a})^{k} Q_{k−1}(a) = 1 − \frac{1}{b}Σ_{n}  (10)

An asymptotic evaluation of an alternating sum as in (10) may be performed using the following

Lemma 1. [8] Let C be a curve surrounding the points s, s + 1, …, n (s ∈ ℕ) in the complex plane and let f(z) be analytic inside C. Then

∑_{k=s}^{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)}. □

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

∑ Res([n; z]f(z)) + O (n^{σ+ε}) , any ε > 0

where the sum is taken over all poles z_{0} different from s, …, n with ℜz_{0} > σ.

In our sum we have s = 1 and f(k) = (\frac{d}{a})^{k} Q_{k−1}(a), which may be continued analytically by

f(z) = (\frac{d}{a})^{z}Q_{z−1}(a), where Q_{z}(a) = \frac{Q_{∞}(a)}{∏_{j≥1} (1 − \frac{1}{a^{z+j}} )}.

In order to find the residues of [n; z]f(z) at the double pole z = 0 we use the local expansions

[n; z] ∼ −\frac{1}{z}(1 + zH_{n})
(\frac{d}{a})^{z} ∼ 1 + z log (\frac{d}{a})
Q_{z−1}(a) ∼ \frac{1}{z log a} (1 + z(log a)(\frac{1}{2} − α_{a})) where α_{a} = ∑_{k≥1} \frac{1}{a^{k} − 1}.

With log a = \frac{1}{b} log 2 we have the following contribution Σ_{n,0} to Σ_{n}:

−Σ_{n,0} = log_{a} n + \frac{γ}{log a} + log_{a} d − \frac{1}{2} − α_{a}  (11)

Near the simple poles z_{k} = \frac{2kπi}{log a} = χ_{k}(a), k ∈ ℤ, k ≠ 0, we have the expansions

[n; z] ∼ n^{χ_{k}(a)} · Γ( − χ_{k}(a)) = e^{2kπi·log_{a} n} · Γ( − χ_{k}(a))
(\frac{d}{a})^{z} ∼ e^{χ_{k}(a)·log d}
Q_{z−1}(a) ∼ \frac{1}{log a} · \frac{1}{z − χ_{k}(a)},

so that the poles z_{k} yield the following fluctuating contribution Σ_{n,k} to Σ_{n} :

Σ_{n,k} = \frac{1}{log a}Γ( − χ_{k}(a))e^{2kπi·log_{a}(nd)}

In total we have

Theorem 2. The expected value E_{n} of the counter C after n random increments with the generalized incremental procedure (**) fulfills

E_{n} = log_{2} n + \frac{γ}{log 2} + log_{2} d + 1 − \frac{1}{2b} − \frac{α_{a}}{b} + δ_{1}( log_{a} n + Δ) + O (n^{−1})

where

α_{a} = ∑_{k≥1} \frac{1}{a^{k} − 1}, a = 2^{1/b}

and the periodic function

δ_{1}(x) = −\frac{1}{log 2} ∑_{k≠0} Γ( − χ_{k}(a))e^{2kπix},

where

χ_{k}(a) = \frac{2kπi}{log a}  and  Δ = log_{a} d. □

Since

|Γ(iy)|^{2} = \frac{π}{y · sinh(πy)},

we have |Γ( − χ_{k}(a))|^{2} = O(be^{− \frac{2π^{2}b}{log 2}} ) for b → ∞, so that the fluctuating term, which is already very small for the classical case b = 1, becomes even smaller for b getting large.

In order to find the appropriate value for the constant d we consider the expectation S_{n} of 2^{C} after n random increments:

S_{n} = ∑_{l} p_{n,l}2^{c_{l}}  (12)

Since

p_{n,l} = p_{n−1,l} (1 − da^{−l}) + p_{n−1,l−1}da^{1−l}  (13)

we have

S_{n} = S_{n−1} − \frac{2d}{a} + 2d, n ≥ 1; S_{0} = 2;

and thus

S_{n} = 2d(1 − \frac{1}{a})n + 2.  (14)

A good choice for d is therefore

d = \frac{a}{2(a − 1)},  (15)

so that S_{n} = n + 2.

Nevertheless we can analyze the variance V_{n} of the content of C after n steps for arbitrary d in an analogous manner as the expectation E_{n}. Omitting the technical details we obtain, neglecting periodic fluctuations of mean 0,

V_{n} ∼ \frac{π^{2}}{6 log^{2} 2} − \frac{β_{a}}{b^{2}} − \frac{α_{a}}{b^{2}} + \frac{1}{12b^{2}} − [δ_{1}^{2}]_{0} ,  (16)

where [δ_{1}^{2}]_{0} is the mean of the square of the periodic function δ_{1}(x) defined in Theorem 2.

In order to study the influence of b on V_{n}, it is helpful to make use of the following remarkable transformation of the constant in (16): We have

α_{a} + β_{a} = ∑_{k≥1} \frac{a^{k}}{(a^{k} − 1)^{2}} = h_{1}(log a),

where

h_{1}(x) = ∑_{k≥1} \frac{e^{kx}}{(e^{kx} − 1)^{2}} .  (17)

Now it follows from Dedekind’s functional equation for the η-function that

h_{1}(x) = \frac{π^{2}}{6x^{2}} − \frac{1}{2x} + \frac{1}{24} − \frac{4π^{2}}{x^{2}} h_{1}(\frac{4π^{2}}{x} )

(compare [5]; observe the typo therein). Thus we have

α_{a} + β_{a} = \frac{π^{2}}{6 log^{2} a} − \frac{1}{2 log a} + \frac{1}{24} − \frac{4π^{2}}{log^{2} a}h_{1}(\frac{4π^{2}}{log a}).  (18)

On the other hand, again using |Γ(iy)|^{2} = \frac{π}{y · sinh(πy)}, we get

[δ_{1}^{2}]_{0} = \frac{log a}{log^{2} 2} ∑_{k≥1} \frac{1}{k · sinh (\frac{2kπ^{2}}{log a} )} = \frac{2 log a}{log^{2} 2}h_{2}(\frac{2π^{2}}{log a})  (19)

with

h_{2}(x) = ∑_{k≥1} \frac{(−1)^{k−1}}{k (e^{kx} − 1)}.  (20)

Combining (18) and (19) and regarding log a = \frac{log 2}{b}, we finally have Theorem 3. The variance V_{n} of the content of the counter C after n steps of the generalized incremental procedure (**) fulfills

V_{n} = \frac{1}{2b log 2} + \frac{1}{24b^{2}} + \frac{4π^{2}}{log^{2} 2}h_{1}(\frac{4π^{2}b}{log 2}) − \frac{2}{b log 2}h_{2}(\frac{2π^{2}b}{log 2})

+ δ_{3}( log_{a} n + Δ) + O(\frac{log n}{n})

where h_{1}(x) and h_{2}(x) are defined in (23) and (26), and where δ_{3}(x) is a periodic function of mean zero, and Δ = log_{a} d. □

δ_{3}(x) is a combination of δ_{1}(x) and δ_{2}(x), whose Fourier coefficients could be computed in principle.

The reader should note that the main term is of order b^{−1} in b; the values h_{1}(\frac{4π^{2}b}{log 2}) resp. h_{2}(\frac{2π^{2}b}{log 2}) tend to 0 exponentially fast in b! The result quantifies the smoother behaviour of the approximate counting procedure for increasing b. For d = 1 Theorem 3 should be compared with Flajolet’s result [2;eq.(50)], where only the leading term \frac{1}{2b log 2} appears.

3. Approximate Counting by Coin Tossings

In this section we apply the previous results to the analysis of an approximate counting algorithm where the incremental procedure (*) is simulated by coin tossings. We flip a fair coin and increase the counter C by 1 after having seen C consecutive heads occurring since the previous incremental step. More formally the set of sequences yielding a counter C = l is described by the regular expression

0^{∗}1{0, 10}^{∗}11{0, 10, 110}^{∗} … 1^{l−1}{0, 10, …, 1^{l−1}0}^{∗}{ε, 1, …, 1^{l−1}}.

The corresponding generating function equals

F_{l}(z) = \frac{1 − z^{l}}{(1 − z)^{2}} z^{\binom{l}{2}} ∏_{j=1}^{l−1} \frac{1 − z}{1 − 2z + z^{j+2}} , l ≥ 1,  (21)

so that the probability p_{n,l} that counter C = l after n tossings is

p_{n,l} = 2^{−n} [z^{n}] F_{l}(z).  (22)

It is our aim to show that the analysis of this coin tossing algorithm may be reduced to the analysis of Section 2 by approximating the probabilities p_{n,l} step by step.

For l ≥ 2, F_{l}(z) is a rational function having l − 1 first order poles ρ_{1}, …, ρ_{l−1} of absolute value ≤ \frac{3}{4}: For z traversing the circle |z| = \frac{3}{4} the value of 1 − 2z + z^{j+2} winds around the origin exactly once, so that 1 − 2z + z^{j+2} has exactly one root ρ_{j} in |z| ≤ \frac{3}{4}. For later purposes we note that |1 − 2z + z^{j+2}| ≥ |−\frac{1}{2} + (\frac{3}{4})^{3}| = \frac{5}{64} for j ≥ 1 and |z| = \frac{3}{4}. Therefore

|F_{l}(z)| ≤ C_{1}(\frac{3}{4})^{\binom{l}{2}}(\frac{7}{4})^{l−1}(\frac{64}{5})^{l−1} = O (η^{\binom{l}{2}}) for any η > \frac{3}{4}.  (23)

The reader should observe that because of

2ρ_{j} = 1 + ρ_{j}^{j+2}  (24)

ρ_{j} will be close to 1/2 for j getting large. More precisely, using Lagrange’s inversion formula, we have

ρ_{j} = \frac{1}{2}(1 + ∑_{k≥1} \frac{1}{k} \binom{k(j + 2)}{k − 1}\frac{1}{2^{k(j+2)}} ) = \frac{1}{2} (1 + \frac{1}{2^{j+2}} + …) .  (25)

Now it follows that

2^{n}p_{n,l} = − ∑_{j=1}^{l−1} Res(F_{l}(z); z = ρ_{j})ρ_{j}^{−n−1} + \frac{1}{2πi} ∫_{|z|= \frac{3}{4}} F_{l}(z)\frac{dz}{z^{n+1}} ,

where the integral is O (η^{\binom{l}{2}} (\frac{4}{3})^{n}) for any η > \frac{3}{4}, with an absolute O–constant. From this observation it is immediate that p_{n,l} may be substituted by

q_{n,l} = − ∑_{j=1}^{l−1} Res(F_{l}(z); z = ρ_{j})ρ_{j}^{−1} (2ρ_{j})^{−n}  (26)

with exponentially small errors in expectation and variance. The computation of the residues gives

Res(F_{l}(z); z = ρ_{j}) = \frac{(1 − ρ_{j}^{l}) ρ\binom{l}{2}_{j} (1 − ρ_{j})^{l−1}}{(1 − ρ_{j})^{2} (−2 + (j + 2)ρ_{j}^{j+1})} A_{j} B_{j,l}

where (compare (24)!)

\begin{aligned}A_{j} (1 − ρ_{j})^{−2} & = ∏_{i=0}^{j−1} (1 − 2ρ_{j} + ρ_{j}^{i+2})^{−1} = ∏_{i=0}^{j−1} (ρ_{j}^{i+2} − ρ_{j}^{j+2})^{−1} \\ & = ρ_{j}^{1−\binom{j+2}{2}}/Q_{j} (ρ_{j}^{−1}) , \end{aligned}

B_{j,l} = ρ_{j}^{−(j+2)(l−1−j)}(−1)^{l−1−j}/Q_{l−1−j} (ρ_{j}^{−1}) .

Using formula (24) it can be shown by some straightforward algebra that

\begin{aligned}q_{n,l} & = ∑_{j=1}^{l−1} \frac{(1 − ρ_{j}^{l}) (1 − ρ_{j}^{j+1})^{l−1}}{(1 − (j + 1)ρ_{j}^{j+2})} \frac{(−1)^{l−1−j}ρ\binom{l−1−j}{2}_{j}}{Q_{j} (ρ_{j}^{−1}) Q_{l−1−j} (ρ_{j}^{−1})} (2ρ_{j})^{−n} \\ & = ∑_{j=1}^{l−1} a_{l,j} (2ρ_{j})^{−n} ,  say. \end{aligned}  (27)

This formula suggests the quantity

r_{n,l} = ∑_{j=1}^{l−1} \frac{(−1)^{l−1−j}2^{−\binom{l−1−j}{2}}}{Q_{j}Q_{l−1−j}} (2ρ_{j})^{−n} = ∑_{j=1}^{l−1} b_{l,j} (2ρ_{j})^{−n} , where Q_{k} = Q_{k}(2),

(28)

as a good approximation of q_{n,l}. Indeed, we have

∑_{l≥j+1} la_{l,j} = \frac{(1 − ρ_{j}^{j+1})^{j}}{(1 − (j + 1)ρ_{j}^{j+2}) Q_{j} (ρ_{j}^{−1})} ∑_{l≥0}(l + j + 1)s_{l,j}

with

s_{l,j} = (1 − ρ_{j}^{j+1}ρ_{j}^{l}) (1 − ρ_{j}^{j+1})^{l} (−1)^{l}ρ\binom{l}{2}_{j}/Q_{l} (ρ_{j}^{−1}) .  (29)

Using Euler’s identity (7)

∑_{l≥0} s_{l,j} = ∏_{m≥0} (1 − (1 − ρ_{j}^{j+1})ρ_{j}^{m}) − ρ_{j}^{j+1} ∏_{m≥0} (1 − (1 − ρ_{j}^{j+1})ρ_{j}^{m+1}) = 0. (30)

Differentiating formula (7) we have

∑_{l≥0} l \frac{(−1)^{l}a^{−\binom{l}{2}}t^{l}}{Q_{l}(a)} = −t( ∑_{m≥0} \frac{1}{a^{m} − t}) ∏_{m≥0} (1 − \frac{t}{a^{m}} ) ,  (31)

so that, after a short computation,

∑_{l≥0} ls_{l,j} = − (1 − ρ_{j}^{j+1}) ∏_{m≥1} (1 − (1 − ρ_{j}^{j+1})ρ_{j}^{m}) .  (32)

Altogether

∑_{l≥j+1} la_{l,j} = −\frac{(1 − ρ_{j}^{j+1})^{j+1}}{(1 − (j + 1)ρ_{j}^{j+2}) Q_{j} (ρ_{j}^{−1})} ∏_{m≥1} (1 − (1 − ρ_{j}^{j+1})ρ_{j}^{m}) .  (33)

In the same way we derive

∑_{l≥j+1} l b_{l,j} = −\frac{Q_{∞}}{Q_{j}} , where Q_{∞} = Q_{∞}(2), Q_{j} = Q_{j}(2).  (34)

The sum is up to a factor 1 + O(j2^{−j}) the right hand side of (33). Therefore the series

∑_{j≥1} (2ρ_{j})^{−n} ∑_{l≥j+1} l (a_{l,j} − b_{l,j})

A coin tossing algorithm 10 converges absolutely and may be rearranged as ∑_{l≥1} l(q_{n,l} − r_{n,l}).

It is easily seen that ∑_{j≥1}(2ρ_{j})^{−n}O(2^{−j}) is o(1) for n → ∞. In order to get a sharper estimate we may apply Lemma 1: We have (2ρ_{j})^{−1} = 1 − δ_{j}, where δ_{j} = O(2^{−j}) so that

∑_{j≥1} (2ρ_{j})^{−n} O(2^{−j}) = ∑_{k=0}^{n} \binom{n}{k}(−1)^{k}f(k)

with f(k) = ∑_{j≥1} δ_{j}^{k}O(2^{−j}). Since ∑_{j≥1} δ_{j}^{z}O(2^{−j}) defines an analytic function for ℜz > −1 we find from Lemma 1 that the whole sum is O(n^{−1+ε}) for any ε > 0.

Thus the expectation E_{n} of the content of the counter C after n tossings fulfills

\begin{aligned}E_{n} & = ∑_{l≥1} lq_{n,l} + O((\frac{2}{3})^{n}) = ∑_{l≥1} lr_{n,l} + ∑_{l≥1} l(q_{n,l} − r_{n,l}) + O((\frac{2}{3})^{n}) \\ & = ∑_{l≥1} lr_{n,l} + O(n^{−1+ε}), any ε > 0. \end{aligned}

In order to evaluate ∑_{l≥1} l r_{n,l} we approximate (2ρ_{j})^{−1} by 1 − 2^{−j−2} (compare (25)):

Δ_{n} = ∑_{j≥1} ((2ρ_{j})^{−n} − (1 − 2^{−j−2})^{n}) \frac{Q_{∞}}{Q_{j}}

= ∑_{k=1}^{n} \binom{n}{k}(−1)^{k} ∑_{j≥1} (δ_{j}^{k} − 2^{−(j+2)k}) \frac{Q_{∞}}{Q_{j}}

where (2ρ_{j})^{−1} = 1 − δ_{j}. From (31) we have δ_{j}^{k} − 2^{−(j+2)k} = O(j2^{−2j}k2^{−j(k−1)}) = O(kj2^{−j(k+1)}) so that f(z) = ∑_{j≥1} (δ_{j}^{z} − 2^{−(j+2)z}) \frac{Q_{∞}}{Q_{j}} is again an analytic function for ℜz > −1. Since f(0) = 0, [n; z]f(z) has a removable singularity at z = 0 and Δ_{n} = O(n^{−1+ε}), any ε > 0.

We finally have

E_{n} = ∑_{l≥1} l r_{n,l} + O(n^{−1+ε}) = ∑_{l≥1} l ∑_{j=1}^{l−1} b_{l,j} (2ρ_{j})^{−n} + O(n^{−1+ε})

= ∑_{l≥1} l ∑_{j=1}^{l−1} b_{l,j} (1 − 2^{−j−2})^{n} + O(n^{−1+ε})

= ∑_{l≥1} l t_{n,l} − ∑_{l≥1} lb_{l,0}(\frac{3}{4})^{n} + O(n^{−1+ε})

= ∑_{l≥1} l t_{n,l} + O(n^{−1+ε})  (35)

where t_{n,l} coincides with p_{n,l} from (6) for a = 2, d = \frac{1}{2}. Therefore E_{n} from this section coincides with E_{n} from Section 2 with an error of order O(n^{−1+ε}). The same result may be proved for the variance V_{n} by an analogous reasoning.

Theorem 4. The expected value E_{n} of counter C after n coin tossings fulfills

E_{n} = log_{2} n + \frac{γ}{log 2} − \frac{1}{2} − α + δ_{1}( log_{2} n) + O (n^{−1+ε}) , any ε > 0,

with

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

The variance V_{n} fulfills for any ε > 0

V_{n} = \frac{1}{2 log 2} + \frac{1}{24} + \frac{4π^{2}}{log^{2} 2}h_{1}(\frac{4π^{2}}{log 2}) − \frac{2}{log 2}h_{2}(\frac{2π^{2}}{log 2}) + δ_{3}( log_{2} n)
+ O (n^{−1+ε}) ≈ 0.7630 …

with δ_{1}, δ_{3}, h_{1}, h_{2} from Theorems 2 and 3.

Theorem 4 shows that our coin tossing algorithm is a very good simulation of the general incremental procedure mentioned in the first two sections with parameters b = 1, d = 1/2.

We finally compare these results with the following alternative variant of a coin tossing algorithm: The Counter C is incremented by 1 if after another flipping of the coin the sequence ends up with a run of C ones. With other words, C maintains 1 plus the length of the longest run of ones. Results on this problem may be found e.g. in [9], [10]; the analysis is closely related to Knuth’s analysis of the average time for carry propagation in binary addition [6]. Intuitively it is clear that the latter proposal leads to a less smooth behaviour than our algorithm from above.

The regular expression corresponding to the set of sequences yielding a counter C ≤ l is

{0, 10, …, 1^{l−1}0}^{∗}{ε, 1, …, 1^{l−1}}

with corresponding generating function

F_{l}(z) = \frac{1 − z^{l}}{1 − 2z + z^{l+1}} .

The dominating singularity is ρ_{l−1}, where ρ_{j} fulfills (24). In Knuth’s analysis [6] the corresponding generating function is

G_{l}(z) = \frac{1}{1 − 2z + \frac{1}{2}z^{l}} .

The dominating singularity τ_{l−1} of G_{l}(z) fulfills τ_{l−1} = ρ_{l−1} + O(l2^{−2l}), so that Knuth’s asymptotic result on the expectation covers the coin tossing problem, too. For comparison we cite the results from [6] and [10]:

A coin tossing algorithm 12

Expectation E_{n} and variance V_{n} of the counter C in the modified algorithm are asymptotic to (neglecting the small periodic fluctuations of mean zero)

E_{n} ∼ log_{2} n + \frac{γ}{log 2} − \frac{1}{2},

V_{n} ∼ \frac{π^{2}}{6 log^{2} 2} + \frac{1}{12} − [δ_{1}^{2}]_{0} ≈ 3.5070 …

(36)

with δ_{1} from Theorem 2. Comparing with (16) we find that the variance in our

algorithm is smaller by α + β = ∑_{k≥1} \frac{2^{k}}{(2^{k} − 1)^{2}} ≈ 2.7440 ….

References

1. G. E. Andrews, The Theory of Partitions, Addison Wesley, 1976.

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

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

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

5. P. Kirschenhofer, H. Prodinger, and J. Schoißengeier, Zur Auswertung gewisser numerischer Reihen mit Hilfe modularer Funktionen, Zahlentheoretische Analysis II (E. Hlawka, ed.), Lecture Notes in Math. 1262, Springer, Berlin, 1987, pp. 108–110.

6. D. E. Knuth, The Average Time for Carry Propagation, Indagationes Mathematicæ 40 (1978), 238–242.

7. R. Morris, Counting Large Numbers of Events in Small Registers, Comm.ACM 21 (1978), 840–842.

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

9. H. Prodinger, Über längste 0–1–Folgen, Zahlentheoretische Analysis II (E. Hlawka, ed.), Lecture Notes in Math. 1262, Springer, Berlin, 1987, pp. 124–133.

10. U. Schmid, Abzählprobleme der theoretischen Informatik, Diplomarbeit, TU Wien, 1985.

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