\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}
\newcommand{\T}[1]{\qquad\mbox{#1}\qquad}
\DeclareMathOperator{\Ext}{Ext}
\DeclareMathOperator{\mo}{mod}
\DeclareMathOperator{\Hom}{Hom}
\DeclareMathOperator{\dimv}{\textbf{dim}}
\newcommand{\MATRIX}[4]{\left[\begin{array}{cc}
#1 & #2 \\#3 & #4 \end{array}\right]} 

\def\polylog{\textrm{polylog}}
\newenvironment{probb}{ \begin{prob} \rm}{ \end{prob} }
\newcommand{\bprobb}{\begin{probb}}
\newcommand{\eprobb}{\end{probb}}
\newcommand{\bth}{\begin{theorem}}
\newcommand{\ethGL}{\end{theorem}}
\newcommand{\bconj}{\begin{conj}}
\newcommand{\econj}{\end{conj}}
\newcommand{\bkey}{\begin{key}}
\newcommand{\ekey}{\end{key}}
\newcommand{\bl}{\begin{lem}}
\newcommand{\el}{\end{lem}}
\newcommand{\bdeff}{\begin{deff}}
\newcommand{\edeff}{\end{deff}}
\newcommand{\bcor}{\begin{cor}}
\newcommand{\ecor}{\end{cor}}
\newcommand{\bprop}{\begin{prop}}
\newcommand{\eprop}{\end{prop}}
\newcommand{\brem}{\begin{rem}}
\newcommand{\erem}{\end{rem}}
\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}
\newcommand{\beqn}{\begin{eqnarray}}
\newcommand{\eeqn}{\end{eqnarray}}
\newcommand{\beqns}{\begin{eqnarray*}}
\newcommand{\eeqns}{\end{eqnarray*}}
\newcommand{\ba}{\begin{array}}
\newcommand{\ea}{\end{array}}
\newcommand{\bit}{\begin{itemize}}
\newcommand{\eit}{\end{itemize}}
%\newcommand{\bpr}{\begin{proof}}
%\newcommand{\epr}{\end{proof}}
\newcommand{\bpr}{\noindent{\bf Proof.\hspace{1em}}}
\newcommand{\epr}{\hfill\rule{3mm}{3mm}\vspace{\baselineskip}\\}
\newcommand{\B}{\mathcal{B}}
\newcommand{\BO}{{O}}
\newcommand{\BN}{\mathcal{N}}
\newcommand{\BF}{\mathcal{F}}
\newcommand{\BMC}{\mathcal{M}}
\newcommand{\non}{\nonumber}
\newcommand{\babs}{\begin{abstract}}
\newcommand{\eabs}{\end{abstract}}
\newcommand{\bal}{\begin{align}}
\newcommand{\bals}{\begin{align*}}
\newcommand{\bs}{\begin{skip}}
\newcommand{\eal}{\end{align}}
\newcommand{\eals}{\end{align*}}
\newcommand{\es}{\end{skip}}
\newcommand{\da}{\downarrow}
\newcommand{\ra}{\rightarrow}
\newcommand{\Lra}{\Leftrightarrow}


\newcommand{\BB}{\qquad}
\newcommand{\kl}{[\hspace{-0.5 mm}[}
\newcommand{\kr}{]\hspace{-0.5 mm}]}
\renewcommand{\l}{\left}
\renewcommand{\r}{\right}
\newcommand{\lp}{\left (}
\newcommand{\rp}{\right)}
\newcommand{\lb}{\left [}
\newcommand{\rb}{\right ]}
\newcommand{\TB}{\textbf}
\newcommand{\BU}{\mathbf{1}}
\newcommand{\BR}{\mathbf{R}}
\newcommand{\Bh}{\mathbf{h}}
\newcommand{\BD}{\mathbf{D}}
\newcommand{\BI}{\mathbf{I}}
\newcommand{\BM}{\mathbf{M}}
\newcommand{\BZ}{\mathbf{Z}}
\newcommand{\BS}{\mathbf{S}}
\newcommand{\BDd}{\mathbf{D^{(2)} }}
\def\ii{\mathbf{i}}
\newcommand{\Bmu}{\mbox{\boldmath$\mu$}} 
\newcommand{\Bpi}{\mbox{\boldmath$\pi$}}
\newcommand{\BPi}{\mbox{\boldmath$\Pi$}} 
\newcommand{\Bal}{\mbox{\boldmath$\al$}} 
\newcommand{\Bde}{\mbox{\boldmath$\de$}} 
\newcommand{\BFi}{\mbox{\boldmath$\Fi$}} 
\newcommand{\Bpsi}{\mbox{\boldmath$\psi$}} 
\newcommand{\Bchi}{\mbox{\boldmath$\chi$}} 
\newcommand{\Bpsid}{\mbox{\boldmath$\psi^{(2)}$}} 
\newcommand{\Bchid}{\mbox{\boldmath$\chi^{(2)}$}} 
\newcommand{\Bded}{\mbox{\boldmath$\de^{(2)}$}} 

\newcommand{\SSl}{\sum_{l=1}^\II}
\newcommand{\SSi}{\sum_{i=1}^\II}
\newcommand{\SSk}{\sum_{k=1}^\II}
\newcommand{\SSj}{\sum_{j=1}^\II}
\newcommand{\SSu}{\sum_{u=1}^\II}

\newcommand{\etasi}{\eta^{*i}}
\newcommand{\etas}{\eta^*}
\newcommand{\las}{\la^*}
\newcommand{\pis}{\pi^*}
\newcommand{\xis}{\xi^*}
\newcommand{\Pis}{\Pi^*}
\newcommand{\xs}{x^{*}}
\newcommand{\zs}{z^{*}}
\newcommand{\zsi}{z^{*i}}
\newcommand{\zsj}{z^{*j}}
\newcommand{\zsl}{z^{*l}}
\newcommand{\zsk}{z^{*k}}
\newcommand{\alt}{\tilde{\al}}
\newcommand{\zt}{\tilde{z}}
\newcommand{\ft}{\tilde{f}}
\newcommand{\FIt}{\tilde{\FI}}
\newcommand{\Lt}{\tilde{L}}
\newcommand{\pt}{\tilde{p}}

\newcommand{\Pt}{\tilde{P}}
\newcommand{\xt}{\tilde{x}}
\newcommand{\yt}{\tilde{y}}
\newcommand{\wt}{\tilde{w}}
\newcommand{\Ct}{\tilde{C}}
\newcommand{\Lb}{\bar{L}}
\newcommand{\hid}{h_i^{(2)}}
\newcommand{\Dd}{D^{(2)}}
\newcommand{\chid}{\chi^{(2)}}
\newcommand{\psid}{\psi^{(2)}}
\newcommand{\ded}{\de^{(2)}}
\newcommand{\xid}{\xi_i^{(2)}}
\newcommand{\tud}{3^{1/2}}
\newcommand{\ns}{n^*}
\newcommand{\chil}{\chi_l}
\newcommand{\Tet}{\Theta}
\newcommand{\de}{\delta}
\newcommand{\De}{\Delta}
\newcommand{\K}{\kappa}
\newcommand{\la}{\lambda}
\newcommand{\La}{\Lambda}
\newcommand{\al}{\alpha}
\newcommand{\be}{\beta}
\newcommand{\srt}{\sqrt{2}}
\newcommand{\srn}{\sqrt{n}}
\newcommand{\srpi}{\sqrt{\pi}}
\newcommand{\Fi}{\varphi}
\newcommand{\FI}{\phi}
\newcommand{\eps}{\varepsilon}
\newcommand{\II}{\infty}
\newcommand{\tet}{\theta}
\newcommand{\sig}{\sigma}
\newcommand{\sigd}{\sigma^2}
\newcommand{\Sig}{\Sigma}
\newcommand{\gam}{\gamma}
\newcommand{\Gam}{\Gamma}
\newcommand{\om}{\omega}
\newcommand{\Om}{\Omega}
\newcommand{\ta}{\tau}
\newcommand{\Up}{\Upsilon}

\def\1{{\ifmmode 1\mskip-1.5\thinmuskip\mathrm{l}%
        \else\textrm{1\hskip -.23em l}\fi}}
\newcommand{\conv}{\stackrel{\mathcal{D}}{\sim}} 
\newcommand{\equ}{\stackrel{\mathcal{D}}{\equiv}} 
\newcommand{\Z}{\mbox{$\mathbb Z$}} 
\newcommand{\E}{\mbox{$\mathbb E$}} 
\newcommand{\V}{\mbox{$\mathbb V$}} 
\def\P{{\mathbb {P}}} 
\def\Pr{{\mathbb {P}}} 
\newcommand{\bib}{\bibliographystyle{plain} \bibliography{biblio}} 
\newcommand{\dilog}{\mathrm{dilog}}


\newcommand{\biindice}[3]
{\renewcommand{\arraystretch}{0.6}
\begin{array}[t]{c}
#1\\
{\scriptstyle #2}\\
{\scriptstyle #3}
\end{array}
\renewcommand{\arraystretch}{1}
}
\newcommand{\bin}[2]
{
{#1\choose #2}
}
\newcommand{\St}[2]
{
\left [ \ba{c}#1\\#2 \ea \right]
}
%BProdinger
\def\j{\bold{j}}
\def\fl#1{\left\lfloor#1\right\rfloor}
\def\a{\alpha}
\def\qf#1#2{(#1;q)_{#2}}
\def\la{\lambda}
\def\bu{\mathbf{u}}
%EProdinger

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf 
The Largest Missing Value in a Composition \\
\vskip .03in
of an Integer and Some Allouche-Shallit-Type  \\
\vskip .11in
Identities
}
\vskip 1cm
\large
Guy Louchard\\
Universit\'e Libre de Bruxelles\\
D\'epartement d'Informatique, CP 212\\
Boulevard du Triomphe \\
B-1050 Bruxelles\\ 
Belgium\\
\href{mailto:louchard@ulb.ac.be}{\tt louchard@ulb.ac.be}\\
\ \\
Helmut Prodinger\\
University of Stellenbosch\\
Mathematics Department\\
7602 Stellenbosch\\ 
South Africa\\
\href{mailto:hproding@sun.ac.za}{\tt hproding@sun.ac.za}
\end{center}

\vskip .2 in

\centerline{\sl Dedicated to Jean-Paul Allouche on the occasion of his 60th birthday.}

\begin{abstract}
Archibald and Knopfmacher recently considered the largest missing value
in a composition of an integer and established the mean and variance.
Our alternative, probabilistic  approach  produces (in principle)
\emph{all} moments {in an almost automatic way}. In order to show that
our forms match the ones given by Archibald and Knopfmacher, we have to
derive some identities which are interesting on their own. We construct 
a one-parameter family of identities, and the first one is (equivalent to)
the celebrated identity due to Allouche and Shallit. We finally provide
a simple direct analysis of the $\textrm{LMV}(-1)$ case: if the largest
missing value is exactly one smaller than the largest value, we say
that the sequence has the $\textrm{LMV}(-1)$ property.
\end{abstract}


\section{Introduction}\label{S1}

Our attention was recently attracted by a paper by M.~Archibald and
A.~Knopfmacher~\cite{AK10} about some asymptotic properties of a
sequence of $n$ geometric independent identically distributed random
variables, with distribution $pq^{j-1}$, $q:=1-p$. In the particular
case $p=1/2$, (which is related to compositions of integers, see
below), and using generating functions techniques,  the authors study
the asymptotic mean and variance of  largest missing value (if it
exists). If the \textbf{l}argest \textbf{m}issing \textbf{v}alue is
exactly one smaller than the largest value, they say that the sequence
has the $\textrm{LMV}(-1)$ property.  They compute the
$\textrm{LMV}(-1)$ probability, and the corresponding mean value.

Here, within our alternative and more powerful approach, we think about
an urn model, with urns labelled $1,2,\ldots$, the probability of each
ball falling into urn $j$ being given by $pq^{j-1}$. In this
probabilistic urn model, we throw $n$ balls, and
have the following properties, which we collect below although the
full relevance of them will only appear later in the text.
\bit
\item We have asymptotic independence of urns, for all events related to urn $j$, $j=\BO(\log n)$. This is proved, by Poissonization-DePoissonization, in  \cite{LP05}, \cite{ALP05}  and \cite{HL00} (in this paper for $p=1/2$, but the proof is easily adapted). The error term is $\BO(n^{-C})$ where $C$ is a positive constant.
\item We obtain asymptotic distributions of the  random variables (RV) of interest. The number  of balls in urn $j$, $j=\BO(\log n)$ is now Poisson-distributed with parameter $(np/q) q^j$.  The asymptotic distributions are related to Gumbel distribution functions or convergent series of such. The error term is  $\BO(n^{-1})$. 
%
\item We have uniform integrability for the moments of our RV. To show that the limiting moments are equivalent to the moments of the limiting 
distributions, we need a suitable rate of convergence. This is related to a uniform integrability condition
(see Lo\`{e}ve \cite[Section~11.4]{LO63}). For the kind of limiting distributions we consider here, the  rate of convergence is analyzed in detail
 in \cite{LP04, ALP05}. The error term is  $\BO(n^{-C})$. 
 \item Asymptotic expressions for the moments are obtained by Mellin transforms. The error term is  $\BO(n^{-C})$. 
 \item $\Gam(s)$ decreases exponentially in the direction  $i\II$ (\cite{AS65}):
\[|\Gam( \sig+it )| \sim \sqrt{2\pi}|t|^{\sig-1/2}e^{-\pi |t|/2}.\]
Also, we have a ``slow increase property'' for all other functions we encounter. So inverting the Mellin transforms is easily justified.
\eit
{We proceed as follows: from the asymptotic properties of the urns, we obtain the asymptotic distributions of our RV of interest. Next we compute the Laplace transform $\FI(\al)$ from which we can derive the dominant part of probabilities and moments as well as the (tiny) periodic part in the form of a Fourier series}.

If we compare the approach in this paper with other ones that appeared previously (related to similar problems), then
we notice the following. Traditionally, one would stay with exact enumerations as long
as possible, and only at a late stage move to asymptotics. Doing this, one would, in terms
of asymptotics, carry many unimportant contributions around, which makes the computations
quite heavy, especially when it comes to higher moments. Here, however, approximations are
carried out as early as possible, and this allows for streamlined (and often automatic)
computations of the higher moments. 

The paper is organized as follows: in Section \ref{S11}, we consider  compositions of an integer. Section \ref{S2} is devoted to a first computation of the dominant part of  the moments. In Section \ref{S3}, we analyze the periodicities and  we briefly consider the conditioning  on the event that there exists a largest missing value. Section \ref{S5} contains the main result of this paper: we present some 
general Allouche-Shallit-type formulas\footnote{We
were kindly informed by  Allouche that the first forms of
the identities in question are due to Woods and Robbins~\cite{Woods,
Robbins}. However, Allouche and Shallit greatly extended them and made
them into what they are today, thanks to the great book~\cite{ALS}.
Thus, also, since this is the birthday volume for Jean-Paul Allouche,
we took the liberty to use the term Allouche-Shallit-type identities.}
and the direct moments computations. Section \ref{S6} is devoted to the $\textrm{LMV}(-1)$ case and Section \ref{S7} concludes the paper.
%
\section{Compositions of an integer}\label{S11}
%
Let us  consider the composition of an integer $\upsilon$ with $n$ parts,
 i.e., $\upsilon=\sum_{i=1}^n x_i$, where $x_i$ are natural numbers. Considering all compositions as equiprobable, we
know (\cite{HL00}) that
the number of parts $n$ is asymptotically Gaussian, $\upsilon \ra \II$: 
\beq
 n \sim \BN\left(\frac{\upsilon}{2},\frac{\upsilon}{4}\right),                                         \label{E11}
\eeq
and that the part sizes
are asymptotically identically distributed as GEOM$(1/2)$ and \emph{independent}. All  distributions we analyze in this paper depend on $\log_2 n$.
 Hence, with (\ref{E11}), the same random variables  related to $\upsilon$ are asymptotically equivalent by replacing
$\log_2 n$ by $\log_2 \upsilon-1$ (\cite{HL00}). 

 We will consider the case $p=1/2$ and  use the following notations:
\bals
n&:=\mbox{number of balls},\ n\mbox{ large},  \\
\mathcal{P}(\la,u)&:=e^{-\la}\la^u/u!,\mbox{ (Poisson distribution)}, \\
\log &:=\log_2,\\
\eta &:=j-\log n,\\
L &:=\ln 2,\\
\alt &:=\al/L,\\
\chil &:=\frac{2l\pi \ii}{L}.
\end{align*}

Let $\B$ be the event that there exists a largest missing value, i.e., a maximal empty urn before the last non-empty urn. Following previous results of the authors~\cite{LP04}, let $J$ be the position of this maximal empty urn before the last non-empty urn. We have (here and in the sequel $\sim$ always denotes $\mathop{\sim}_{n \ra \II}$)
\bals
\P[J=j;\B]&\sim \Fi (\eta),\\
\Fi (\eta)&:=\exp(-e^{-L\eta})\sum_{r\geq 1}\prod_{i=1}^r \lb 1-\exp(-e^{-L(\eta+i)})\rb \exp(-e^{-L(\eta+r)}).
\end{align*}
 Here is the explanation: we recall that we  have i.i.d. geometrically distributed RVs, and that the urns are  asymptotically independent, for all events related to  urn $j$ containing $\BO(1)$ balls. 
Also the number  of balls in each such urn is now asymptotically Poisson-distributed with parameter $npq^{j-1}$ in  urn $j$. So the asymptotic number $\ell$ of balls in urn $j$ is given by 
\[\exp \lp -npq^{j-1}\rp \frac{\lp npq^{j-1}\rp^\ell}{\ell !},\]
and with $p=1/2$, $\eta=j-\log n$,
this is equivalent to $\mathcal{P}\lp e^{-L\eta},\ell\rp$. Here, urn $j$ is empty, we have $r\geq 1$ non-empty urns after urn $j$, and all urns after urn $j+r$ are empty. This leads to
\[\P[J=j;\B] \sim \mathcal{P}\bigl(  e^{-L\eta},0\bigr)\sum_{r\geq 1}\prod_{i=1}^r \lb 1- \mathcal{P}\bigl( e^{-L(\eta+i)},0\bigr)\rb 
\mathcal{P}\bigl( e^{-L(\eta+r)},0\bigr) .\] 
%
Following \cite{LP04} again, we now compute the Laplace transform (with the change of variables $y=e^{-L\eta}$):
\bal
\FI(\al)&=\int_{-\II}^\II e^{-\al \eta}\Fi (\eta) d\eta \non \\
&=\int_0^\II y^{-\alt}e^{-y}\sum_{r\geq 1}\prod_{i=1}^r \lb  1-e^{-ye^{-Li}}\rb e^{-ye^{-Lr}}\frac{dy}{Ly}                 \label{E12}\\
&=\int_0^\II y^{-\alt}e^{-y}\sum_{r\geq 1}\prod_{i=1}^r \lb  1-e^{-y2^{-i}}\rb e^{-y2^{-r}}\frac{dy}{Ly}. \non
\end{align}
Again by \cite{LP04}, we have, with
\bal
F_0(s)&:=\left. \FI(\al)\right|_{\al=-Ls},                                                 \label{E20}\\
\P(\B)&\sim \FI(0)+\sum_{l\neq 0}F_0(\chil)e^{-2 l\pi\ii\log n}.                                            \label{E21}
\end{align}
But, from \cite{LP05} and \cite{HK04}, we know that $\P(\B)=1/2$. 
{So we should first independently confirm that}
\begin{equation}
\FI(0)=\int_0^\infty e^{-y}\sum_{r\ge1}\prod_{i=1}^r\Big(1-e^{-y/2^i}\Big)e^{-y/2^r}\frac{dy}{Ly}=\frac12.                      \label{E1}
\end{equation}
To do that, set
\begin{equation*}
f_0(y):=\sum_{r\ge1}\prod_{i=1}^r\Big(1-e^{-y/2^i}\Big)e^{-y/2^r}.
\end{equation*}
Then
\begin{align*}
f_0(2y)&=\sum_{r\ge1}\prod_{i=1}^r\Big(1-e^{-y/2^{i-1}}\Big)e^{-y/2^{r-1}}\\
&=\sum_{r\ge0}\prod_{i=0}^{r}\Big(1-e^{-y/2^{i}}\Big)e^{-y/2^{r}}\\
&=(1-e^{-y})e^{-y}+\sum_{r\ge1}\prod_{i=0}^{r}\Big(1-e^{-y/2^{i}}\Big)e^{-y/2^{r}}\\
&=(1-e^{-y})e^{-y}+(1-e^{-y})\sum_{r\ge1}\prod_{i=1}^{r}\Big(1-e^{-y/2^{i}}\Big)e^{-y/2^{r}}\\
&=(1-e^{-y})e^{-y}+(1-e^{-y})f_0(y).
\end{align*}
%
Now
\begin{align*}
G_0(t)&:=\int_{0}^\infty e^{-ty}f_0(y)\frac{dy}{y}=\int_{0}^\infty e^{-2ty}f_0(2y)\frac{dy}{y}\\
&=\int_{0}^\infty e^{-2ty}\Big[(1-e^{-y})e^{-y}+(1-e^{-y})f_0(y)\Big]\frac{dy}{y}\\
&=\ln(2t+2)-\ln(2t+1)+\int_{0}^\infty e^{-2ty}(1-e^{-y})f_0(y)\frac{dy}{y}.
\end{align*}
So
\begin{align*}
G_0(t)&=\ln(2t+2)-\ln(2t+1)+G_0(2t)-G_0(2t+1).
\end{align*}
If one iterates this formally, one gets
\begin{equation*}
G_0(1)=\sum_{n\ge3}(-1)^{\nu(n-1)}\ln n.
\end{equation*}
Here $\nu(k)$ is the number of ones in the binary expansion of the integer $k$.
We will only need the properties $\nu(2k)=\nu(k)$ and $\nu(2k+1)=1+\nu(k)$.

This is not a convergent series, but it makes good sense as follows. We have
\bal
G_0(1)&=\sum_{n\ge 2}(-1)^{\nu(n)}\ln (n+1)\non \\
&=\sum_{j\geq 1}(-1)^{\nu(j)}[\ln(2j+1)-\ln(2j+2)]\non\\
&=\sum_{j\geq 0}(-1)^{\nu(j)}\ln\lb \frac{2j+1}{2j+2}\rb+\ln 2\non\\
&=-\frac12 \ln 2+\ln 2=\frac{\ln 2}{2}=\frac{L}{2}                                \label{E22}
\end{align}
by the Allouche-Shallit (or Woods-Robbins) identity (\cite{ALS, AlCoMFSh87, LP05}). This proves (\ref{E1}).

Now we must confirm that $F_0(\chil)=0$ { in order to prove that the second part of (\ref{E21}) is null}. Set
\begin{equation*}
f_\al (y)=\sum_{r\ge1}\prod_{i=1}^r\Big(1-e^{-y/2^i}\Big)e^{-y/2^r}y^{-\alpha}.
\end{equation*}
Then
\begin{align*}
f_\al (2y)&=\sum_{r\ge1}\prod_{i=1}^r\Big(1-e^{-y/2^{i-1}}\Big)e^{-y/2^{r-1}}(2y)^{-\alpha}\\
&=\sum_{r\ge0}\prod_{i=0}^{r}\Big(1-e^{-y/2^{i}}\Big)e^{-y/2^{r}}(2y)^{-\alpha}\\
&=(1-e^{-y})e^{-y}(2y)^{-\alpha}+\sum_{r\ge1}\prod_{i=0}^{r}\Big(1-e^{-y/2^{i}}\Big)e^{-y/2^{r}}(2y)^{-\alpha}\\
&=(1-e^{-y})e^{-y}(2y)^{-\alpha}+(1-e^{-y})\sum_{r\ge1}\prod_{i=1}^{r}\Big(1-e^{-y/2^{i}}\Big)e^{-y/2^{r}}(2y)^{-\alpha}\\
&=(1-e^{-y})e^{-y}(2y)^{-\alpha}+(1-e^{-y})2^{-\alpha}f_\al (y).
\end{align*}
Now
\begin{align*}
G_\al(t)&:=\int_{0}^\infty e^{-ty}f_\al (y)\frac{dy}{y}=\int_{0}^\infty e^{-2ty}f_\al (2y)\frac{dy}{y}\\
&=\int_{0}^\infty e^{-2ty}\Big[(1-e^{-y})e^{-y}(2y)^{-\alpha}+(1-e^{-y})f_\al (y)2^{-\alpha}\Big]\frac{dy}{y}\\
&=2^{-\alpha}\Gamma(-\alpha)[(2t+1)^\alpha-(2t+2)^\alpha]+\int_{0}^\infty e^{-2ty}(1-e^{-y})f_\al (y)2^{-\alpha}\frac{dy}{y}.\\
\end{align*}
So
\begin{align*}
G_\al(t)=\Gamma(-\alpha)2^{-\alpha}[(2t+1)^\alpha-(2t+2)^\alpha]+2^{-\alpha}G_\al(2t)-2^{-\alpha}G_\al(2t+1).
\end{align*}
By iteration we find
\begin{align}
M(\al):=G_\al(1)&=-\Gamma(-\alpha)\sum_{k\ge1}\sum_{j=0}^{2^k-1}(-1)^{\nu(2^k+j)}2^{-\alpha k}(2^k+j+1)^\alpha \non\\
&=\Gamma(-\alpha)\sum_{k\ge1}\sum_{j=0}^{2^k-1}(-1)^{\nu(j)}2^{-\alpha k}(2^k+j+1)^\alpha,                 \label{E31}
\end{align}
and
\beq
\FI(\al)=M(\alt)/L.                                                                               \label{E2}
\eeq
Now, by (\ref{E20}) and setting $s=\chil$,
\bals
F_0(\chil)&=\frac1L\Gamma(\chil)\sum_{k\ge1}\sum_{j=0}^{2^k-1}(-1)^{\nu(j)}(2^k+j+1)^{-\chil}.
\end{align*}
It is already proved in \cite{LP05} that this is zero. (But it follows readily from the computations that appear in this paper.)

%
\section{The moments}\label{S2}
%
The purpose of this section is  to obtain the dominant terms of the moments of $J$, the first two of  which have been computed already in \cite{AK10}.

The paper \cite{LP04} contains the following theorem, which we express in our notation
\[F_k(s):=\left. \FI^{(k)}(\al)\right|_{\al=-Ls}.\]
\bth Let $J$ be the position of the maximal empty urn before the last non-empty urn. The first two moments of the parameter $J$ are asymptotically given by
\bals
\E(J-\log n;\B)&\sim \FI'(0)+\sum_{l\neq 0}F_1(\chil)e^{-2 l\pi\ii\log n},\\
\E((J-\log n)^2;\B)&\sim \FI''(0)+\sum_{l\neq 0}F_2(\chil)e^{-2 l\pi\ii\log n}.
\end{align*}
\rightline{$\square$}
\ethGL
Now, by (\ref{E31}) and (\ref{E2}),
\bal
\FI(\al)&=M(\alt)/L, \non\\
M(\al)&=\Gamma(-\alpha)H(\al) ,\quad \text{with}                                                                     \label{E3}\\
H(\al)&:=\sum_{k\ge 1}\sum_{j=0}^{2^k-1}(-1)^{\nu(j)}2^{-\alpha k}(2^k+j+1)^\alpha. \non 
\end{align}
The following expansion is well known, where $\gam$ is the Euler's constant (\cite{AS65}):
\[\Gamma(-\alpha)=-\frac{1}{\al}-\gam-\lp \frac{\pi^2}{12}+\frac{\gam^2}{2}\rp \al +\cdots.\]
Now we expand $H(\al)$:
\bal
H(\al)&=0+H'(0)\al+H''(0)\frac{\al^2}{2}+H'''(0)\frac{\al^3}{6}+\cdots,\non \\
H'(0)&=\sum_{k\ge 1}\biggl[ -Lk \sum_{j=0}^{2^k-1}(-1)^{\nu(j)} +L \sum_{j=0}^{2^k-1}(-1)^{\nu(j)}\log (2^k+j+1)\biggr],\non \\
H''(0)&=\sum_{k\ge 1}\biggl[ L^2k^2 \sum_{j=0}^{2^k-1}(-1)^{\nu(j)} -2L^2 k \sum_{j=0}^{2^k-1}(-1)^{\nu(j)}\log (2^k+j+1)
\\&\qquad\qquad+L^2 \sum_{j=0}^{2^k-1}(-1)^{\nu(j)}\log^2 (2^k+j+1)\biggr],\non \\
H'''(0)&=\sum_{k\ge 1}\biggl[ -L^3k^3 \sum_{j=0}^{2^k-1}(-1)^{\nu(j)} +3L^3k^2  \sum_{j=0}^{2^k-1}(-1)^{\nu(j)}\log (2^k+j+1)\non \\
&\qquad\qquad  -3L^3k \sum_{j=0}^{2^k-1}(-1)^{\nu(j)}\log^2 (2^k+j+1)+ \sum_{j=0}^{2^k-1}(-1)^{\nu(j)}\log^3 (2^k+j+1)\biggr].\non 
\end{align}
Note that, as $\FI(0)=1/2$,  the first term in these equations is identically $0$ and
$H'(0)=-\frac{L}{2}$. Set
\begin{align*}
f(x)&=\sum_{k\ge0}k\sum_{j=0}^{2^k-1}(-1)^{\nu(j)}\log (2^k+j+x),\\
g(x)&=\sum_{k\ge0}\sum_{j=0}^{2^k-1}(-1)^{\nu(j)}\log (2^k+j+x).
\end{align*}
A similar computation as before shows that
\begin{align*}
f(x)=f\Big(\frac x2\Big)-f\Big(\frac{x+1}{2}\Big)+g(x)-\log (1+x)
\end{align*}
and
\begin{align*}
g(x)&=\log (1+x)+g\Big(\frac x2\Big)-g\Big(\frac{x+1}2\Big).
\end{align*}
(Later we will make one general observation that produces all the necessary identities at once.)
Therefore
\begin{equation*}
g(0)=g(0)-g(\textstyle\frac{1}{2})
\quad\Rightarrow \quad
g(\textstyle\frac{1}{2})=0 \quad\Rightarrow \quad
g(1)=1+g(\tfrac 12)-g(1) \quad\Rightarrow \quad
g(1)=\textstyle\frac{1}{2}.
\end{equation*}
Likewise
\begin{align*}
f(0)&=f(0)-f(\tfrac{1}{2})+g(0) \quad\Rightarrow\quad
f(\tfrac{1}{2})=g(0) \quad \Rightarrow\\
f(1)&=f(\tfrac 12)-f(1)+g(1)-1 \quad\Rightarrow\quad
f(1)=\textstyle\frac{1}{2}g(0)+\tfrac14-\textstyle\frac{1}{2}=\textstyle\frac{1}{2}g(0)-\tfrac14.
\end{align*}

We don't know what $g(0)$ is, but it will  cancel out later on.
Furthermore, we note that the constant $g(0)$ is related to $N'(0)$ from  a paper by Flajolet and Martin~\cite{FM85}; this observation is, however, irrelevant here. The notation refers to
 $N(s)$  which is  the 
analytic continuation of
 \[\sum_{j\geq1}(-1)^{\nu(j)}/j^s.\] 
Set
\begin{equation*}
h(x)=\sum_{k\ge0}\sum_{j=0}^{2^k-1}(-1)^{\nu(j)}\log ^2(2^k+j+x).
\end{equation*}
Then we derive in a similar fashion that
\begin{align*}
h(x)&=\log ^2(1+x)+2g\Big(\frac x2\Big)+h\Big(\frac x2\Big)
-2g\Big(\frac {x+1}2\Big)-h\Big(\frac {x+1}2\Big).
\end{align*}
Hence
\begin{equation*}
h(0)=2g(0)+h(0)-2g(\textstyle\frac{1}{2})-h(\textstyle\frac{1}{2}) \quad\Rightarrow \quad
0=2g(0)-h(\textstyle\frac{1}{2}) \quad\Rightarrow \quad
h(\textstyle\frac{1}{2})=2g(0),
\end{equation*}
and
\begin{equation*}
h(1)=1+2g(\tfrac 12)+h(\tfrac 12)-2g(1)-h(1) \quad\Rightarrow \quad
2h(1)=1+2g(0)-1 \quad\Rightarrow \quad
h(1)=g(0).
\end{equation*}
Note that
\begin{equation*}
f(1)-\textstyle\frac{1}{2}h(1)=\textstyle\frac{1}{2}g(0)-\tfrac14-\textstyle\frac{1}{2}g(0)=-\tfrac14,
\end{equation*}
and the quantity $g(0)$ cancels out. Writing it in extended form, 
\begin{align*}
\sum_{k\ge1}k\sum_{j=0}^{2^k-1}(-1)^{\nu(j)}\log (2^k+j+1)
-\frac12\sum_{k\ge0}\sum_{j=0}^{2^k-1}(-1)^{\nu(j)}\log ^2(2^k+j+1)=-\frac14.
\end{align*}
Hence $H''(0)=-L^2/2$.

Let us turn to the third derivative. Omitting the details (introducing various auxiliary functions), we can prove that  $H'''(0)=-L^3/2$. But we will soon show  (in Section \ref{S5}) how one can streamline these
computations to get all moments {in a mechanical way}. 

Now we substitute $\al=\alt$ in $M(\al)/L$ and expand w.r.t. $\al$. By (\ref{E2}) and (\ref{E3}), this immediately gives
\bals
\FI(0)&=\frac12,\\
\FI'(0)&=\frac12\lp\frac{\gam}{L}+\frac12\rp,\\
\FI''(0)&=\frac12\lp\frac{1}{3}+\frac{\gam}{L}+\frac{\gam^2}{L^2}+\frac{\pi^2}{6L^2}\rp.\\
\end{align*}
Note that this  conforms to \cite{AK10}, as it should.
%
\section{The periodicities}\label{S3}
%
Let us analyze $F_1(\chil)$. To simplify the notation, we will simply write $\chi$. We have
\bals
\FI(\al)&=\frac1L \Gamma(-\alpha/L)\sum_{k\ge1}\sum_{j=0}^{2^k-1}(-1)^{\nu(j)}e^{-\alpha k}(2^k+j+1)^{\alpha/L},\\
\FI'(\al)&=\frac1L \biggl[ -\frac1L\Gamma(-\alpha/L)\psi(-\alpha/L)\sum_{k\ge1}\sum_{j=0}^{2^k-1}(-1)^{\nu(j)}e^{-\alpha k}(2^k+j+1)^{\alpha/L}\\
&\quad+\Gamma(-\alpha/L)\biggl[ -\sum_{k\ge1}\sum_{j=0}^{2^k-1}k(-1)^{\nu(j)}e^{-\alpha k} (2^k+j+1)^{\alpha/L}\\
&\quad+\sum_{k\ge1}\sum_{j=0}^{2^k-1}\log (2^k+j+1) (-1)^{\nu(j)}e^{-\alpha k}(2^k+j+1)^{\alpha/L}\biggr]\biggr],\\
F_1(\chi)&=-\frac{1}{L^2}\Gamma(\chi)\sum_{k\ge1}\sum_{j=0}^{2^k-1}(2^k+j+1)^{-\chi}\bigl(\psi(\chi)+kL-L \log (2^k+j+1)\bigr).
\end{align*}
We need an auxiliary  function
\begin{equation*}
g(x):=\sum_{k\ge0}\sum_{j=0}^{2^k-1}(-1)^{\nu(j)}(2^k+j+x)^{-\chi}.
\end{equation*}
As usual,
\begin{align*}
g(x)&=(1+x)^{-\chi}+\sum_{k\ge0}\sum_{j=0}^{2^{k+1}-1}(-1)^{\nu(j)}(2^{k+1}+j+x)^{-\chi}\\
&=(1+x)^{-\chi}+\sum_{k\ge0}\sum_{j=0}^{2^{k}-1}(-1)^{\nu(j)}\Bigl(2^{k}+j+\frac x2\Bigr)^{-\chi}-
\sum_{k\ge0}\sum_{j=0}^{2^{k}-1}(-1)^{\nu(j)}\Bigl(2^{k}+j+\frac {x+1}2\Bigr)^{-\chi},
\end{align*}
and so
\begin{align*}
g(x)&=(1+x)^{-\chi}+g\Big(\frac x2\Big)-g\Big(\frac{x+1}2\Big).
\end{align*}
Therefore
\begin{align*}
g(0)=1+g(0)-g(\tfrac{1}2) \quad &\Rightarrow \quad 
g(\tfrac{1}2)=1 \quad \Rightarrow \quad 
g(1)=1+g(\tfrac 12)-g(1) \\& \Rightarrow \quad 
2g(1)=2 \quad \Rightarrow \quad 
g(1)=1.
\end{align*}
We need a further auxiliary function
\begin{equation*}
f(x):=\sum_{k\ge0}k\sum_{j=0}^{2^k-1}(-1)^{\nu(j)}(2^k+j+x)^{-\chi}
\end{equation*}
and derive
\begin{align*}
f(x)&=\sum_{k\ge1}(k-1)\sum_{j=0}^{2^k-1}(-1)^{\nu(j)}(2^k+j+x)^{-\chi}-(1+x)^{-\chi}+g(x)\\
&=f\Big(\frac x2\Big)-f\Big(\frac{x+1}2\Big)-(1+x)^{-\chi}+g(x).
\end{align*}
Therefore
\begin{align*}
f(0)=f(0)-f(\tfrac{1}2)-1+g(0)\quad &\Rightarrow \quad 
f(\tfrac{1}2)=-1+g(0)\quad \Rightarrow\quad
f(1)=f(\tfrac 12)-f(1)\\&\Rightarrow \quad 
f(1)=-\textstyle\frac{1}{2}+\textstyle\frac{1}{2}g(0).
\end{align*}
We need a third function
\begin{equation*}
h(x):=\sum_{k\ge0}\sum_{j=0}^{2^k-1}(-1)^{\nu(j)}(2^k+j+x)^{-\chi}\log (2^k+j+x).
\end{equation*}
The usual procedure (that we suppress) leads to
\begin{align*}
h(x)
&=h\Big(\frac{x}{2}\Big)-h\Big(\frac{x+1}{2}\Big)+g\Big(\frac{x}{2}\Big)-g\Big(\frac{x+1}{2}\Big)+(1+x)^{-\chi}\log (1+x).\\
\end{align*}
Therefore
\begin{align*}
h(0)&=h(0)-h(\tfrac{1}{2})+g(0)-g(\tfrac{1}{2})\quad\Rightarrow \quad
h(\tfrac{1}{2})=g(0)-1\quad\Rightarrow \\h(1)&=h(\tfrac{1}{2})-h(1)+g(\tfrac{1}{2})-g(1)+1\quad\Rightarrow \quad
h(1)=\textstyle\frac{1}{2}g(0).
\end{align*}
Now
\begin{align*}
F_1(\chi)&=-\frac{1}{L^2}\Gamma(\chi)\Big[\psi(\chi)(g(1)-1)+Lf(1)-L(h(1)-1)\Big]\\
&=-\frac1L \Gamma(\chi)\Big[-\frac12+\frac12g(0)-\frac12g(0)+1\Big]
=-\frac{1}{2L}\Gamma(\chi).
\end{align*}
Finally, we turn to $F_2(\chi)$. Omitting the details, we can prove that
\begin{equation*}
F_2(\chi)=-\frac{\Gamma(\chi)}{2L}+\frac{\Gamma(\chi)\psi(\chi)}{L^2}.
\end{equation*}

Note that the periodicities conform to \cite{AK10}. We will not pursue these computations as we will soon give a simple, direct way of getting all the expressions we need.

To obtain the conditioned moments, we divide by $\P(\B)=1/2$. So
\bals
\E(J-\log n|\B)&\sim 2\biggl[ \FI'(0)+\sum_{l\neq 0}F_1(\chil)e^{-2 l\pi\ii\log n}\biggr],\\
\E((J-\log n)^2|\B)&\sim 2\biggl[ \FI''(0)+\sum_{l\neq 0}F_2(\chil)e^{-2 l\pi\ii\log n}\biggr]
\end{align*}
and we have the conditioned variance
\begin{align*}
\V(J|\B)&\sim 2\FI''(0)-4(\FI'(0))^2+2\sum_{l\neq 0}F_2(\chil)e^{-2 l\pi\ii\log n}\\&
-8\FI'(0)\biggl[\sum_{l\neq 0}F_1(\chil)e^{-2 l\pi\ii\log n}\biggr]
-4 \bigg[\sum_{l\neq 0}F_1(\chil)e^{-2 l\pi\ii\log n}\biggr] ^2.
\end{align*}
This has been computed in \cite{AK10} already.
%
\section{General Allouche-Shallit-type formulas and direct moments computations}\label{S5}
%
In this section, we first prove a very simple expression for $H^{(m)}(0)$ which translates to $\FI(\al)$. As a byproduct, we have a direct form for all moments and also a family of new interesting identities.

Set
\begin{equation*}
A(a,b):=\sum_{k\ge0}k^a\sum_{j=0}^{2^k-1}(-1)^{\nu(j)}\log ^b(2^k+j+1).
\end{equation*}
We have seen already, by (\ref{E22}), that
\begin{equation*}
A(0,1)=\frac12,
\end{equation*}
which is the Allouche-Shallit identity, and
\begin{equation*}
A(0,2)-2A(1,2)=\frac12.
\end{equation*}
Introducing more and more auxiliary functions, one is led to 
\begin{gather*}
A(0,3)-3A(1,2)+3A(2,2)=\frac12,\\
A(0,4)-4A(1,3)+6A(2,2)-4A(3,1)=\frac12.
\end{gather*}
An obvious pattern appears:
\begin{equation*}
\sum_{l=0}^m\binom ml(-1)^{m-l}A(l,m-l)=\frac12.
\end{equation*}
All these formulas follow from the \emph{master formula}  for $m\ge0$:
\bth
\begin{equation*}
\sum_{k\ge0}\sum_{j=0}^{2^k-1}(-1)^{\nu(j)}\Bigl(\log (2^k+j+1)-k\Bigr)^m=\frac12.
\end{equation*}
\ethGL
\bpr 
Here is the simple proof. Set
\begin{equation*}
f(x):=\sum_{k\ge0}\sum_{j=0}^{2^k-1}(-1)^{\nu(j)}\Bigl(\log (2^k+j+x)-k\Bigr)^m.
\end{equation*}
Then 
\begin{align*}
f(x)&=\log ^m(1+x)+\sum_{k\ge0}\sum_{j=0}^{2^{k+1}-1}(-1)^{\nu(j)}\Bigl(\log (2^{k+1}+j+x)-k-1\Bigr)^m\\
&=\log ^m(1+x)+\sum_{k\ge0}\sum_{j=0}^{2^{k+1}-1}(-1)^{\nu(j)}\Bigl(\log (2^{k}+\frac{j+x}2)-k\Bigr)^m\\
&=\log ^m(1+x)+\sum_{k\ge0}\sum_{j=0}^{2^{k}-1}(-1)^{\nu(j)}\Bigl(\log (2^{k}+\frac{2j+x}2)-k\Bigr)^m\\&\qquad\qquad\qquad-\sum_{k\ge0}\sum_{j=0}^{2^{k}-1}(-1)^{\nu(j)}\Bigl(\log (2^{k}+\frac{2j+1+x}2)-k\Bigr)^m\\
&=\log ^m(1+x)+f\Big(\frac x2\Big)-f\Big(\frac{x+1}2\Big).
\end{align*}
Therefore, by setting $x=0$,
\begin{equation*}
f(\tfrac12)=0,
\end{equation*}
and by setting $x=1$,
\begin{equation*}
f(1)=\frac12. \ 
\end{equation*}
\epr
The master theorem leads to (note that the summation on $k$ is from $k=0$, but the summation in $H^{(m)}$ starts from $k=1$)
\bals
H^{(m)}(0)&=-\frac12 L^m,\qquad m\geq 1.
\end{align*}
This gives the following {Laplace transforms}:
\bth
\bals
M(\al)&=\Gamma(-\alpha)H(\al)=-\frac12 \Gamma(-\alpha) ( e^{L\al}-1), \\
\FI(\al)&=M(\alt)/L = -\frac{1}{2L} \Gamma(-\alt) ( e^{L\alt}-1).
\end{align*}
\ethGL
Now that we found that $\FI(\al)$ has such a simple explicit form, we recover immediately $\FI(0)$, $\FI'(0)$, $\FI{''}(0)$, and a new expression $\FI{'''}(0)$ related to the third moment:
\beq
\FI{'''}(0)=\frac{\zeta(3)}{L^3}+\frac{\pi^2\gam}{4L^3}+\frac{\pi^2}{8L^2}+\frac{\gam}{2L}+\frac{\gam^3}{2L^3}+\frac{1}{8}+\frac{3\gam^2}{4L^2}.                                                                                                                                   \label{E4}
\eeq
Similarly, we recover $F_1(\chi)$, $F_2(\chi)$, and a new expression
\beq
F_3(\chi)=\Gam(\chi)\lb -\frac{3\psi(1,\chi)}{2L^3}-\frac{3\psi^2(\chi)}{2L^3}+\frac{3\psi(\chi)}{L^2}-\frac{1}{2L}\rb.            \label{E5}
\eeq
For instance,  we can state the third moment:
\bth
\[\E\bigl((J-\log n)^3;\B\bigr)\sim \FI'''(0)+\sum_{l\neq 0}F_3(\chil)e^{-2 l\pi\ii\log n}\]
with (\ref{E4}) and (\ref{E5}).
\ethGL
All moments can in principle be computed automatically.
%
\section{The $\textrm{LMV}(-1)$ case}\label{S6}
%
If the largest missing value is exactly one smaller than the largest value, we say,
following Archibald and Knopfmacher~\cite{AK10}, that the sequence has the $\textrm{LMV}(-1)$ property.
In this case, contrarily to the previous sections, our urn model leads almost immediately  to all probabilistic properties: we have here a very simple form for $\FI(\al)$. Let $\B$ be now the event that the $\textrm{LMV}(-1)$ property is satisfied, and $J$ be the largest missing value  exactly one smaller than the largest value. 
We easily derive (we just plug $r=1$ into (\ref{E12}))
\bals
\FI(\al)&=
\int_0^\II y^{-\alt}e^{-y}\lb  1-e^{-ye^{-L}}\rb e^{-ye^{-L}}\frac{dy}{Ly}\\
&=\frac1L \lp 2^{-\alt}3^{\alt}-2^{\alt}\rp\Gam(-\alt).
\end{align*}
Hence, automatically,
\bals
\FI(0)&=2-\log 3,\\
\FI'(0)&=\frac{2\gam}{L}+\log 3-\frac{\gam \log 3}{L}-\frac{\log^2 3}{2},\\
\FI''(0)&=-\frac{\log^3 3}{3}+\frac23+\log^2 3 
-\frac{\log 3\gam^2}{L^2}+2\frac{\gam\log 3}{L}-\frac{\pi^2\log 3}{6L^2}-\log 3+\frac{\pi^2}{3L^2}+2\frac{\gam^2}{L^2}-\frac{\gam\log^2 3}{L}.
\end{align*}
The first two expressions are already given in \cite{AK10}. The third one is new. All moments are obtained in the same way.

Also we easily derive
\bals
F_0(\chil)&=\frac1L(3^{-\chil}-1)\Gam(\chil),\\
F_1(\chil)&=-\frac{\Gam(\chil)3^{-\chil}}{L^2}\lb L-L\log 3+L3^{\chil} +\psi(\chil)-\psi(\chil)3^{\chil}\rb,\\
F_2(\chil)&=-\frac{\Gam(\chil)3^{-\chil}}{L^3}\Bigl[ -L^2+L^23^{\chil}+2\log 3L^2-2\psi(\chil)L-2\psi(\chil)L3^{\chil} \\
&\quad -\log^2 3L^2+2\psi(\chil)\log 3L-\psi(1,\chil)+\psi(1,\chil)3^{\chil}-\psi^2(\chil)+\psi^2(\chil)3^{\chil}\Bigr]. 
\end{align*}
Again the first two expressions are already given in \cite{AK10}. The third one is new. That described the moments, but we can
also get the (asymptotic) probability that $\B$ holds:
\[\P(\B)\sim \FI(0)+\sum_{l\neq 0}F_0(\chil)e^{-2 l\pi\ii\log n}.\]

%
\section{Conclusion}\label{S7}
%
We succeeded in analyzing the instance $p=1/2$, related to random compositions.
The \hbox{(semi)}\-automatic computations of all moments led us to a one parameter extension
of the celebrated identity due to Allouche and Shallit.
Unfortunately, this analysis cannot be extended to the case $p\neq 1/2$, as no expansions that
involve $\nu(k)$ are available. Of course we could use a general integral form similar to (\ref{E12}) and use the theorems we developed in  \cite{LP04},
but it would not be really explicit. One could also use some recursion on the number of gaps and some inclusion-exclusion expressions, but it would not be simpler.

The instance $p=1/2$ is privileged inasmuch as it leads to very beautiful mathematics,
and this is just appropriate for the present birthday issue.


\begin{thebibliography}{10}

\bibitem{AK10}
M.~Archibald and A.~Knopfmacher.
\newblock The largest missing value in a composition of an integer.
\newblock {\em Discrete Math.} {\bf 311} (2011), 723--731.

\bibitem{AlCoMFSh87}
J.-P. Allouche, H.~Cohen, M.~Mend{\`e}s France, and J.~O. Shallit.
\newblock De nouveaux curieux produits infinis.
\newblock {\em Acta Arith.} {\bf 49} (1987), 141--153.

\bibitem{ALP05}
G.~Louchard, H.~Prodinger, and M.~D. Ward.
\newblock The number of distinct values of some multiplicity in sequences of
  geometrically distributed random variables.
\newblock {\em Discr. Math. and Theoret. Comp. Sci.} (2005), 231--256.
\newblock 2005 International Conference on Analysis of Algorithms.

\bibitem{ALS}
J.-P. Allouche and J.~Shallit.
\newblock {\em Automatic Sequences: Theory, Applications, Generalizations}.
\newblock Cambridge University Press, Cambridge, 2003.

\bibitem{AS65}
M.~Abramowitz and I.~A.~Stegun.
\newblock {\em Handbook of Mathematical Functions}.
\newblock Dover, 1965.

\bibitem{FM85}
P.~Flajolet and G.~N.~Martin.
\newblock Probabilistic counting algorithms for data base applications.
\newblock {\em J. Comput. Syst. Sci.} {\bf 31} (1985),
  182--209.

\bibitem{HK04}
P.~Hitczenko and A.~Knopfmacher.
\newblock Gap-free samples of geometric random variables.
\newblock {\em Discrete Math.} {\bf 294} (2005), 225--239.

\bibitem{HL00}
P.~Hitczenko and G.~Louchard.
\newblock Distinctness of compositions of an integer: a probabilistic analysis.
\newblock {\em Random Structures \& Algorithms} {\bf 19} (2001),
  407--437.

\bibitem{LO63}
M.~Lo\`{e}ve.
\newblock {\em Probability Theory}, 3rd edition.
\newblock D. Van Nostrand, 1963.

\bibitem{LP04}
G.~Louchard and H.~Prodinger.
\newblock Asymptotics of the moments of extreme-value related distribution
  functions.
\newblock {\em Algorithmica} {\bf 46} (2006), 431--467.
\newblock Long version: \url{http://www.ulb.ac.be/di/mcs/louchard/moml.ps}.

\bibitem{LP05}
G.~Louchard and H.~Prodinger.
\newblock On gaps and unoccupied urns in sequences of geometrically distributed
  random variables.
\newblock {\em Discrete Math.} {\bf 308-309} (2008), 1538--1562.
\newblock Long version: \url{http://www.ulb.ac.be/di/mcs/louchard/gaps18.ps}.

\bibitem{Robbins}
D.~Robbins.
\newblock Solution to Elementary problem E2692.
\newblock {\em Amer. Math. Monthly} {\bf 86} (1979), 395--395.

\bibitem{Woods}
D.~R.~Woods.
\newblock Elementary problem E2692.
\newblock {\em Amer. Math. Monthly} {\bf 85} (1978), 48.

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 05A16; Secondary 60C05.

\noindent \emph{Keywords:} composition, largest missing value, asymptotic expansion, identity,
sum-of-digits function.


\bigskip
\hrule
\bigskip

\noindent (Concerned with sequence
\seqnum{A000120}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received April 18 2012;
revised version received  October 25 2012.
Published in {\it Journal of Integer Sequences}, March 2 2013.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}