%Annals of Applied Probability

\input amstex
\documentstyle{amsppt}



\TagsOnRight
\headline=               
{\ifnum\pageno=1\hfil
 \else\vbox{\line {\tenit The Number of Winners
 \hfil\tenrm\number\pageno}
\vskip 2pt\hrule}\fi}
\footline={\hfil}
\catcode`\@=11
\redefine\logo@{}
\firstpage@false
\catcode`\@=13

\topmatter
\redefine\L{\log 2}

\title 
the number of winners in a discrete geometrically distributed sample
\endtitle
\author Peter Kirschenhofer and Helmut Prodinger \endauthor
\affil 
Department of Algebra and Discrete Mathematics 
Technical University of Vienna, Austria
\endaffil
\keywords Geometric distribution, generating functions, Rice's method
\endkeywords
\subjclass 60\, C\, 05 
 \endsubjclass
\address
 TU Vienna\newline
 Wiedner Hauptstrasse 8-10\newline A-1040 Vienna\newline Austria
\endaddress 

\endtopmatter

\def \P{\Bbb P}
\document
\baselineskip=2em

\heading
\endheading


Let the random variable $G$ be geometrically distributed, i.e.
$\P\{G=k\}=pq^{k-1}$, with $q=1-p$. Also, assume that $n$ independent
copies are given. Finally, let $X$  count the number
of winners, i.e. the number of random variables with highest value.
In  \cite{1} the probability distribution
of $X$, the expectation {\bf E}$X$ of $X$ and the asymptotic behaviour of
$\P\{X=1\}$ (probability of a single winner)
for $n\to\infty$
 was to be determined.
In the solution \cite{2} it was remarked that -- surprisingly -- this probability
does not converge as $n\to\infty$ but rather has an oscillating 
behaviour.
At the same time, 
 Eisenberg, Stengle and Strang \cite{5}
discussed 
this problem and related topics, exhibiting
the structure of the periodic fluctuation, for which an explicit
Fourier expansion was given. Also about this time, Brands, Steutel
and Wilms \cite{3} came independently to roughly the same results.
A recent paper due to Baryshnikov, Eisenberg and Stengle \cite{4}
deals with the existence of the limiting probability of a tie for first
place.

In fact, a fluctuating behaviour in asymptotic expansions is not at all
uncommon. There are numerous results of that type, e.g. in the analysis
of divide--and--conquer recursions \cite{7, 8, 16}
 or digital sums \cite{6},
to mention just some examples, that play a prominent role in the 
probabilistic analysis of algorithms.

Our aim in this paper is to some extent tutorial:
The asymptotic technique that yields the Fourier expansions of the 
fluctuating functions very comfortably is called ``Rice's method'', 
see the recent survey \cite{9}. In order to convince the reader of
the advantages of this method we will rederive some results on the
initially mentioned problem in the sequel, and afterwards present some
new results concerning higher moments of distribution as well as
the number of persons reaching a specified level beyond the winner.








\bigskip

Let us abbreviate $Q:=1/q$ and $L:=\log Q$.
Let further $p_m$ denote the probability $p_m=\P\{X=m\}$, i.e. the
probability to have $m$ winners (amongst $n$ players).
Then
$$
p_m=p^m\binom{n}{m}\sum_{j\ge1}q^{(j-1)m}\big(1-q^{j-1}\big)^{n-m}.
$$
This follows from the observation that $m$ out of $n$ people have a
(winning) value $j$, while the other ones have a smaller value. Now
we set $N:=n-m$, expand the binomial and sum over $j$ to get the alternative
$$
p_m=p^m\binom{n}{m}\sum_{k=0}^N\binom{N}{k}(-1)^k\frac{1}{1-Q^{-k-m}}.
\tag1
$$
The key point in analyzing this alternating sum asymptotically
is the 
following Lemma.
\bigskip
\proclaim{Lemma} {\rm \cite{9}}
Let $f(z)$ be a function that is analytic on $[n_0,+\infty[$.
Assume that $f(z)$ is meromorphic in the whole of $\Bbb C$ and analytic
on $\Omega=\bigcup_{j=1}^\infty \gamma_j$ where the $\gamma_j$ are
concentric circles whose radius tends to infinity. Let $f(z)$ be of
polynomial growth on $\Omega$. Then, for $n$ large enough, 
$$
\sum_{k=n_0}^n \binom nk \, {(-1)}^k f(k)=
\sum_{z}\text{{\rm Res}} [n;z] f(z)~,
\tag2
$$
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
$$
and the sum is extended to all poles not on $[n_0,+\infty[$.


\endproclaim
Extending the contour of integration to the left it turns out that,
under suitable growth conditions on $f(z)$ (which are fulfilled in all
our examples), an asymptotic equivalent of \thetag2 is given by the residues
of $[n;z]f(z)$ at the additional poles.

In our example we only have to consider the residues
of
$$[N;z]\frac{1}{1-Q^{-z-m}}$$
left of the line $\Re z=0$. They are at $z=-m+\chi_j$, with
$\chi_j=\frac{2j\pi i}{L}$. The computation of the residues is simple;
$$
\text{Res}_{z=-m+\chi_j}=n^{\chi_j}\frac{
\Gamma(N+1)
\Gamma(N+1+m-\chi_j)}{m!}\frac 1L,
$$
whence we have 
(after multiplication by the 
factor $p^m\binom{n}{m}$ and going back to $n$ instead of $N$)
the asymptotic formul\ae\ (for $m$ fixed and $n\to\infty$)
$$
p_m=\frac 1L\frac{p^m}{m!}\sum_{j\in \Bbb Z}
\frac{\Gamma(n+1)}{\Gamma(n+1-\chi_j)}\Gamma\left(m-\chi_j\right)+
\text{smaller order terms}.\tag3
$$
It is often convenient to pull out the term with index $j=0$ (the
``mean'') and give a name to the remaining
periodic fluctuation (of mean zero),
$$
\delta_m(x)=\frac{1}{m!}\sum_{j\ne 0}\Gamma(m-\chi_j)e^{2j\pi ix}.
$$
This is a continuous,  periodic function of period 1,
(integral) mean zero and small amplitude
(for $m$ not too large, compare the discussion in \cite{12}), and we can thus
write
$$
p_m\sim \frac 1L\frac{p^m}{m}+\frac{p^m}{L}\delta_m(\log_Qn)+\Cal O\big(\frac
1n\big),\quad m \text{ fixed }, n\to\infty.\tag4
$$

It is interesting to note that the alternating sum \thetag1 can also
be rewritten using the partial fraction decomposition of the meromorphic
function $\frac{1}{1-q^{z+m}}$, namely (compare \cite{11, 7.10})
$$
\frac{1}{1-q^{z+m}}=\frac12+\frac{1}{L}\sum_{j\in\Bbb Z}\frac{1}{z+m
+\chi_j},\quad\text{with } \chi_j=\frac{2j\pi i}{L}.\tag5
$$
Inserting \thetag4 into \thetag1 we find
$$
p_m=p^m\binom{n}{m}\sum_{k=0}^N\binom{N}{k}(-1)^k\frac12+\frac1L
p^m\binom{n}{m}\sum_{j\in\Bbb Z}\sum_{k=0}^N\binom{N}{k}(-1)^k
\frac{1}{k+m+\chi_j}
.$$
Now for  $x\in \Bbb C\setminus\{-N,\dots,0\}$
$$
\sum_{k=0}^N\binom{N}{k}(-1)^k\frac{1}{k+x}=\frac{\Gamma(N+1)\Gamma(x)}{
\Gamma(N+1+x)}=\frac{N!}{(N+x)_{N+1}}
$$
(compare \cite{10, (5.41)}), so that (remembering $N=n-m$)
$$\aligned
p_m&=\frac{p^m}{2}\delta_{n,m}+\frac{1}{L}\frac{p^m}{m!}\sum_{j\in\Bbb Z}
\frac{n!}{(m+\chi_j)\dots(n+\chi_j)}\\
&=\frac{p^m}{2}\delta_{n,m}+\frac{1}{L}\frac{p^m}{m!}\sum_{j\in\Bbb Z}
{\Gamma(m-\chi_j)}\frac{\Gamma(n+1)}{\Gamma(n+1-\chi_j)}
.\endaligned\tag6
$$
From \thetag6 we may conclude that the smaller order terms from expansion
 \thetag3 equal zero in fact.



Now let us consider the expectation,
$$\aligned
\text{E}_n&=\sum_{m\ge1}mp_m\\
&=n\sum_{m\ge1}\binom{n-1}{m-1}p^m\sum_{j\ge0}q^{jm}\left(1-q^j\right)^{n-m
}\\
&=\frac{np}{q}\sum_{j\ge0}q^{j+1}
\left(1-q^j\right)^{n-1}\sum_{m\ge0}\binom{n-1}{m}
\left(\frac{pq^j}{1-q^j}\right)^m\\
&=\frac{np}{q}\sum_{j\ge1}q^{j}(1-q^j)^{n-1}\\
&=(Q-1)n\sum_{k=0}^{n-1}\binom{n-1}{k}(-1)^k\frac{1}{Q^{k+1}-1}\\
&=Q(p_1-p\delta_{n,1}).
\endaligned
$$

From \thetag3 we conclude the asymptotic formula
$$
E_n=\frac pq\frac1L\Big(1+\delta_1(\log_Qn)\Big)+\Cal O\big(\frac1n\big).\tag7
$$
This computation was already reported in \cite{2}. Let us now engage 
in the computation of the {\sl variance}, which seems to be new.

For this we compute the second factorial moment $M_n$ for $n\ge2$:
$$\aligned
M_n&=\sum_{m\ge2}m(m-1)p_m\\
&=n(n-1)\sum_{m\ge2}\binom{n-2}{m-2}p^m\sum_{j\ge0}q^{jm}\left(1-q^j\right)^{n-m
}\\
&=\frac{n(n-1)p^2}{q^2}\sum_{j\ge1}q^{2j}
\left(1-q^j\right)^{n-2}\\
&=\frac{n(n-1)p^2}{q^2}\sum_{k=0}^{n-2}\binom{n-2}{k}(-1)^k\frac{1}{
Q^{k+2}-1}\\
&=2Q^2p_2-2\frac{p^2}{q^2}\delta_{n,2}=2Q^2(p_2-p^2\delta_{n,2}).
\endaligned\tag8
$$
The variance is obtained in the usual way by computing
$V_n=M_n+E_n-E_n^2$. Hence
$$
V_n=\frac{p^2}{q^2}\frac{1}{L}+\frac pq\frac1L-
\frac{p^2}{q^2}\frac{1}{L^2}+\tau(\log_Qn)+\Cal O\big(\frac{1}{n}\big).
\tag9
$$
This time
$\tau(x)=\frac{p^2}{q^2}\frac{2}{L}\delta_2(x)+\frac{p}{q}
\frac{1}{L}\delta_1(x)-\frac{p^2}{q^2}\frac{1}{L^2}\delta_1^2(x)
$
has (integral)
mean {\sl different} from zero! While this quantity is quite small,
it can be extracted using the methods described in \cite{13}, and we find
the alternative 
$$
\text{V}_n=\frac{p}{q^2}\frac{1}{L}
-\frac{p^2}{q^2}\frac{1}{L}\bigg(2
\sum_{j\ge1}\frac{Q^j}{(Q^j+1)^2}+\frac14\bigg)+
\tau_1(\log_Qn)+\Cal O\big(\frac{1}{n}\big),\tag10
$$
where the function $\tau_1(x)$ has now mean zero.


\bigskip

There is a nice way to derive the explicit forms of the expectation
and the second factorial moment, using  generating functions.
Let the coefficient of $z^k$ in $F_n(z)$ denote the probability that
$n$ player produce $k$ winners. We get the following recursion
$$
F_n(z)=\sum_{k=1}^n\binom{n}{k}p^{n-k}q^kF_k(z)+p^nz^n, \qquad n\ge1.
\tag11
$$
It is convenient to set $F_0(z)=1$. This recursion is almost 
selfexplanatory. When at a certain level the remaining players all fail,
we label each of them by a ``$z$'' and leave the recursion.
The expectation $E_n$ is obtained via $F'_n(1)$; therefore
$$
E_n=\sum_{k=1}^n\binom{n}{k}p^{n-k}q^k{E}_k+np^n, \qquad n\ge1.
$$
Define the exponential generating function
$$
E(z)=\sum_{n\ge0}E_n\frac{z^n}{n!},
$$
then we obtain
$$
E(z)=e^{pz}E(qz)+pze^{pz},
$$
which will be easier by using the ``Poisson transform''
$$
\hat E(z)=e^{-z}E(z)=\sum_{n\ge0}\hat{ {E}}_n\frac{z^n}{n!};
$$
$$
\hat E(z)=\hat E(qz)+pze^{-qz}.
$$
Equating coefficients we see, that, for $n\ge1$,
$$
\hat{{ E}}_n=\frac{np}{q}(-1)^{n-1}\frac{q^n}{1-q^n}
$$
and furthermore for $n\ge1$
$$\aligned
{E}_n&=\sum_{k=0}^n\binom{n}{k}\hat{{E}}_k\\
&=\sum_{k=1}^n\binom{n}{k}\frac{kp}{q}(-1)^{k-1}\frac{1}{Q^k-1}\\
&=\frac{np}{q}\sum_{k=0}^{n-1}\binom{n-1}{k}(-1)^k
\frac{1}{Q^{k+1}-1}.
\endaligned
$$
For the second factorial moment we have to derive twice, and evaluate
at $z=1$. An almost identical computation gives  the same
expression that we obtained already.

This approach was used by Knuth in \cite{15} under the name
``binomial transform'' and subsequently used by many people, see 
for instance \cite{17}.

\bigskip

Finally we want to produce some new results which shed some 
additional light on  the original question about the number of winners.

Assume that the winners have reached the level $j$. We are interested in
the number of people who reached the level $j-d$, where $d$ is a parameter.
($d=0$ is the case that was just considered.)
Call the random variable in question $X_d$. Then we have 
$$\aligned
&\P\{X_d=m_d\}\\ &=\sum\sum_{j\ge d+1}\binom{n}{m_0,\dots,m_d,\mu
}\big(pq^{j-1}\big)^{m_0}\dots
\big(pq^{j-d-1}\big)^{m_d}\Big(1-q^{j-d-1}\Big)^{\mu},
\endaligned\tag12
$$
where the first sum runs over all $m_0\ge1$, $m_1\ge0$,\dots,
$m_{d-1}\ge0$ and $\mu=n-m_0-\dots-m_d$.
 The expected value is just the sum of $m_d$ times
this quantity. We get
$$\aligned
{E}_n^{(d)}&=n\sum_{j\ge d+1}pq^{j-d-1}
\bigg[
\Big(pq^{j-1}+\dots+pq^{j-d-1}+1-q^{j-d-1}\Big)^{n-1}\\ & \qquad \qquad
\qquad\qquad -
\Big(pq^{j-2}+\dots+pq^{j-d-1}+1-q^{j-d-1}\Big)^{n-1}
\bigg]
\\
&=pn\sum_{j\ge d+1}q^{j-d-1}\left[
\big(1-q^j\big)^{n-1}-\big(1-q^{j-1}\big)^{n-1}
\right]
\\
&=\frac{p^2}{q^{d+1}}n\sum_{j\ge d}q^j\big(1-q^j\big)^{n-1}-
\frac{p}{q}n
\big(1-q^d\big)^{n-1}.
\endaligned
$$
This formula holds only for $d\ge1$. Since
$$
{E}_n^{(0)}=E_n=n\frac pq \sum_{j\ge1}q^j\big(1-q^j\big)^{n-1},
$$
we find
$$
{E}_n^{(d)}=\frac{p}{q^d}{E}_n^{(0)}-\frac{p^2}{q^{d+1}}n
\sum_{j=1}^{d-1}q^j\big(1-q^j\big)^{n-1}-\frac{p}{q}n\big(1-q^d\big)^{n-1},
\tag13
$$
and, since the extra terms are exponentially small, we can use the
asymptotic result for $E_n^{(0)}$ and have
$$\aligned
{E}_n^{(d)}&=\frac{p}{q^{d+1}}p_1\qquad (n\ge2)\\
&=\frac{1}{L}\frac{p^2}{q^{d+1}}+\frac{1}{L}\frac{p^2}{q^{d+1}}
\delta_1(\log_Qn)+\Cal O \big(\frac1n\big)\qquad (n\to\infty).
\endaligned\tag14
$$
The second factorial moment $M_n^{(d)}$ is computed analogously as
$(d\ge1)$
$$\aligned
M_n^{(d)}&=n(n-1)\sum_{j\ge d+1}\left(pq^{j-d-1)}\right)^2\left[
\left(1-q^j\right)^{n-2}-\left(1-q^{j-1}\right)^{n-2}\right]\\
&=\frac{p^3}{q^{2d+2}}n(n-1)\sum_{j\ge d}q^{2j}\left(1-q^j\right)^{n-2}
-\frac{p^2}{q^2}n(n-1)\left(1-q^d\right)^{n-2}\\
&=\frac{p}{q^{2d}}+ \text{exponentially small terms in $n$},
\qquad n\to\infty.
\endaligned\tag15
$$
(with $M_n^{(0)}=M_n$ from above). Altogether we find for the
variance
$$
V_n^{(d)}=\frac{p^2}{q^{2d+2}}\frac1L\left(1+q^{d+1}\right)-
\frac{p^4}{q^{2d+2}}\frac1L\bigg(
2\sum_{j\ge1}\frac{Q^j}{(Q^j+1)^2}+\frac14\bigg)+\tau_1^{(d)}(\log_Qn)
+\Cal O\big(\frac1n\big).\tag16
$$
















\Refs

\ref \no1\by E3436 (Problem)\jour American Mathematical Monthly
\vol99\yr1991\pages 366
\endref

\ref \no2\by E3436 (Solution)\jour American Mathematical Monthly
\vol101\yr1994\pages 78--80
\endref

\ref \no3 \by J.J.A.M.Brands, F.W.Steutel, and R.J.G.Wilms
\paper
On the number of maxima in a discrete sample
\jour Statistics and Probability Letters\vol20\yr1994\pages209--217
\endref


\ref \no4 \by Y. Baryshnikov, B.Eisenberg, and G.Stengle\paper
A necessary and sufficient condition for the existence of the limiting
probability of a tie for first place
\jour Statistics and Probability Letters \yr 23 \yr 1995\pages 
203--209
\endref






\ref \no5 \by B.Eisenberg, G.Stengle, and G.Strang\paper
The asymptotic probability of a tie for first place
\jour Annals of Applied Probability\vol3\yr1993\pages731--745
\endref

\ref \no 6 \paper Mellin Transforms and Asymptotics: Digital Sums
 \by P.Flajolet, P. Grabner, 
P.Kirschenhofer, H.Prodinger and R.F.Tichy \jour Theoretical Computer Science
\vol 123\pages 291--314\yr 1994
\endref

\ref \no 7 \by  P.Flajolet and L.B.Richmond
\paper Generalized Digital Trees and Their Difference-Differential Equations
\jour Random Structures and Algorithms
\yr 1992 \pages 305--320        \vol 3      
\endref

\ref \no 8 \by P. Flajolet and R. Sedgewick \pages 748--767 \paper
Digital Search Trees Revisited \yr 1986 \vol 15 \jour SIAM J.Comput. 
\endref

\ref\no9 \by P.Flajolet and R.Sedgewick\paper Mellin transforms and asymptotics:
Finite differences and Rice's integrals \jour Theoret. Comput. Sci.
\toappear
\yr 1994
\endref

\ref\no10 \by R.Graham,  D.E.Knuth, and O.Patashnik
\book Concrete Mathematics 
 \publ Addison-Wesley \yr 1989
\endref

\ref\no 11\by P. Henrici\book Applied and 
Computational Complex Analysis, vol.1 
\publ J. Wiley\publaddr New York\yr 1977\endref

\ref \no 12 \paper
A Result in Order Statistics Related to Probabilistic
Counting
\jour Computing \vol 51\pages 15--27 \by P. Kirschenhofer and H.Prodinger
\yr 1993
\endref

\ref\no 13
\paper On Some Applications of Formul\ae of Ramanujan in the 
Analysis of Algorithms
\jour Mathematika \vol 38 \pages 14--33
 \yr 1991 \by P.Kirschenhofer and H.Prodinger
\endref

\ref \no 14   \paper On the Variance of the External Pathlength 
in a Symmetric Digital Trie 
\jour Discrete Applied Mathematics \yr 1989 \pages 129--143\vol 25
\by P.Kirschenhofer, H.Prodinger and W.Szpankowski 
\endref

\ref \no 15  \by D.E.Knuth \book The Art of Computer Programming,
Vol. 3 \publ Addison-Wesley \yr 1973 \endref

\ref \no 16 \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 17 \paper
A note on  binomial recurrences arising in the analysis of algorithms
 (Letter to the Editor)
\jour Information Processing Letters \vol46\yr 1993 \pages 309--311
\by H.Prodinger and W.Szpankowski
\endref

\ref \no 18\by W. Szpankowski \paper 
The Evaluation of an Alternative Sum with Applications to the Analysis
of Some Data Structures
\yr 1988 \pages 13--19
\jour Information Processing Letters \vol 28 \endref

\endRefs

\enddocument




