THE FIBONACCI KILLER

Peter J. Grabner and Helmut Prodinger

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

1. Introduction

We consider the following stochastic process: Assume that a “player” is hit at any time x with probability p. However he dies only after two consecutive hits. We might code this process by 0 and 1, marking a hit e.g. by a “1”. Then the sequences associated with a player can be described by

{0, 10}^{∗} · 11.

The notation {0, 10}^{∗} denotes arbitrary sequences consisting of the blocks 0 and 10, the block 11 are the fatal hits. Notice that {0, 10}^{∗} are exactly the admissible blocks in the Fibonacci expansion of integers (Zeckendorf expansion, cf.[13]). Accordingly, the generating function

\frac{p^{2}z^{2}}{1 − qz − pqz^{2}}  (1.1)

has as the coefficient of z^{x} the probability ℙ{X = x} that the lifetime X of a player is exactly x. The generating function (1.1) is known in the context of the Fibonacci distribution or geometric distribution of order 2, cf. [1], [3], [4], [7], [8], [10], [12].

Here, we are interested in n (independent) players subject to this game and ask when (in the sense of a mean value) the last player dies.

Without the “Fibonacci” restriction, i.e. the maximum of n (independent) geometric random variables, this problem has been studied previously and has some applications. (Compare [5], [11].)

We have obviously

ℙ{ max{X_{1}, …, X_{n}} ≤ x} = (ℙ{X ≤ x})^{n}.  (1.2)

Typeset by AMS-TEX 2 PETER J. GRABNER AND HELMUT PRODINGER

1991 Mathematics Subject Classification. 05A15.

This research was supported by the Austrian-Hungarian cooperation project 10U3.

The generating function of ℙ{X > x} is given by

\frac{1 + pz}{1 − qz − pqz^{2}} .

We now factor the denominator of this function to obtain

1 − qz − pqz^{2} = (1 − az)(1 − bz)

with

a = \frac{q + \sqrt{q^{2} + 4pq}}{2} and b = \frac{q − \sqrt{q^{2} + 4pq}}{2} .

Performing the partial fraction decomposition and extracting coefficients yields

ℙ\{X > x\} = \frac{1}{\sqrt{q^{2} + 4pq}} (a^{x}(a + p) − b^{x}(b + p)) .

Using (1.2) we obtain the expectation for the maximum lifetime of n players

\begin{aligned}𝔼_{n} & = 𝔼 max \{X_{1}, …, X_{n}\} \\ & = ∑_{x≥0} (1 − (1 − \frac{1}{\sqrt{q^{2} + 4pq}} (a^{x}(a + p) − b^{x}(b + p)) )^{n}) . \end{aligned}  (1.3)

By the binomial theorem we obtain

𝔼_{n} = ∑_{m=1}^{n}(−1)^{m−1}\binom{n}{m} ∑_{x≥0} (Aa^{x} − Bb^{x})^{m} ,  (1.4)

where we use the notation

A = \frac{a + p}{\sqrt{q^{2} + 4pq}} = \frac{a^{2}}{q\sqrt{q^{2} + 4pq}} and B = \frac{b + p}{\sqrt{q^{2} + 4pq}} = \frac{b^{2}}{q\sqrt{q^{2} + 4pq}} .

For example, in the symmetric case p = q = \frac{1}{2} we have a = \frac{1+\sqrt{5}}{4}, b = \frac{1−\sqrt{5}}{4}, A = \frac{5+3\sqrt{5}}{10} and B = \frac{5−3\sqrt{5}}{10}.

We will find that 𝔼_{n} ∼ log_{1/a} n and refer for the (technical) proof and a more precise statement to the next section.

2. Asymptotic Analysis

In (1.4) we found the expression

𝔼_{n} = ∑_{m=1}^{n}(−1)^{m−1}\binom{n}{m}f(m),  (2.1)

containing the function

f(z) = ∑_{x≥0} (Aa^{x} − Bb^{x})^{z} for ℜz > 0.

For an expression of that type we can write a complex contour integral

𝔼_{n} = \frac{1}{2πi} ∮_{C} \frac{(−1)^{n}n!}{z(z − 1) ⋯ (z − n)}f(z) dz,  (2.2)

where C is a positively oriented Jordan curve encircling the points 1, 2, …, n (and no other integer points); this can easily be checked by residue calculus.

The contours of integration

We will use Rice’s method to obtain an asymptotic expansion for 𝔼_{n}. For this, we refer e.g. to [2] and [6]. This method is based on a deformation of the contour of integration. For this purpose we need an analytic continuation of the function f to a region containing a half-plane ℜz > −ε for ε > 0 (we actually give an analytic continuation to the whole complex plane).

Using the notation C = \frac{B}{A} and d = \frac{b}{a} (observe that |C| < 1 and |d| < 1) we obtain

\begin{aligned}f(z) & = A^{z} ∑_{x≥0} a^{xz} (1 − Cd^{x})^{z} = A^{z} ∑_{x≥0} a^{xz} ∑_{ℓ≥0}(−1)^{ℓ}C^{ℓ}d^{xℓ}\binom{z}{ℓ} \\ & = A^{z} ∑_{ℓ≥0}(−1)^{ℓ}C^{ℓ}\binom{z}{ℓ} ∑_{x≥0}(a^{z}d^{ℓ})^{x} \\ & = A^{z} ∑_{ℓ≥0} \binom{z}{ℓ}\frac{(−1)^{ℓ}C^{ℓ}}{1 − a^{z}d^{ℓ}} , \end{aligned}  (2.3)

where the reversion of the order of summation was justified because of the absolute convergence of the sum for ℜz > 0. The sum in the last line gives a valid expression for f(z) for every complex number z which is not a solution of any of the equations 1 − a^{z}d^{ℓ} = 0. In the points z_{ℓ,x} = −ℓ\frac{log d}{log a} + \frac{2xπi}{log a} with ℓ = 0, 1, … and x ∈ ℤ there are simple poles with residue

A^{z_{ℓ,x}} \binom{z_{ℓ,x}}{ℓ}\frac{(−1)^{ℓ−1}C^{ℓ}}{log a} .

In order to be able to deform the contour of integration we need an estimate for f(z) along the vertical line ℜz = −u. For this purpose we write

f(z) − \frac{A^{z}}{1 − a^{z}} = ∑_{x≥0} A^{z}a^{xz} ((1 − Cd^{x})^{z} − 1)

and observe the inequality |(1 − Cd^{x})^{z} − 1| ≤ min(2, |z|Cd^{x}). This yields

|f(z) − \frac{A^{z}}{1 − a^{z}} | ≤ A^{−u} ( ∑_{0≤x≤log |z|} 2|a|^{−xu} + |z| ∑_{x>log |z|} a^{−xu}Cd^{x}) ≪ |z|^{α} (2.4)

for |d| < a^{u} < 1 and α = −u log a.

We are now ready to start the deformation of the contour of integration: we take C′ as the new contour and write

\begin{matrix}\frac{1}{2πi} ∮_{C} \frac{(−1)^{n}n!}{z(z − 1) ⋯ (z − n)}f(z) dz = \frac{1}{2πi} ∮_{C′} \frac{(−1)^{n}n!}{z(z − 1) ⋯ (z − n)}f(z) dz \\ − ∑ Res_{z=z_{i}} \frac{(−1)^{n}n!}{z(z − 1) ⋯ (z − n)}f(z), \end{matrix} (2.5)

where the summation runs over all poles z_{i} between the curves C and C′. Notice that there is a second order pole at 0. Computation of residues yields (with H_{n} = 1 + \frac{1}{2} + ⋯ + \frac{1}{n})

Res_{z=0} \frac{(−1)^{n}n!}{z(z − 1) ⋯ (z − n)}f(z) = \frac{1}{log a}H_{n} + \frac{log A}{log a} − \frac{1}{2}

Res_{z=χ_{x}} \frac{(−1)^{n}n!}{z(z − 1) ⋯ (z − n)}f(z) = \frac{A^{χ_{x}}}{χ_{x} loga} \frac{n!Γ(1 − χ_{x})}{Γ(n + 1 − χ_{x})} for x ≠ 0,

(2.6)

where χ_{x} = \frac{2xπi}{log a} = z_{0,x}.

Shifting the upper, the lower and the right part of C′ (cf. the figure) to infinity and observing, that the integrals over these parts of the contour vanish then, yields

𝔼_{n} = \frac{1}{log \frac{1}{a}} H_{n} − \frac{log A}{log a} + \frac{1}{2} − ∑_{x∈ℤ\\{0\}} \frac{A^{χ_{x}}}{χ_{x} log a} \frac{n!Γ(1 − χ_{x})}{Γ(n + 1 − χ_{x})}

− \frac{1}{2πi} ∫_{−u−i∞}^{−u+i∞}\frac{(−1)^{n}n!}{z(z − 1) ⋯ (z − n)}f(z) dz.

(2.7)

We now use the well-known asymptotic expansions H_{n} = log n + γ + O(\frac{1}{n}) and

\frac{n!}{Γ(n + 1 − χ_{x})} = n^{χ_{x}} (1 + O(\frac{x^{2}}{n})) (by Stirling’s formula) to formulate our main

result.

Theorem 1. The expected maximal lifetime 𝔼_{n} of n independent players each of which has the Fibonacci distribution (or geometric distribution of order 2) fulfils for n → ∞

𝔼_{n} = log_{1/a} n − \frac{γ + log A}{log a} + \frac{1}{2} − φ(log_{1/a} n) + O(n^{−u}),  (2.8)

for 0 < u < min(1, \frac{log |d|}{log a}) and φ denotes a continuous periodic function of period 1 and mean 0 given by the Fourier expansion

φ(t) = \frac{1}{log a} ∑_{x∈ℤ\\{0\}} A^{χ_{x}}Γ(−χ_{x})e^{2xπit} = \frac{1}{log a} ∑_{x∈ℤ\\{0\}} Γ(−χ_{x})e^{2xπi(t−log_{1/a} A)},

(2.9)

which is rapidly convergent due to the exponential decay of the Γ-function along vertical lines. The remainder term is obtained by a trivial estimate of the integral and the (uniform) O-terms in Stirling’s formula.

3. Extensions

Here, we briefly sketch the more general case where k consecutive hits are necessary to kill a player. In this case the probability ℙ(X = x) was derived by Philippou and Muwafi [9] in terms of multinomial coefficients. As described in the introduction there is a bijection to the sequences

{0, 10, 110, …, 1^{k−1}0} · 1^{k},

which yield the probability generating function

\frac{p^{k}z^{k}}{1 − qz − pqz^{2} − ⋯ − p^{k−1}qz^{k}} = \frac{p^{k}z^{k}(1 − pz)}{1 − z + qp^{k}z^{k+1}}  (3.1)

for the lifetime of a player (cf. [1, pp. 299ff], [3, p. 428], [7, p. 207], [8]). Likewise, the generating function of ℙ{X > x} is given by

\frac{1 − p^{k}z^{k}}{1 − z + qp^{k}z^{k+1}}  (3.2)

Again we factor the polynomial in the denominator

1 − qz − pqz^{2} − ⋯ − p^{k−1}qz^{k} = (1 − αz)(1 − α_{2}z) ⋯ (1 − α_{k}z)

with |α| > |α_{2}| ≥ ⋯ ≥ |α_{k}| (α > 0). Then we have by partial fraction decomposition and extracting coefficients

ℙ{X > x} = Aα^{x} + A_{2}α_{2}^{x} + ⋯ + A_{k}α_{k}^{x}  (3.3)

with

A = \frac{α(α − p)}{q((k + 1)α − k)}

and similar expressions for A_{2}, …, A_{k}.

For the expectation of the maximal lifetime of n players we obtain

𝔼_{n,k} = 𝔼 max\{X_{1}, …, X_{n}\} = ∑_{m=1}^{n}(−1)^{m−1}\binom{n}{m}g(m)

with

g(z) = ∑_{ℓ≥0} (Aα^{ℓ} + ⋯ + A_{k}α_{k}^{ℓ})^{z} for ℜz > 0.

For the purpose of analytic continuation of g we consider

g(z) − \frac{A^{z}}{1 − α^{z}}

and proceed as in (2.4) to obtain the continuation and a polynomial estimate for g(z) along some vertical line ℜz = −ε for sufficiently small ε > 0.

We are now ready to perform similar calculations as in Section 2. Thus we obtain

Theorem 2. The expected maximal lifetime 𝔼_{n,k} of n players each of which has geometric distribution of order k satisfies

𝔼_{n,k} = log_{1/α} n − \frac{γ + log A}{log α} + \frac{1}{2} + ψ (log_{1/α} n) + O(n^{−ε}),

for 0 < ε < min(1, \frac{log |α_{2}|}{log α}) and a continuous periodic function ψ of period 1 and mean 0 whose Fourier expansion is given by

ψ(t) = \frac{1}{log α} ∑_{x∈ℤ\\{0\}} A^{χ_{x}}Γ(−χ_{x})e^{2xπit} = \frac{1}{log α} ∑_{x∈ℤ\\{0\}} Γ(−χ_{x})e^{2xπi(t−log_{1/α} A)},

where χ_{x} = \frac{2xπi}{log α}.

By bootstrapping we find that, for k → ∞,

α ∼ 1 − qp^{k} + … and A ∼ 1 + kqp^{k} + ….

References

1. W. Feller, An Introduction to Probability Theory and Its Applications, vol. 1, J. Wiley, New York, 1957.

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

3. N.L. Johnson, S. Kotz and A.W. Kemp, Discrete Univariate Distributions, Wiley, New York, 1992.

4. A.W. Kemp, Second-Order Linear Recurrence Distributions and Their Properties, manuscript.

5. P.Kirschenhofer and H.Prodinger, A Result in Order Statistics Related to Probabilistic Counting, submitted (1992).

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

7. A.N. Philippou, Distributions and Fibonacci Polynomials of Order k, Longest Runs, and Reliability of Consecutive-k-out-of-n: F Systems, Fibonacci Numbers and Their Applications (A.N. Philippou, G.E. Bergum and A.F. Horadam, eds.), Reidel, Dordrecht, 1986, pp. 203– 227.

8. A.N. Philippou, C. Georghiou and G.N. Philippou, A Generalized Geometric Distribution and Some of Its Properties, Stat. and Probab. Letters 1 (1983), 171–175.

9. A.N. Philippou and A.A. Muwafi, Waiting for the k-th Consecutive Success and the Fibonacci Sequence of Order k, Fibonacci Quarterly 20 (1982), 28–32.

10. H.D. Shane, A Fibonacci Probability Function, Fibonacci Quarterly 11 (1973), 517–522.

11. W.Szpankowski and V.Rego, Yet another Application of a Binomial Recurrence: Order Statistics, Computing 43 (1990), 401–410.

12. C. Taillie and G.P. Patil, The Fibonacci Distribution Revisited, Communications in Statistics – Theory and Methods 15 (1986), 951–959.

13. E. Zeckendorf, Représentations des nombres naturels par une somme des nombres de Fibonacci ou des nombres de Lucas, Bull. Soc. Royale Sci. Liège 41 (1972), 179–182.

TU Graz Steyrergasse 30 A-8010 Vienna Austria

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

E-mail address: grabner@ftug.dnet.tu–graz.ac.at, proding@email.tuwien.ac.at