%Fibonacci Quarterly
%Contour of integration (picture) missing in this version






\input amstex
\magnification 1200
\documentstyle{amsppt}
\TagsOnRight
\define\({\left(}
\define\){\right)}
\define\Res{\operatornamewithlimits{Res}}
\document
\topmatter
\title
The Fibonacci Killer
\endtitle

\author Peter J. Grabner and Helmut Prodinger \endauthor
\affil 
Department of Mathematics\\
Technical University of Graz, Austria\\
and\\
Department of Algebra and Discrete Mathematics \\
Technical University of Vienna, Austria
\endaffil
\address TU Graz
\newline Steyrergasse 30
\newline A-8010 Vienna
\newline Austria\bigskip\noindent
TU Vienna
\newline Wiedner Hauptstrasse 8--10
\newline A-1040 Vienna
\newline Austria
\endaddress 
\email grabner\@ftug.dnet.tu--graz.ac.at,
proding\@email.tuwien.ac.at
\endemail
\thanks
This research was supported by the Austrian-Hungarian cooperation project 10U3.
\endthanks
\subjclass 05A15\endsubjclass
\endtopmatter

\head 1. Introduction \endhead

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 $\bold 0$ and 
$\bold 1$, marking
a hit e.g. by a ``$\bold 1$''. 
Then the sequences associated with a player can
be described by
$$
\{\bold 0,\bold{10}\}^*\cdot \bold{11}.
$$
The notation $\{\bold0,\bold{10}\}^*$ denotes 
arbitrary sequences consisting of the blocks
$\bold 0$ and $\bold{10}$, the block $\bold{11}$ 
are the fatal hits. Notice that $\{\bold 0,\bold{10}\}^*$ are
exactly the admissible blocks in the Fibonacci expansion of integers 
({\sl Zeckendorf\/}
expansion, cf.\cite{13}). Accordingly, the generating function
$$
\frac{p^2z^2}{1-qz-pqz^2}\tag 1.1
$$
has as the coefficient of $z^x$ the probability 
$\Bbb P \{X=x\}$
that the lifetime $X$ of a player is exactly $x$.
The generating function \thetag{1.1} is known in the context of the
Fibonacci distribution or geometric distribution of order $2$, cf. \cite{1},
\cite{3}, \cite{4}, \cite{7}, \cite{8}, \cite{10}, \cite{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 \cite{5}, \cite{11}.)

We have obviously
$$
\Bbb P\Big\{\max\{X_1,\dots,X_n\}\le x\Big\}=\Big(\Bbb P\{X\le 
x\}\Big)^n.\tag1.2
$$
The generating function of $\Bbb P\{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\quad\text{and}
\quad b=\frac{q-\sqrt{q^2+4pq}}2.$$
Performing the partial fraction decomposition and extracting coefficients
yields
$$\Bbb P\{X>x\}=\frac1{\sqrt{q^2+4pq}}\(a^x(a+p)-b^x(b+p)\).$$

Using \thetag{1.2} we obtain the expectation for the maximum lifetime of $n$ 
players
$$\aligned\Bbb E_n&=\Bbb E\max\big\{X_1,\dots,X_n\big\}\cr
&=\sum_{x\geq0}\(1-\bigg(1-\frac1{\sqrt{q^2+4pq}}
\(a^x(a+p)-b^x(b+p)\)\bigg)^n\).\endaligned\tag1.3$$
By the binomial theorem we obtain
$$\Bbb E_n=\sum_{m=1}^n(-1)^{m-1}{n\choose 
m}\sum_{x\geq0}\(Aa^x-Bb^x\)^m,\tag1.4$$
where we use the notation
$$A=\frac{a+p}{\sqrt{q^2+4pq}}
=\frac{a^2}{q\sqrt{q^2+4pq}}
\quad\text{and}
\quad B=\frac{b+p}{\sqrt{q^2+4pq}}=\frac{b^2}{q\sqrt{q^2+4pq}}.$$
For example, in the symmetric case $p=q=\frac12$ we have
$a=\frac{1+\sqrt5}4$, $b=\frac{1-\sqrt5}4$, $A=\frac{5+3\sqrt5}{10}
$ and $B=\frac{5-3\sqrt5}{10}$.

We will find that $\Bbb E_n\sim \log_{1/a}n$ and refer for the (technical)
proof and a more precise statement to the next section.

\heading 2. Asymptotic Analysis\endheading

In \thetag{1.4} we found the expression
$$\Bbb E_n=\sum_{m=1}^n(-1)^{m-1}{n\choose  m}f(m),\tag2.1$$
containing the function
$$f(z)=\sum_{x\geq0}\(Aa^x-Bb^x\)^z\quad\text{for}\quad\Re z>0.$$
For an expression of that type we can write a complex contour integral
$$\Bbb E_n=\frac1{2\pi i}\oint_\Cal C 
\frac{(-1)^nn!}{z(z-1)\cdots(z-n)}f(z)\,dz,\tag2.2$$
where $\Cal C$ is a positively oriented Jordan curve encircling the points
$1,2,\ldots,n$ (and no other integer points); this can easily be checked by
residue calculus.

\vbox to 11 truecm{\hrule width 15 truecm height 0pt width 0pt
\vfill\special{picture contour scaled 750}}
\centerline{\smc The contours of integration}
\medskip

We will use Rice's method to obtain an asymptotic expansion for $\Bbb E_n$.
For this, we refer e.g. to \cite{2} and \cite{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 $\Re z>-\varepsilon$ for
$\varepsilon>0$ (we actually give an analytic continuation to the whole complex
plane).

Using the notation $C=\frac BA$ and $d=\frac ba$ (observe that $|C|<1$ and
$|d|<1$) we obtain
$$\aligned f(z)&=A^z\sum_{x\geq0}a^{xz}\(1-Cd^x\)^z
=A^z\sum_{x\geq0}a^{xz}\sum_{\ell\ge0}
(-1)^\ell C^\ell d^{x\ell}{z\choose\ell}\cr
&=A^z\sum_{\ell\ge0} (-1)^\ell C^\ell{z\choose\ell}\sum_{x\geq0}(a^zd^\ell)^x\cr
&=A^z\sum_{\ell\ge0}{z\choose \ell}
\frac{(-1)^\ell C^\ell}{1-a^zd^\ell},\endaligned\tag2.3$$
where the reversion of the order of summation was justified because of the 
absolute
convergence of the sum for $\Re 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^zd^\ell=0$. In the points $z_{\ell,x}=-\ell\frac{\log d}{\log a}+
\frac{2x\pi i}{\log a}$ with $\ell=0,1,\ldots$ and $x\in\Bbb Z$ there are simple
poles with residue
$$A^{z_{\ell,x}}{z_{\ell,x}\choose\ell}\frac{(-1)^{\ell-1}
 C^\ell}{\log a}.$$

In order to be able to deform the contour of integration we need an estimate
for $f(z)$ along the vertical line $\Re z=-u$. For this purpose
we write
$$f(z)-\frac{A^z}{1-a^z}=\sum_{x\geq0}A^za^{xz}\(\(1-Cd^x\)^z-1\)$$
and observe the inequality 
$\left|\big(1-Cd^x\big)^z-1\right|\leq\min(2,|z|Cd^x)$. This yields
$$\left|f(z)-\frac{A^z}{1-a^z}\right|\leq
A^{-u}\(\sum_{0\leq x\leq\log|z|}2|a|^{-xu}+|z|\sum_{x>\log|z|}a^{-xu}Cd^x\)\ll 
|z|^\alpha\tag2.4$$
for $|d|<a^u<1$ and $\alpha=-u\log a$.

We are now ready to start the deformation of the contour of integration: we take
$\Cal C'$ as the new contour and write
$$\aligned&\frac1{2\pi i}\oint_\Cal C 
\frac{(-1)^nn!}{z(z-1)\cdots(z-n)}f(z)\,dz=\frac1{2\pi i}\oint_{\Cal C'} 
\frac{(-1)^nn!}{z(z-1)\cdots(z-n)}f(z)\,dz\cr
&-\sum\Res_{z=z_i} \frac{(-1)^nn!}{z(z-1)\cdots(z-n)}f(z),\endaligned\tag2.5$$
where the summation runs over all poles $z_i$ between the curves $\Cal C$ and
$\Cal C'$. Notice that there is a second order pole at $0$. Computation of
residues yields (with $H_n=1+\frac12+\cdots+\frac1n$)
$$\aligned&\Res_{z=0}\frac{(-1)^nn!}{z(z-1)\cdots(z-n)}f(z)=
\frac1{\log a}H_n+\frac{\log A}{\log a}-\frac12\cr
&\Res_{z=\chi_x}\frac{(-1)^nn!}{z(z-1)\cdots(z-n)}f(z)=\frac{A^{\chi_x}}{\chi_x\
log a}
\frac{n!\Gamma(1-\chi_x)}{\Gamma(n+1-\chi_x)}\quad\text{for 
}x\not=0,\endaligned\tag2.6$$
where $\chi_x=\frac{2x\pi i}{\log a}=z_{0,x}$.

Shifting the upper, the lower and the right part of $\Cal C'$ (cf. the figure) 
to infinity and
observing, that the integrals over these parts of the contour vanish then, 
yields
$$\aligned\Bbb E_n&=\frac1{\log\frac1a}H_n-\frac{\log A}{\log a}+\frac12
-\sum_{x\in\Bbb Z\setminus\{0\}}\frac{A^{\chi_x}}{\chi_x\log 
a}\frac{n!\Gamma(1-\chi_x)}{\Gamma(n+1-\chi_x)}\cr
&-\frac1{2\pi 
i}\int\limits_{-u-i\infty}^{-u+i\infty}\frac{(-1)^nn!}{z(z-1)\cdots(z-n)}f(z)\,d
z.\endaligned\tag2.7$$
We now use the well-known asymptotic expansions $H_n= \log n+
\gamma+O(\frac1n)$ and
$\dfrac{n!}{\Gamma(n+1-\chi_x)}=n^{\chi_x}\(1+O(\frac{x^2}n)\)$ 
(by Stirling's formula)
to formulate our main
result.

\proclaim{Theorem 1} The expected maximal lifetime $\Bbb E_n$ 
of $n$ independent players each of which has the Fibonacci distribution
(or geometric distribution of order $2$)
fulfils for $n\to\infty$
$$\Bbb E_n=\log_{1/a}n-\frac{\gamma+\log A}{\log a}+
\frac12-\varphi(\log_{1/a}n)+O(n^{-u}),\tag2.8$$
for $0<u<\min(1,\frac{\log|d|}{\log a})$
%where the last term is obtained by a trivial estimate of the integral 
and $\varphi$
denotes a continuous periodic function of period $1$ and
mean $0$ given by the Fourier expansion
$$\varphi(t)=
\frac{1}{\log a}
\sum_{x\in\Bbb Z\setminus\{0\}}A^{\chi_x}\Gamma(-\chi_x)e^{2x\pi it}
=\frac{1}{\log a}
\sum_{x\in\Bbb Z\setminus\{0\}}\Gamma(-\chi_x)e^{2x\pi i(t-\log_{1/a}A)}
,\tag2.9$$
which is rapidly convergent due to the exponential decay of the 
$\Gamma$-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.
\endproclaim

\head 3. Extensions \endhead
Here, we briefly sketch the more general case where $k$ consecutive
hits are necessary to kill a player. In this case the probability $\Bbb P(X=x)$
was derived by Philippou and Muwafi \cite{9} in terms of multinomial 
coefficients.
As described in the introduction there
is a bijection to the sequences
$$\{\bold 0,\bold{10},\bold{110},\dots,\bold 1^{k-1}
\bold 0\}\cdot\bold1^{k},$$
which yield the probability generating function
$$\frac{p^kz^k}{1-qz-pqz^2-\cdots-p^{k-1}qz^k}
=\frac{p^kz^k(1-pz)}{1-z+qp^kz^{k+1}}\tag3.1$$
for the lifetime of a player (cf. \cite{1, pp. 299ff}, \cite{3, p. 428},
\cite{7, p. 207}, \cite{8}). 
Likewise, the generating function of $\Bbb P\{X>x\}$ is given by
$$\frac{1-p^kz^k}
{1-z+qp^kz^{k+1}}\tag3.2$$
Again we factor the
polynomial in the denominator
$$1-qz-pqz^2-\cdots-p^{k-1}qz^k=(1-\alpha z)(1-\alpha_2z)\cdots(1-\alpha_kz)$$
with $|\alpha|>|\alpha_2|\geq\cdots\geq|\alpha_k|$ ($\alpha>0$). Then we have
by partial fraction decomposition and extracting coefficients
$$\Bbb P\{X>x\}=A\alpha^x+A_2\alpha_2^x+\cdots+A_k\alpha_k^x\tag3.3$$
with
$$A=\frac{\alpha(\alpha-p)}{q((k+1)\alpha-k)}$$
and similar expressions for $A_2,\dots,A_k$.

For the expectation of the maximal lifetime of $n$ players we obtain
$$\Bbb E_{n,k}=\Bbb E\max\{X_1,\ldots,X_n\}=\sum_{m=1}^n(-1)^{m-1}{n\choose 
m}g(m)$$
with
$$g(z)=\sum_{\ell\geq0}\(A\alpha^\ell+\cdots+A_k\alpha_k^\ell\)^z
\quad\text{for }\Re z>0.$$
For the purpose of analytic continuation of $g$ we consider
$$g(z)-\frac{A^z}{1-\alpha^z}$$
and proceed as in \thetag{2.4} to obtain the continuation and a polynomial
estimate for $g(z)$ along some vertical line $\Re z=-\varepsilon$ for 
sufficiently 
small $\varepsilon>0$.

We are now ready to perform similar calculations as in Section 2. Thus we obtain
\proclaim{Theorem 2} The expected maximal lifetime $\Bbb E_{n,k}$ of $n$ players
each of which has geometric distribution of order $k$ satisfies
$$\Bbb E_{n,k}=\log_{1/\alpha}n-\frac{\gamma+\log A}{\log\alpha}+\frac12+
\psi\(\log_{1/\alpha}n\)+O(n^{-\varepsilon}),$$
for $0<\varepsilon<\min(1,\frac{\log|\alpha_2|}{\log\alpha})$ and a continuous
periodic function $\psi$ of period $1$ and mean $0$ whose Fourier expansion is
given by
$$\psi(t)=\frac{1}{\log \alpha}
\sum_{x\in\Bbb Z\setminus\{0\}}A^{\chi_x}\Gamma(-\chi_x)e^{2x\pi it}
=\frac{1}{\log \alpha}
\sum_{x\in\Bbb Z\setminus\{0\}}\Gamma(-\chi_x)e^{2x\pi i(t-\log_{1/\alpha}A)},$$
where $\chi_x=\frac{2x\pi i}{\log\alpha}$.
\endproclaim

By {\sl bootstrapping\/} we find that, for $k\to\infty$,
$$
\alpha\sim1-qp^k+\dots\quad\text{and}\quad A\sim 1+kqp^k+\dots\,
.$$
\Refs

\ref\no 1\by W. Feller\book An Introduction to Probability Theory and Its
Applications\vol 1\publ J. Wiley\publaddr New York\yr 1957\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 N.L. Johnson, S. Kotz and A.W. Kemp\book Discrete Univariate
Distributions\publ Wiley\publaddr New York\yr 1992\endref
\ref\no 4\by A.W. Kemp\paper Second-Order Linear Recurrence Distributions and
Their Properties\jour manuscript\endref
\ref\no 5\paper A Result in Order Statistics Related to Probabilistic
Counting\jour submitted \by P.Kirschenhofer and H.Prodinger\yr 
1992\endref
\ref\no 6
\by D.E.Knuth 
\book The Art of Computer Science Vol.3\publ
Addison-Wesley \yr 1973 \publaddr Reading, MA \endref
\ref\no 7\by A.N. Philippou\paper Distributions and Fibonacci Polynomials of
Order $k$, Longest Runs, and Reliability of Consecutive-$k$-out-of-$n$: $F$
Systems\inbook Fibonacci Numbers and Their Applications\eds A.N.~Philippou,
G.E. Bergum and A.F. Horadam\pages 203--227\publ Reidel\publaddr Dordrecht
\yr 1986\endref
\ref\no 8\by A.N. Philippou, C. Georghiou and G.N. Philippou\paper A Generalized
Geometric Distribution and Some of Its Properties\jour Stat. and Probab. Letters
\vol 1\pages 171--175\yr1983\endref
\ref\no 9\by A.N. Philippou and A.A. Muwafi\paper Waiting for the $k$-th
Consecutive Success and the Fibonacci Sequence of Order $k$\jour Fibonacci
Quarterly\vol 20\pages 28--32\yr1982\endref
\ref\no 10\by H.D. Shane\paper A Fibonacci Probability Function\jour Fibonacci
Quarterly\vol 11\pages 517--522\yr1973\endref
\ref\no 11\by W.Szpankowski and V.Rego \jour Computing\vol 43
\pages 401--410 \yr 1990 \paper Yet another Application of a
Binomial Recurrence: Order 
Statistics\endref
\ref\no 12\by C. Taillie and G.P. Patil\paper The Fibonacci Distribution 
Revisited
\jour Communications in Statistics -- Theory and Methods\vol 15\pages 
951--959\yr 1986\endref
\ref\no 13\by E. Zeckendorf\paper Repr\'esentations des nombres naturels par une
somme des nombres de Fibonacci ou des nombres de Lucas\jour Bull. Soc. Royale
Sci. Li\`ege\vol41\pages 179--182\yr1972\endref

\endRefs



\enddocument



