#  $r$-Lah distribution: properties, limit theorems and an application to
compressed sensing

Zakhar Kabluchko and David Albert Steigenberger

###### Abstract.

We introduce and study the $r$-Lah distribution whose definition involves
$r$-Stirling numbers of both kinds. We compute its expectation, show its log-
concavity and prove limit theorems for this distribution. We use these results
to prove threshold phenomena for convex cones generated by random walks and to
analyze the probability of unique recovery of sparse monotone signals from
linear measurements.

###### Key words and phrases:

$r$-Stirling numbers, $r$-Lah numbers, central limit theorem,
mod-$\phi$-convergence, log-concavity, compressed sensing, convex cones,
random walks

###### 2020 Mathematics Subject Classification:

Primary: 11B73, 60C05; Secondary: 60D05, 60E05, 60F05, 60F10

##  1\. Introduction

The goal of this paper is to introduce and study the $r$-Lah distribution. The
motivation comes from the following problem (c.f. Section 6 in [16]). Let
$\xi_{1},\dotsc,\xi_{n}$ be a collection of i.i.d. random $d$-dimensional
vectors with absolutely continuous, centrally symmetric distribution (the
latter means that $\xi_{1}$ has the same law as $-\xi_{1}$). Their partial
sums are denoted by

$\displaystyle S_{i}\coloneqq\xi_{1}+\dotsm+\xi_{i},\qquad 1\leq i\leq
n,\qquad S_{0}=0.$

The sequence $S_{0},S_{1},\dotsc,S_{n}$ is called a random walk. We are
interested in the random polyhedral cone $C_{n}^{B}\subseteq\mathbb{R}^{d}$
defined by

$\displaystyle C_{n}^{B}\coloneqq\text{pos}\\{S_{1},\dotsc
S_{n}\\}=\\{\lambda_{1}S_{1}+\dotsm+\lambda_{n}S_{n}\;|\;\lambda_{1},\dotsc,\lambda_{n}\geq
0\\},$

which is referred to as the Weyl random cone of type B+ due to its relation to
the Weyl chamber of type $B$, see [13]. Corollary 2.12 in [13] (see also [12,
Eqn. (2.23)]) states that the expected total number of $k$-dimensional faces
of $C_{n}^{B}$ is

$\displaystyle\mathbb{E}\Bigl{[}f_{k}\bigl{(}C_{n}^{B}\bigr{)}\Bigr{]}=\frac{2\cdot
k!}{n!}\sum_{l=0}^{\infty}{n\brack d-2l-1}_{\frac{1}{2}}{d-2l-1\brace
k}_{\frac{1}{2}},$ (1.1)

for all $k\in\\{0,\ldots,d-1\\}$ and $n\geq d$, where the numbers on the
right-hand side are the $r$-Stirling numbers with parameter $r=1/2$, to be
defined in Section 2. Our goal is to investigate the relation between the
expected number of $k$-dimensional faces of $C_{n}^{B}$ and the maximal
possible number $\binom{n}{k}$ of such $k$-faces. Namely, if $d\to\infty$ and
$n=n(d)\to\infty$ grows sufficiently slow, then we expect the number of
$k$-faces of $C_{n}^{B}$ to be “close” to the maximal number $\binom{n}{k}$,
while in the regime when $d\to\infty$ and $n=n(d)\to\infty$ grows sufficiently
fast, we expect it to be much smaller than $\binom{n}{k}$. We will confirm
this intuition and identify the position of the threshold where the phase
transition occurs. To this end, we introduce the $r$-Lah distribution which is
closely related to the right-hand side of (1.1). This distribution generalizes
the Lah distribution, which has been studied in [16] and corresponds to $r=0$.
As it turns out, limit theorems for the $r$-Lah distribution lead to threshold
phenomena for the face numbers of $C_{n}^{B}$. Threshold phenomena of this
type were first investigated by Vershik and Sporyshev [30] and Donoho and
Tanner [6, 7, 8, 9] in the setting of random projections of regular simplices,
cubes, orthants, and Gaussian polytopes.

This paper is organized as follows. In Section 2, we will recall the
definition of the $r$-Stirling numbers and use these to define the $r$-Lah
distribution. In Section 3 we give an explicit formula for the expectation of
this distribution and prove log-concavity. Furthermore, we prove several limit
theorems including a central limit theorem. These limit theorems will then be
used to prove threshold phenomena for the expected number of $k$-faces of
$C_{n}^{B}$ in Section 4. As another application, in Section 5 we analyze
threshold phenomena for the probability of unique recovery of sparse monotone
signals from linear measurements.

##  2\. $r$-Stirling numbers and the $r$-Lah distribution

The Stirling number of the first kind, denoted by ${n\brack k}$, counts the
number of permutations of $\\{1,\dotsc,n\\}$ that have exactly $k$ cycles. The
Stirling number of the second kind counts the number of ways to partition the
set $\\{1,\dotsc,n\\}$ into $k$ non-empty subsets and is denoted by ${n\brace
k}$. For $k\in\mathbb{N}_{0}$, these numbers can be defined by their
exponential generating functions via

$\displaystyle\frac{1}{k!}\left(\log\left((1-x)^{-1}\right)\right)^{k}=\sum_{n=k}^{\infty}{n\brack
k}\frac{x^{n}}{n!}\quad\text{ and
}\quad\frac{1}{k!}\left(\mathrm{e}^{x}-1\right)^{k}=\sum_{n=k}^{\infty}{n\brace
k}\frac{x^{n}}{n!}.$ (2.1)

The Lah number [21, 27] is defined by

$\displaystyle L(n,k)\coloneqq\sum_{j=k}^{n}{n\brack j}{j\brace k}$

and counts the number of ways to partition the set $\\{1,\dotsc,n\\}$ into $k$
non-empty subsets and to linearly order the elements inside each subset.

One can generalize [3, 22, 24, 26] all three kinds of numbers in the following
way: for $r\in\mathbb{N}_{0}$, the $r$-Stirling number of the first kind
${n\brack k}_{r}$ counts the number of permutations of the set
$\\{1,\dotsc,n+r\\}$ with exactly $k+r$ cycles, such that the elements
$1,\dotsc,r$ are in distinct cycles. The $r$-Stirling number of the second
kind, ${n\brace k}_{r}$, as well as the $r$-Lah number, $L(n,k)_{r}$, can be
defined analogously111We follow the notation of Nyul and Rácz [26]: what we
denote by ${n\brack k}_{r}$ corresponds to ${n+r\brack k+r}_{r}$ in the
notation of Broder [3], and similarly for ${n\brace k}_{r}$.. The exponential
generating functions of the $r$-Stirling numbers are given by

$\displaystyle\frac{1}{k!}\left(\log\left((1-x)^{-1}\right)\right)^{k}(1-x)^{-r}=\sum_{n=k}^{\infty}{n\brack
k}_{r}\frac{x^{n}}{n!}\quad$ (2.2)

and

$\displaystyle\quad\frac{1}{k!}\left(\mathrm{e}^{x}-1\right)^{k}\mathrm{e}^{rx}=\sum_{n=k}^{\infty}{n\brace
k}_{r}\frac{x^{n}}{n!}.$ (2.3)

It is clear from these formulas that the regular Stirling numbers are
recovered by taking $r=0$. Using (2.1) and the Taylor series of
$\mathrm{e}^{rx}$ and $(1-x)^{-r}$ one gets (c.f. [26, p. 1661])

$\displaystyle{n\brack k}_{r}=\sum_{j=k}^{n}{n\brack
j}\binom{j}{k}r^{j-k}\qquad\text{ and }\qquad{n\brace
k}_{r}=\sum_{j=k}^{n}\binom{n}{j}{j\brace k}r^{n-j}.$ (2.4)

These formulas define the $r$-Stirling numbers for $n\in\mathbb{N}_{0}$,
$k\in\\{0,\ldots,n\\}$ and arbitrary non-integer $r\in\mathbb{R}$.
Furthermore, they prove that ${n\brack k}_{r}$ and ${n\brace k}_{r}$ are
polynomials in $r$. The $r$-Stirling numbers satisfy the recurrence relations

$\displaystyle{n\brack k}_{r}$ $\displaystyle=(n+r-1){n-1\brack
k}_{r}+{n-1\brack k-1}_{r},$ (2.5) $\displaystyle{n\brace k}_{r}$
$\displaystyle=(k+r){n-1\brace k}_{r}+{n-1\brace k-1}_{r}.$ (2.6)

A combinatorial proof for $r\in\mathbb{N}_{0}$ can be found in [3, Theorems
1,2], but the relations stay true for all $r\in\mathbb{R}$ since both sides
are polynomials in $r$. Notable special cases are ${n\brack
0}_{r}=r(r+1)\dotsm(r+n-1)$ and ${n\brace 0}_{r}=r^{n}$. In particular,
${0\brack 0}_{r}={0\brace 0}_{r}=1$ for all $r\in\mathbb{R}$. For integer
$k>n$ and $k<0$ we put ${n\brack k}_{r}={n\brace k}_{r}=0$, for all
$r\in\mathbb{R}$, $n\in\mathbb{N}_{0}$. For these and further properties of
the $r$-Stirling numbers we refer to [3, 26] and [24, Chapter 8].

The $r$-Lah number [26], see also [2, 4, 28], is defined as

$\displaystyle L(n,k)_{r}\coloneqq\sum_{j=k}^{n}{n\brack j}_{r}{j\brace
k}_{r}=\binom{n+2r-1}{k+2r-1}\frac{n!}{k!},$ (2.7)

for $n\in\mathbb{N}_{0}$, $k\in\\{0,\ldots,n\\}$, $r\in\mathbb{R}$. The second
equation has been proven for $r\in\mathbb{N}_{0}$ in Theorem 3.7 in [26] but
it stays true for $r\in\mathbb{R}$ since both sides are polynomials in $r$. We
are now in a position to define the $r$-Lah distribution.

######  Definition 2.1.

A random variable $X=\mathop{\mathrm{Lah}}\nolimits(n,k)_{r}$ has an $r$-Lah
distribution with parameters $n\in\mathbb{N}$, $k\in\\{0,\ldots,n\\}$ and
$r\in[0,\infty)$ (where the case $k=r=0$ is always excluded) if

$\displaystyle\mathbb{P}[\mathop{\mathrm{Lah}}\nolimits(n,k)_{r}=j]=\frac{1}{L(n,k)_{r}}{n\brack
j}_{r}{j\brace k}_{r},\qquad j\in\\{k,k+1,\dotsc,n\\}.$ (2.8)

We exclude the case $k=r=0$ in which $L(n,0)_{0}=0$, $n\in\mathbb{N}$, since
$(-1)!=\infty$. For $r=0$, the $r$-Lah distribution coincides with the Lah
distribution that has been studied in [16]. The present paper extends these
results to arbitrary real $r\geq 0$.

######  Definition 2.2.

We say $(n,k,r)$ is an admissible triple of parameters for the $r$-Lah
distribution if $n\in\mathbb{N}$, $k\in\\{0,\ldots,n\\}$, $r\in[0,\infty)$ and
$\max\\{k,r\\}>0$.

######  Remark 2.3.

The term ${n\brack j}_{r}{j\brace k}_{r}$ counts the number of permutations of
$\\{1,2,\ldots,n+r\\}$ with $j+r$ cycles which are decomposed into $k+r$
blocks of cycles and have the property that the elements $1,\ldots,r$ appear
in distinct blocks of cycles (and, consequently, in distinct cycles). The
well-known Foata correspondence is a bijection between permutations of
$\\{1,\ldots,m\\}$ with $i$ cycles and permutations of the same set with $i$
minima. Applying the Foata correspondence to each block of cycles yields a
decomposition of $\\{1,\ldots,n+r\\}$ into $k+r$ blocks, with a specified
ordering of the elements inside each block, with $j+r$ local minima inside the
blocks and such that the elements $1,\ldots,r$ are inside different blocks. It
follows from (2.7) and (2.8) that $\mathop{\mathrm{Lah}}\nolimits(n,k)_{r}-r$
is the distribution of the number of local minima inside a uniformly random
decomposition as just described. This interpretation stems from the
combinatorial explanation of (2.7) established in Theorem 4.1 (iv) in [28] for
$r=s$.

##  3\. Properties of the $r$-Lah distribution

In this section, we will derive explicit and asymptotic formulas for the
expectation of the $r$-Lah distribution. We will show that the $r$-Lah
distribution is log-concave and thus unimodal. Finally, we will use the
concept of mod-Poisson convergence to prove limit theorems for the $r$-Lah
distribution, namely central and local limit theorems, precise large
deviations and an asymptotic formula for its mode.

###  3.1. Expectation

######  Theorem 3.1.

For any admissible triple of parameters $(n,k,r)$ the expectation of an
$r$-Lah distributed random variable $\mathop{\mathrm{Lah}}\nolimits(n,k)_{r}$
is given by

$\displaystyle\mathbb{E}[\mathop{\mathrm{Lah}}\nolimits(n,k)_{r}]$
$\displaystyle=$
$\displaystyle\frac{k(n+2r)}{n-(k-1)}\bigl{[}H_{n+2r}-H_{k+2r-1}\bigr{]}+r\bigl{[}H_{n+2r-1}-H_{k+2r-1}\bigr{]}$
(3.1) $\displaystyle=$
$\displaystyle\frac{k+\bigl{[}k(n+r)+r(n+1)\bigr{]}\cdot\bigl{[}H_{n+2r-1}-H_{k+2r-1}\bigr{]}}{n-(k-1)}.$
(3.2)

Here, $H_{n}=1+\frac{1}{2}+\dotso+\frac{1}{n}$ denotes the $n$-th harmonic
number. The harmonic number of fractional argument $z$ can be defined by
$H_{z}=\Gamma^{\prime}(z+1)/\Gamma(z+1)+\gamma$, but, actually, this is not
necessary since the above formulas contain only differences of the form
$H_{\alpha+m}-H_{\alpha}:=\sum_{j=\alpha+1}^{\alpha+m}\frac{1}{j}$ with
integer $m\in\mathbb{N}_{0}$ and $\alpha>-1$.

For $r=0$ Theorem 3.1 yields the following corollary which has been overlooked
in [16, Theorem 3.2], where a more lengthy expression has been given.

######  Corollary 3.2.

The expectation of a Lah distributed random variable with parameters
$n\in\mathbb{N}$, $k\in\\{1,\ldots,n\\}$ (and $r=0$) is given by

$\displaystyle\mathbb{E}[\mathop{\mathrm{Lah}}\nolimits(n,k)_{0}]=\frac{nk}{n-(k-1)}[H_{n}-H_{k-1}].$

In order to prove Theorem 3.1 we need two lemmata. As usual, $[x^{n}]f(x)$
denotes the coefficient of $x^{n}$ in the Taylor/Laurent expansion of the
function $f$.

######  Lemma 3.3.

For any $n\in\mathbb{N}$, $k\in\\{0,\ldots,n\\}$, $j\in\\{k,\ldots,n\\}$ and
$r\in\mathbb{R}$ we have

$\displaystyle\frac{k!}{n!}{n\brack j}_{r}{j\brace
k}_{r}=\bigl{[}t^{j}\bigr{]}\bigl{[}x^{n}\bigr{]}\bigl{(}(1-x)^{-t}-1\bigr{)}^{k}(1-x)^{-(rt+r)}.$

###### Proof.

We compute the Taylor series of the function on the right-hand side using the
exponential generating functions of the $r$-Stirling numbers.

$\displaystyle\frac{1}{k!}\bigl{(}(1-x)^{-t}-1\bigr{)}^{k}(1-x)^{-(rt+r)}$
$\displaystyle=(1-x)^{-r}\Biggl{[}\frac{1}{k!}\Bigr{(}\mathrm{e}^{-t\log(1-x)}-1\Bigl{)}^{k}\mathrm{e}^{-rt\log(1-x)}\Biggr{]}$
$\displaystyle\stackrel{{\scriptstyle\eqref{Definition_r_Stir_second}}}{{=}}(1-x)^{-r}\sum_{j=k}^{\infty}\Biggl{[}{j\brace
k}_{r}\frac{\bigl{(}-t\log(1-x)\bigr{)}^{j}}{j!}\Biggr{]}$
$\displaystyle=\sum_{j=k}^{\infty}{j\brace
k}_{r}t^{j}\Biggl{[}\frac{\left(-\log(1-x)\right)^{j}}{j!}(1-x)^{-r}\Biggr{]}$
$\displaystyle\stackrel{{\scriptstyle\eqref{Definition_r_Stir_first}}}{{=}}\sum_{j=k}^{\infty}{j\brace
k}_{r}t^{j}\Biggl{[}\sum_{n=j}^{\infty}{n\brack
j}_{r}\frac{x^{n}}{n!}\Biggr{]}$
$\displaystyle=\sum_{j=k}^{\infty}\sum_{n=j}^{\infty}\frac{1}{n!}{n\brack
j}_{r}{j\brace k}_{r}t^{j}x^{n}.$ (3.3)

This gives the statement. ∎

Next up, we will use Lemma 3.3 to derive the formula that will help us
calculate the expectation of the $r$-Lah distribution.

######  Lemma 3.4.

For any $n\in\mathbb{N}$, $k\in\\{0,\ldots,n\\}$ and $r\in\mathbb{R}$ we have

$\displaystyle\sum_{j=k}^{n}j{n\brack j}_{r}{j\brace k}_{r}$
$\displaystyle=(-1)^{n-k}\frac{n!}{k!}[x^{n-k+1}]\bigl{(}(1+x)^{-(k+2r)}\log(1+x)(k-rx)\bigr{)}$
(3.4)
$\displaystyle=\frac{n!}{k!}[x^{n-k+1}]\Biggl{(}(1+x)^{n+2r}\log(1+x)\biggl{(}k+r\frac{x}{1+x}\biggr{)}\Biggr{)}.$
(3.5)

###### Proof.

We start with the formula (3.3), valid for arbitrary $k\in\mathbb{N}_{0}$,
$r\in\mathbb{R}$:

$\displaystyle\sum_{n=k}^{\infty}\sum_{j=k}^{n}t^{j}x^{n}\frac{k!}{n!}{n\brack
j}_{r}{j\brace k}_{r}=\bigl{(}(1-x)^{-t}-1\bigr{)}^{k}(1-x)^{-(rt+r)}.$

The function $((1-x)^{-t}-1)^{k}(1-x)^{-(rt+r)}$ is analytic in $(x,t)$ as a
composition of analytic functions as long as $|x|<1$, $t\in\mathbb{C}$.
Therefore, we may differentiate its Taylor series any number of times in $x$
and $t$ and interchange the order of derivatives. We differentiate in $t$ and
set $t=1$:

$\sum_{n=k}^{\infty}\sum_{j=k}^{n}j\frac{k!}{n!}{n\brack j}_{r}{j\brace
k}_{r}x^{n}=-\biggl{(}\frac{x}{1-x}\biggr{)}^{k-1}(1-x)^{-2r-1}(\log(1-x))(k+rx).$

Dividing by $x^{k-1}$ and evaluating the coefficient of $x^{n-k+1}$, we get

$\sum_{j=k}^{n}j{n\brack j}_{r}{j\brace
k}_{r}=-\frac{n!}{k!}[x^{n-k+1}](1-x)^{-(k+2r)}(\log(1-x))(k+rx).$

Changing $x$ to $(-x)$ on the right-hand side yields Equation (3.4)

$\displaystyle\sum_{j=k}^{n}j{n\brack j}_{r}{j\brace
k}_{r}=(-1)^{n-k}\frac{n!}{k!}[x^{n-k+1}]\bigl{(}1+x\bigl{)}^{-(k+2r)}\log(1+x)(k-rx).$

To prove Equation (3.5) we use Cauchy’s integral formula giving

$\displaystyle\sum_{j=k}^{n}j{n\brack j}_{r}{j\brace
k}_{r}=(-1)^{n-k}\frac{n!}{k!}\frac{1}{2\pi
i}\oint_{\gamma}\frac{\log(1+x)}{(1+x)^{k+2r}}\frac{(k-rx)}{x^{n-k+2}}\mathop{}\\!{d}x.$

Here, $\gamma$ is a small counterclockwise circle centered at zero. Now, we
substitute $1+x$ with $\frac{1}{1+y}$ to get

$\displaystyle\sum_{j=k}^{n}j{n\brack j}_{r}{j\brace
k}_{r}=\frac{n!}{k!}\frac{1}{2\pi
i}\oint_{\gamma^{\prime}}\frac{\log(1+y)(1+y)^{n+2r}}{y^{n-k+2}}\Biggr{(}k+r\frac{y}{1+y}\Biggr{)}\mathop{}\\!{d}y.$

Using Cauchy’s integral formula once more, we arrive at Equation (3.5). ∎

###### Proof of Theorem 3.1.

We start with (3.5) and realize that

$\frac{k!}{n!}\sum_{j=k}^{n}j{n\brack j}_{r}{j\brace
k}_{r}=k\bigl{[}x^{n-k+1}\bigr{]}\left((1+x)^{n+2r}\log(1+x)\right)\\\
+r\bigl{[}x^{n-k}\bigr{]}\left((1+x)^{n+2r-1}\log(1+x)\right).$

Using the Taylor series
$\log(1+x)=\sum_{m=1}^{\infty}(-1)^{m-1}\frac{x^{m}}{m}$ and
$(1+x)^{\nu}=\sum_{p=0}^{\infty}\binom{\nu}{p}x^{p}$ which converge for
$|x|<1$ we write

$\displaystyle\log(1+x)(1+x)^{\nu}=\sum_{z=1}^{\infty}$ $\displaystyle
x^{z}\sum_{m=1}^{z}(-1)^{m-1}\frac{1}{m}\binom{\nu}{z-m}.$

Then,

$\displaystyle\frac{k!}{n!}\sum_{j=k}^{n}j{n\brack j}_{r}{j\brace
k}_{r}=k\sum_{m=1}^{n-k+1}(-1)^{m-1}\frac{1}{m}\binom{n+2r}{n-k+1-m}+r\sum_{m=1}^{n-k}(-1)^{m-1}\frac{1}{m}\binom{n+2r-1}{n-k-m}$
$\displaystyle=k\frac{n+2r}{n-(k-1)}\binom{n+2r-1}{k+2r-1}\sum_{m=k+2r}^{n+2r}\frac{1}{m}+r\binom{n+2r-1}{k+2r-1}\sum_{m=k+2r}^{n+2r-1}\frac{1}{m},$

where we used the identity

$\displaystyle\sum\limits_{m=1}^{z}\binom{\nu}{z-m}\frac{(-1)^{m-1}}{m}=\binom{\nu}{z}\sum\limits_{m=\nu-z+1}^{\nu}\frac{1}{m},$

which holds for all $z\in\mathbb{N}$ and real $\nu>z-1$. The latter condition
is secured by $\max\\{k,r\\}>0$. For integer $\nu$, the identity can be shown
by induction. For real $\nu$, it holds since both sides are polynomials in
$\nu$. Multiplying by $1/L(n,k)_{r}$ and applying (2.7) gives us Theorem 3.1.
∎

######  Theorem 3.5.

Let $n\to\infty$ and $k=k(n)\in\\{1,\dotsc,n\\}$ be a function of $n$.
Let $r\geq 0$ be fixed. Then,

$\displaystyle\mathbb{E}[\mathop{\mathrm{Lah}}\nolimits(n,k)_{r}]\sim\begin{cases}(k+r)\log\left(n/k\right),&\text{if
}\quad k=o(n)\\\ \frac{n\alpha\log\left(1/\alpha\right)}{1-\alpha},&\text{if
}\quad k\sim\alpha n\text{ with }\alpha\in(0,1)\\\ n,&\text{if }\quad k\sim
n,\end{cases}$

where we write $a_{n}\sim b_{n}$ if $a_{n}/b_{n}\to 1$ as $n\to\infty$.

Setting $r=0$ we recover the formula obtained in Theorem 3.7 in [16].

###### Proof.

First, let $k=o(n)$. Using the formula $H_{m+2r-1}=\log m+O(1)$ we get
$H_{n+2r-1}-H_{k+2r-1}=\log(n/k)+O(1)\sim\log(n/k)$ and the result follows
from (3.2) upon observing that $k(n+r)+r(n+1)\sim(k+r)n$.

Let now $k\sim\alpha n$ with $\alpha\in(0,1)$. Then, using the formula
$H_{m+2r-1}=\log m+\gamma+o(1)$ as $m\to\infty$, we get
$H_{n+2r-1}-H_{k+2r-1}\to\log(1/\alpha)$ and the claim follows from (3.2)
after observing that $k(n+r)+r(n+1)\sim\alpha n^{2}$ and
$n-(k-1)\sim(1-\alpha)n$.

For $k\sim n$, we use (3.1). We notice that

$\displaystyle
H_{n+2r}-H_{k+2r-1}=\frac{1}{k+2r}+\dotso+\frac{1}{n+2r}\in\left[\frac{n-(k-1)}{n+2r},\frac{n-(k-1)}{k+2r}\right],$

which, by the sandwich lemma, leads to

$\lim_{n\to\infty}[H_{n+2r}-H_{k+2r-1}]\frac{(n+2r)}{n-(k-1)}=1.$

Together with $H_{n+2r-1}-H_{k+2r-1}\to 0$ this yields the claim. ∎

###  3.2. Mod-Poisson convergence and central limit theorem

The notion of mod-Poisson convergence has been introduced in [20], see also
[1, 5, 10, 15, 19, 25], and provides a unified approach to various limit
theorems such as local limit theorems and precise large deviations.

######  Definition 3.6.

A sequence of random variables $(Z_{n})_{n\in\mathbb{N}}$ converges in the
mod-Poisson sense with parameters $(\lambda_{n})_{n\in\mathbb{N}}$, where
$\lambda_{n}\to+\infty$, if the limit

$\displaystyle\Psi(u):=\lim_{n\to\infty}\frac{\mathbb{E}\bigl{[}\mathrm{e}^{uZ_{n}}\bigr{]}}{\mathrm{e}^{\lambda_{n}(\mathrm{e}^{u}-1)}}$

exists for all $u$ in some open set $\mathcal{D}\subseteq\mathbb{C}$
containing the real axis $\mathbb{R}$ and the convergence is uniform on
compact subsets of $\mathcal{D}$.

In the following, we will prove that $r$-Lah distributed random variables
converge in the mod-Poisson sense. To this end, we need the generating
function of an $r$-Lah distributed random variable which is defined for
complex $t$ by

$\displaystyle
P_{n,k,r}(t)\coloneqq\mathbb{E}\Bigl{[}t^{\mathop{\mathrm{Lah}}\nolimits(n,k)_{r}}\Bigr{]}=\frac{1}{L(n,k)_{r}}\displaystyle\sum_{j=k}^{n}t^{j}{n\brack
j}_{r}{j\brace k}_{r}.$

######  Lemma 3.7.

For any admissible triple of parameters $(n,k,r)$ and all $t\in\mathbb{C}$ we
have

$\displaystyle P_{n,k,r}(t)$
$\displaystyle=\frac{1}{\binom{n+2r-1}{k+2r-1}}[x^{n}]\bigl{(}(1-x)^{-t}-1\bigr{)}^{k}(1-x)^{-(rt+r)}$
(3.6)
$\displaystyle=\frac{1}{\binom{n+2r-1}{k+2r-1}}\sum_{m=0}^{k}(-1)^{k-m}\binom{k}{m}\frac{\Gamma\Bigl{(}\bigl{(}r(t+1)+tm+n\bigr{)}\Bigr{)}}{\Gamma\Bigl{(}\bigl{(}r(t+1)+tm\bigr{)}\Bigr{)}n!}.$
(3.7)

For $r=0$, the summand with $m=0$ should be interpreted as $0$.

###### Proof.

Equation (3.3) gives us

$\displaystyle\sum_{j=k}^{n}t^{j}\frac{k!}{n!}{n\brack j}_{r}{j\brace
k}_{r}=[x^{n}]\bigl{(}(1-x)^{-t}-1\bigr{)}^{k}(1-x)^{-(rt+r)}.$

Dividing by $\binom{n+2r-1}{k+2r-1}$ gives us (3.6). To prove (3.7), we apply
the binomial formula to (3.6):

$\displaystyle
P_{n,k,r}(t)=\frac{1}{\binom{n+2r-1}{k+2r-1}}[x^{n}]\sum_{m=0}^{k}\binom{k}{m}(-1)^{k-m}(1-x)^{-tm}(1-x)^{-(rt+r)}$
$\displaystyle=\frac{1}{\binom{n+2r-1}{k+2r-1}}\sum_{m=0}^{k}\binom{k}{m}(-1)^{k-m}[x^{n}](1-x)^{-(r(t+1)+tm)}.$

To complete the proof of (3.7), we use the Taylor expansion of the last term
around zero

$\displaystyle(1-x)^{-(r(t+1)+tm)}=1+\sum_{n=1}^{\infty}\frac{\Gamma\Bigl{(}\bigl{(}r(t+1)+tm+n\bigr{)}\Bigr{)}}{\Gamma\Bigl{(}\bigl{(}r(t+1)+tm\bigr{)}\Bigr{)}n!}x^{n}.$

∎

The next theorem states that, for fixed $k,r$ and as $n\to\infty$, the $r$-Lah
distribution $\mathop{\mathrm{Lah}}\nolimits(n,k)_{r}$ converges in the mod-
Poisson sense with parameters $\lambda_{n}=(k+r)\log n$.

######  Theorem 3.8.

Let $k\in\mathbb{N}_{0}$ and $r\in[0,\infty)$ be fixed and such that
$\max\\{k,r\\}>0$. Then,

$\displaystyle\lim_{n\to\infty}\frac{\mathbb{E}\Bigl{[}\mathrm{e}^{z\mathop{\mathrm{Lah}}\nolimits(n,k)_{r}}\Bigr{]}}{\mathrm{e}^{(k+r)(\log
n)(\mathrm{e}^{z}-1)}}=\frac{\Gamma(k+2r)}{\Gamma((k+r)\mathrm{e}^{z}+r)}$

for every
$z\in\mathcal{D}_{\mathop{\mathrm{Lah}}\nolimits}\coloneqq\\{t\in\mathbb{C}|\cos(\operatorname{Im}t)>0\\}\supseteq\mathbb{R}$.
This convergence is uniform as long as $z$ stays in any compact subset $K$ of
$\mathcal{D}_{\mathop{\mathrm{Lah}}\nolimits}$ and the speed of convergence is
$O(n^{-\varepsilon(K)})$ for some $\varepsilon(K)>0$.

###### Proof.

Note that
$\mathbb{E}[\mathrm{e}^{z\mathop{\mathrm{Lah}}\nolimits(n,k)_{r}}]=P_{n,k,r}(\mathrm{e}^{z})$.
Since the number of summands in (3.7) is fixed, we investigate each term
individually. We shall use that

$\displaystyle\frac{\Gamma(\alpha+n)}{\Gamma(\beta+n)}=n^{\alpha-\beta}\bigl{(}1+O(1/n)\bigr{)},\qquad\text{
as }n\to\infty,$ (3.8)

where the remainder term is uniform as long as $\alpha$ and $\beta$ stay
bounded; see [11]. For $t\coloneqq\mathrm{e}^{z}$ and $m\in\\{0,\dotsc,k\\}$,
the $m$-th summand in (3.7) is

$\displaystyle(-1)^{k-m}\binom{k}{m}\frac{\Gamma\Bigl{(}r(\mathrm{e}^{z}+1)+\mathrm{e}^{z}m+n\Bigr{)}}{\Gamma\Bigl{(}r(\mathrm{e}^{z}+1)+\mathrm{e}^{z}m\Bigr{)}n!}$
$\displaystyle=$
$\displaystyle(-1)^{k-m}\binom{k}{m}\frac{n^{r(\mathrm{e}^{z}+1)+\mathrm{e}^{z}m-1}}{\Gamma\Bigl{(}r(\mathrm{e}^{z}+1)+\mathrm{e}^{z}m\Bigr{)}}\bigl{(}1+O(1/n)\bigr{)}$

by (3.8) with $\alpha=r(\mathrm{e}^{z}+1)+\mathrm{e}^{z}m$ and $\beta=1$. If
$z$ stays in a compact subset $K$ of
$\mathcal{D}_{\mathop{\mathrm{Lah}}\nolimits}\coloneqq\\{t\in\mathbb{C}|\cos(\operatorname{Im}t)>0\\}$,
we can find $\varepsilon(K)\in(0,1)$ such that
$\operatorname{Re}\mathrm{e}^{z}>\varepsilon(K)>0$. Thus, the summand with
$m=k$ dominates in the following sense:

$\displaystyle P_{n,k,r}(\mathrm{e}^{z})$
$\displaystyle=\frac{1}{\binom{n+2r-1}{k+2r-1}}\left(\frac{n^{r(\mathrm{e}^{z}+1)+\mathrm{e}^{z}k-1}}{\Gamma(r(\mathrm{e}^{z}+1)+\mathrm{e}^{z}k)}\bigl{(}1+O(1/n)\bigr{)}\right.$
$\displaystyle\qquad+\left.\sum_{m=0}^{k-1}(-1)^{k-m}\binom{k}{m}\frac{n^{r(\mathrm{e}^{z}+1)+\mathrm{e}^{z}m-1}}{\Gamma(r(\mathrm{e}^{z}+1)+\mathrm{e}^{z}m)}\bigl{(}1+O(1/n)\bigr{)}\right)$
$\displaystyle=\frac{\Gamma(k+2r)}{\Gamma\bigl{(}(k+r)\mathrm{e}^{z}+r\bigr{)}}n^{(r+k)(\mathrm{e}^{z}-1)}\Bigl{(}1+O\bigl{(}n^{-\varepsilon}\bigr{)}\Bigr{)}.$

Since the choice of $\varepsilon$ only relies on $K$, the error term is
uniform on $K$. ∎

The following result shows that the mod-Poisson convergence implies a central
limit theorem (c.f. Proposition 2.4(2) in [20] and its proof).

######  Theorem 3.9.

Let $(Z_{n})_{n\in\mathbb{N}}$ be a sequence of random variables converging in
the mod-Poisson sense with parameters $\lambda_{n}$ such that
$\lim_{n\to\infty}\lambda_{n}=\infty.$ Then,

$\displaystyle\frac{Z_{n}-\lambda_{n}}{\sqrt{\lambda_{n}}}\overset{{d}}{\underset{n\to\infty}{\longrightarrow}}\mathcal{N}(0,1).$

Theorems 3.8 and 3.9 imply the following Central Limit Theorem for the $r$-Lah
distribution.

######  Theorem 3.10 (Central Limit Theorem).

Let $k\in\mathbb{N}_{0}$ and $r\in[0,\infty)$ be fixed and such that
$\max\\{k,r\\}>0$. Then,

$\displaystyle\frac{\mathop{\mathrm{Lah}}\nolimits(n,k)_{r}-(k+r)\log
n}{\sqrt{(k+r)\log
n}}\overset{{d}}{\underset{n\to\infty}{\longrightarrow}}\mathcal{N}(0,1).$

###  3.3. Log-concavity of the $r$-Lah distribution

The main result of this section is the following

######  Proposition 3.11.

For any admissible triple of parameters $(n,k,r)$ the $r$-Lah distribution
$\mathop{\mathrm{Lah}}\nolimits(n,k)_{r}$ is log-concave, that is

$\displaystyle\mathbb{P}[\mathop{\mathrm{Lah}}\nolimits(n,k)_{r}=i]^{2}\geq\mathbb{P}[\mathop{\mathrm{Lah}}\nolimits(n,k)_{r}=i-1]\mathbb{P}[\mathop{\mathrm{Lah}}\nolimits(n,k)_{r}=i+1]$

for all $i\in\\{k+1,\dotsc,n-1\\}$.

To prove this proposition, we need to generalize the log-concavity of
$r$-Stirling numbers that is known [23] for $r\in\mathbb{N}$ to arbitrary
$r\in[0,\infty)$. A sequence $(a_{k})_{k=0}^{n}$ is called strictly log-
concave if $a_{k}^{2}>a_{k+1}a_{k-1}$ for all $k\in\\{1,\ldots,n-1\\}$.

######  Lemma 3.12.

For $r\in[0,\infty)$ and $n\in\mathbb{N}$, the sequence

$\displaystyle\left({n\brack k}_{r}\right)_{k=0}^{n}$

is strictly log-concave.

###### Proof.

For $r\in\mathbb{N}_{0}$, the claim has been proven in [23, Theorem 2]. The
proof is based on the formula

$\displaystyle A_{n,r}(x):=\sum_{j=0}^{n}{n\brack
j}_{r}x^{j}=(x+r)(x+r+1)\dotsm(x+r+n-1)$

which can be found in [3, Corollary 9] for $r\in\mathbb{N}_{0}$ but stays true
for all $r\geq 0$ since both sides are polynomials in $r$. Thus, all roots of
$A_{n,r}(x)$ are real and the claim follows from Newton’s inequality; see,
e.g. [23, Theorem 1]. ∎

######  Lemma 3.13.

For $r\in[0,\infty)$ and $n\in\mathbb{N}$, the sequence

$\displaystyle\left({n\brace k}_{r}\right)_{k=0}^{n}$

is strictly log-concave.

###### Proof.

For $r\in\mathbb{N}_{0}$, the statement has been proven by Mező [23, Theorem
6]. To adapt his proof to arbitrary $r>0$, we consider the polynomial

$\displaystyle B_{n,r}(x)\coloneqq\sum_{j=0}^{n}{n\brace j}_{r}x^{j}$

and show that its roots are all real (and negative). Using the recurrence
relation (2.6) we can write

$\displaystyle B_{n,r}(x)$ $\displaystyle=$
$\displaystyle\sum_{j=0}^{n}\left[(j+r){n-1\brace j}_{r}+{n-1\brace
j-1}_{r}\right]x^{j}$ $\displaystyle=$ $\displaystyle
x\left(\frac{d}{dx}B_{n-1,r}(x)+B_{n-1,r}(x)\right)+rB_{n-1,r}(x).$ (3.9)

If $x\geq 0$, then $B_{n,r}(x)\geq B_{n,r}(0)={n\brace 0}_{r}=r^{n}>0$ for all
$n\in\mathbb{N}$. Thus, let $x<0$ from now on. Then (3.9) can be rewritten as

$\displaystyle
B_{n,r}(x)=\frac{x}{\mathrm{e}^{x}(-x)^{r}}\frac{\mathop{}\\!{d}}{dx}\left(\mathrm{e}^{x}(-x)^{r}B_{n-1,r}(x)\right).$
(3.10)

We continue with induction over $n$. The only root of $B_{1,r}(x)=x+r$ is real
and negative since $r>0$. Assume that $B_{n-1,r}(x)$ has $n-1$ negative roots.
Then, $\mathrm{e}^{x}(-x)^{r}B_{n-1,r}(x)$ has $n-1$ negative roots and a root
at $x=0$. By Rolle’s theorem,
$\frac{d}{dx}(\mathrm{e}^{x}(-x)^{r}B_{n-1,r}(x))$ has at least $n-1$ negative
roots. Equation (3.10) implies that $B_{n,r}(x)$ has at least $n-1$ negative
roots. The remaining $n$-th root of this polynomial must be real (and
negative), since $B_{n,r}(x)$ has real (and positive) coefficients and its
roots come in complex conjugate pairs. This completes the induction. Newton’s
inequality then yields the claim. ∎

######  Lemma 3.14.

For $k\in\mathbb{N}_{0}$, real $r\geq 0$ and integer $j>k$ it holds that

${j\brace k}_{r}^{2}\geq{j-1\brace k}_{r}{j+1\brace k}_{r}.$

Equality only holds for $k=0$, while strict inequality holds for all $k\geq
1$.

###### Proof.

The cases $k=0$ and $k=1$ follow from the equations ${j\brace 0}_{r}=r^{j}$
and ${j\brace 1}_{r}=(r+1)^{j}-r^{j}$ which can be found in [26]. For $k\geq
2$ we use (2.6):

$\displaystyle{j\brace k}_{r}{j\brace k}_{r}-{j-1\brace k}_{r}{j+1\brace
k}_{r}$ (3.11) $\displaystyle=$ $\displaystyle{j\brace
k}_{r}\left[(k+r){j-1\brace k}_{r}+{j-1\brace k-1}_{r}\right]-{j-1\brace
k}_{r}\left[(k+r){j\brace k}_{r}+{j\brace k-1}_{r}\right]$ $\displaystyle=$
$\displaystyle{j\brace k}_{r}{j-1\brace k-1}_{r}-{j-1\brace k}_{r}{j\brace
k-1}_{r}$ (3.12) $\displaystyle=$ $\displaystyle\left[(k+r){j-1\brace
k}_{r}+{j-1\brace k-1}_{r}\right]{j-1\brace k-1}_{r}-{j-1\brace
k}_{r}\left[(k+r-1){j-1\brace k-1}_{r}+{j-1\brace k-2}_{r}\right]$
$\displaystyle=$ $\displaystyle{j-1\brace k-1}_{r}{j-1\brace k}_{r}+{j-1\brace
k-1}_{r}^{2}-{j-1\brace k}_{r}{j-1\brace k-2}_{r}>0$

The last statement is true because of Lemma 3.13. ∎

Equations (3.11) and (3.12) yield the following corollary which, for $r=0$,
can be found in Theorem 3.3 and Corollary 3.1 of [29].

######  Corollary 3.15.

For all $k\in\mathbb{N}$ and $r\in[0,\infty)$ the sequence $({{j+1\brace
k}_{r}}/{{j\brace k}_{r}})_{j\geq k}$ is strictly decreasing, while the
sequence $({j\brace k+1}_{r}/{{j\brace k}_{r}})_{j\geq k}$ is strictly
increasing.

###### Proof of Proposition 3.11.

The claim follows by multiplying the inequalities of Lemmas 3.12 and 3.14. ∎

The log-concavity of the $r$-Lah distribution yields the following

######  Corollary 3.16 (Unimodality).

For any admissible triple of parameters $(n,k,r)$ the $r$-Lah distribution is
unimodal. That is, there exists $m_{n,k,r}\in\\{k,\dotsc,n\\}$ such that
$i\mapsto\mathbb{P}[\mathop{\mathrm{Lah}}\nolimits(n,k)_{r}=i]$ is
nondecreasing for $i\leq m_{n,k,r}$ and nonincreasing for $i\geq m_{n,k,r}$.

###  3.4. Further limit theorems

Fix $k\in\mathbb{N}_{0}$ and $r\geq 0$ such that $\max\\{k,r\\}>0$. To derive
additional limit theorems for the $r$-Lah distribution we will verify
conditions A1-A4 of [17] with the parameters

$\displaystyle\mathbb{L}_{n}(j)=\mathbb{P}[\mathop{\mathrm{Lah}}\nolimits(n,k)_{r}=j],$
$\displaystyle w_{n}=(k+r)\log n,$ $\displaystyle\beta_{\pm}=\pm\infty,$
$\displaystyle\mathcal{D}=\\{\beta\in\mathbb{C}:|\operatorname{Im}\beta|<\pi/2\\},$
$\displaystyle\varphi(\beta)=\mathrm{e}^{\beta}-1,$ $\displaystyle
W_{\infty}(\beta)=\Gamma(k+2r)/\Gamma((k+r)\mathrm{e}^{\beta}+r).$

Assumption A1 is trivial, while A2 and A3 follow from Theorem 3.8. It remains
to check A4. We recall from Lemma 3.7 that

$\displaystyle P_{n,k,r}\Bigl{(}\mathrm{e}^{\beta+iu}\Bigr{)}$
$\displaystyle=\mathbb{E}\biggl{[}\mathrm{e}^{(\beta+iu)\mathop{\mathrm{Lah}}\nolimits(n,k)_{r}}\biggr{]}$
$\displaystyle=\frac{1}{\binom{n+2r-1}{k+2r-1}}\sum_{m=0}^{k}(-1)^{k-m}\binom{k}{m}\frac{\Gamma\Bigl{(}r\bigl{(}\mathrm{e}^{\beta+iu}+1\bigr{)}+\mathrm{e}^{\beta+iu}m+n\Bigr{)}}{\Gamma\Bigl{(}r\bigl{(}\mathrm{e}^{\beta+iu}+1\bigr{)}+\mathrm{e}^{\beta+iu}m\Bigr{)}n!}.$

Let $K\subset\mathbb{R}$ be an arbitrary compact set and $a\in(0,\pi)$.
Uniformly over $\beta\in K$, we have

$\displaystyle
n^{-(k+r)(\mathrm{e}^{\beta}-1)}\int_{a}^{\pi}\biggl{|}P_{n,k,r}\Bigl{(}\mathrm{e}^{\beta+iu}\Bigr{)}\biggr{|}\mathop{}\\!{d}u$
$\displaystyle\leq$ $\displaystyle
Cn^{-(k+r)(\mathrm{e}^{\beta}-1)}\sum_{m=0}^{k}\int_{a}^{\pi}\biggl{|}\frac{\Gamma\Bigl{(}r\bigl{(}\mathrm{e}^{\beta+iu}+1\bigr{)}+\mathrm{e}^{\beta+iu}m+n\Bigr{)}}{n^{k+2r-1}n!}\biggr{|}\mathop{}\\!{d}u$
$\displaystyle\leq$ $\displaystyle
C\sum_{m=0}^{k}\int_{a}^{\pi}\biggl{|}n^{\mathrm{e}^{\beta+iu}(r+m)-(k+r)\mathrm{e}^{\beta}}\biggr{|}\mathop{}\\!{d}u\leq
Cn^{-\delta}$

for some constants $C=C(K,k)>0$ and $\delta=\delta(K,k,a)>0$. We used that
$1/\Gamma(z)$ is bounded on every compact subset of $\mathbb{C}$ and, in the
last line, (3.8).

Now we can use the results from [17] to prove limit theorems for the $r$-Lah
distribution.

######  Theorem 3.17 (Local limit theorem).

For every fixed $k\in\mathbb{N}_{0}$ and $r\in[0,\infty)$ such that
$\max\\{k,r\\}>0$ we have

$\displaystyle\sqrt{\log
n}\sup_{j\in\mathbb{Z}}\Biggl{|}\mathbb{P}\bigl{[}\mathop{\mathrm{Lah}}\nolimits(n,k)_{r}=j\bigr{]}-\frac{\exp\Bigl{\\{}-\frac{(j-(k+r)\log
n)^{2}}{2(k+r)\log n}\Bigr{\\}}}{\sqrt{2\pi(k+r)\log
n}}\Biggr{|}\overset{}{\underset{n\to\infty}{\longrightarrow}}0.$

###### Proof.

The statement follows directly from Theorem 2.7 in [17]. ∎

######  Proposition 3.18 (Location of the mode).

For all $r\in[0,\infty)$ and every fixed $k\in\mathbb{N}_{0}$ such that
$\max\\{k,r\\}>0$ there is $N\in\mathbb{N}$ such that for all integers $n>N$,
all maximizers of the function
$i\mapsto\mathbb{P}[\mathop{\mathrm{Lah}}\nolimits(n,k)_{r}=i]$ are among the
following two numbers:

$\displaystyle\biggl{\lfloor}(k+r)\log
n-\frac{(k+r)\Gamma^{\prime}(k+2r)}{\Gamma(k+2r)}-\frac{1}{2}\biggr{\rfloor},\biggl{\lceil}(k+r)\log
n-\frac{(k+r)\Gamma^{\prime}(k+2r)}{\Gamma(k+2r)}-\frac{1}{2}\biggr{\rceil}.$

###### Proof.

The claim follows from Theorem 2.11 and Remark 2.12 in [17]. ∎

######  Theorem 3.19 (Precise asymptotics of large deviations).

Let $k\in\mathbb{N}_{0}$ and $r\in[0,\infty)$ be such that $\max\\{k,r\\}>0$
and let $(x_{n})_{n\in\mathbb{N}}$ be a sequence of real numbers converging to
$x>0$, such that $(k+r)x_{n}\log n$ is integer for all $n\in\mathbb{N}$. Then,
we have the asymptotics

$\displaystyle\mathbb{P}\bigl{[}\mathop{\mathrm{Lah}}\nolimits(n,k)_{r}=(k+r)x_{n}\log
n\bigr{]}$
$\displaystyle\sim\frac{n^{-(k+r)\bigl{(}x_{n}\log(x_{n})-x_{n}+1\bigr{)}}}{\sqrt{2\pi(k+r)x\log
n}}\frac{\Gamma(k+2r)}{\Gamma\bigl{(}(k+r)x+r\bigr{)}},$
$\displaystyle\mathbb{P}\bigl{[}\mathop{\mathrm{Lah}}\nolimits(n,k)_{r}\geq(k+r)x_{n}\log
n\bigr{]}$
$\displaystyle\sim\frac{x}{x-1}\frac{n^{-(k+r)\bigl{(}x_{n}\log(x_{n})-x_{n}+1\bigr{)}}}{\sqrt{2\pi(k+r)x\log
n}}\frac{\Gamma(k+2r)}{\Gamma\bigl{(}(k+r)x+r\bigr{)}},$
$\displaystyle\mathbb{P}\bigl{[}\mathop{\mathrm{Lah}}\nolimits(n,k)_{r}\leq(k+r)x_{n}\log
n\bigr{]}$
$\displaystyle\sim\frac{1}{1-x}\frac{n^{-(k+r)\bigl{(}x_{n}\log(x_{n})-x_{n}+1\bigr{)}}}{\sqrt{2\pi(k+r)x\log
n}}\frac{\Gamma(k+2r)}{\Gamma\bigl{(}(k+r)x+r\bigr{)}}.$

The second statement only holds for $x>1$, while the third only holds for
$x<1$.

###### Proof.

The first statement follows from Remark 2.9 in [17], with $K\subset\mathbb{R}$
being an arbitrary compact segment which contains $x$ and $\log(x_{n})$. For
the other two asymptotics, c.f. Theorem 3.2.2 in [10] (or repeat the proof of
Theorem 2.8 in [17] starting with the second formula of Lemma 3.2.1 of [10]).
∎

##  4\. A threshold phenomenon for face numbers of cones generated by random
walks

We will use the results from the previous section to prove weak and strong
threshold phenomena for the expected number of $k$-faces of the cone
$C_{n}^{B}$ that has been defined in the introduction. As already stated, the
following equation holds for all $k\in\\{0,\ldots,d-1\\}$ and $n\geq d$:

$\displaystyle\mathbb{E}\Bigl{[}f_{k}\bigl{(}C_{n}^{B}\bigr{)}\Bigr{]}=\frac{2\cdot
k!}{n!}\sum_{l=0}^{\infty}{n\brack d-2l-1}_{\frac{1}{2}}{d-2l-1\brace
k}_{\frac{1}{2}},$

see [13, Corollary 2.12] and [12, Equation (2.23)]. We can represent the
right-hand side in terms of the $r$-Lah distribution with $r=1/2$

$\displaystyle\frac{\mathbb{E}\bigl{[}f_{k}(C_{n}^{B})\bigr{]}}{\binom{n}{k}}$
$\displaystyle=$ $\displaystyle
2\frac{k!}{\binom{n}{k}n!}\sum_{l=0}^{\infty}{n\brack
d-2l-1}_{\frac{1}{2}}{d-2l-1\brace k}_{\frac{1}{2}}$ $\displaystyle=$
$\displaystyle
2\mathbb{P}\left[\mathop{\mathrm{Lah}}\nolimits(n,k)_{\frac{1}{2}}\in\\{d-1,d-3,\dotsc\\}\right].$
(4.1)

Since it holds that

  * •

$\displaystyle\sum_{j=k}^{n}(-1)^{n-j}{n\brack j}_{r}{j\brace k}_{r}=0$ if
$n>k$ (c.f. Theorem 5 in [3]),

  * •

$\displaystyle\sum_{j=k}^{n}{n\brack j}_{r}{j\brace k}_{r}=L(n,k)_{r}$,

we conclude that, for $n>k$,

$\displaystyle\mathbb{P}[\mathop{\mathrm{Lah}}\nolimits(n,k)_{r}\text{ takes
even value}]=\mathbb{P}[\mathop{\mathrm{Lah}}\nolimits(n,k)_{r}\text{ takes
odd value}]=\frac{1}{2}.$ (4.2)

This allows us to rewrite (4.1) as

$\displaystyle
1-\frac{\mathbb{E}\bigl{[}f_{k}(C_{n}^{B})\bigr{]}}{\binom{n}{k}}=2\mathbb{P}\left[\mathop{\mathrm{Lah}}\nolimits(n,k)_{\frac{1}{2}}\in\\{d+1,d+3,\dotsc\\}\right].$
(4.3)

These representations will be used to prove threshold phenomena; c.f. [16,
Theorems 6.2, 6.3] for corresponding results in the case $r=0$.

######  Theorem 4.1 (Weak Threshold).

Let $d\to\infty$ and $n=n(d)\geq d$ be a function of $d$ such that

$\displaystyle\gamma\coloneqq\lim_{d\to\infty}\frac{\log\bigl{(}n(d)\bigr{)}}{d}\in[0,\infty].$

Then, for every fixed $k\in\mathbb{N}_{0}$, we have

$\displaystyle\lim_{d\to\infty}\frac{\mathbb{E}\bigl{[}f_{k}(C_{n}^{B})\bigr{]}}{\binom{n}{k}}=\begin{cases}1,&\text{if
}\quad\gamma<\frac{1}{k+\frac{1}{2}},\\\ 0,&\text{if
}\quad\gamma>\frac{1}{k+\frac{1}{2}}.\end{cases}$

In the critical case $\gamma=\frac{1}{k+\frac{1}{2}}$, if

$\displaystyle\log\bigl{(}n(d)\bigr{)}=\biggl{(}\frac{1}{k+\frac{1}{2}}\biggr{)}\biggl{(}d+c\sqrt{d}+o\Bigl{(}\sqrt{d}\Bigr{)}\biggr{)}$
(4.4)

for some constant $c\in\mathbb{R}$, then

$\displaystyle\lim_{d\to\infty}\frac{\mathbb{E}\bigl{[}f_{k}(C_{n}^{B})\bigr{]}}{\binom{n}{k}}=\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{-c}\mathrm{e}^{-x^{2}/2}\mathop{}\\!{d}x.$

###### Proof.

First, let $\gamma>\frac{1}{k+\frac{1}{2}}$. Then,

$\displaystyle\frac{\mathbb{E}\bigl{[}f_{k}(C_{n}^{B})\bigr{]}}{\binom{n}{k}}$
$\displaystyle=$ $\displaystyle
2\mathbb{P}\left[\mathop{\mathrm{Lah}}\nolimits(n,k)_{\frac{1}{2}}\in\\{d-1,d-3,\dotsc\\}\right]$
$\displaystyle\leq$ $\displaystyle
2\mathbb{P}\left[\mathop{\mathrm{Lah}}\nolimits(n,k)_{\frac{1}{2}}\leq
d\right]$ $\displaystyle=$ $\displaystyle
2\mathbb{P}\left[\frac{\mathop{\mathrm{Lah}}\nolimits(n,k)_{\frac{1}{2}}-\left(k+\frac{1}{2}\right)\log
n}{\sqrt{\left(k+\frac{1}{2}\right)\log
n}}\leq\frac{d-\left(k+\frac{1}{2}\right)\log
n}{\sqrt{\left(k+\frac{1}{2}\right)\log n}}\right]$ $\displaystyle=$
$\displaystyle
2\mathbb{P}\left[\frac{\mathop{\mathrm{Lah}}\nolimits(n,k)_{\frac{1}{2}}-\left(k+\frac{1}{2}\right)\log
n}{\sqrt{\left(k+\frac{1}{2}\right)\log n}}\leq\frac{\sqrt{\log
n}\left(\frac{1}{\gamma}+o(1)-\left(k+\frac{1}{2}\right)\right)}{\sqrt{k+\frac{1}{2}}}\right].$

Since $\frac{1}{\gamma}<k+\frac{1}{2}$, the last fraction on the right-hand
side goes to $-\infty$ and the probability goes to $0$ by the CLT for the
$r$-Lah distribution, see Theorem 3.10.

Let now $\gamma<\frac{1}{k+\frac{1}{2}}$. Equation (4.3) gives

$\displaystyle 1-\frac{\mathbb{E}\left[f_{k}(C_{n}^{B})\right]}{\binom{n}{k}}$
$\displaystyle\leq$ $\displaystyle
2\mathbb{P}\left[\mathop{\mathrm{Lah}}\nolimits(n,k)_{\frac{1}{2}}\geq
d\right]$ $\displaystyle=$ $\displaystyle
2\mathbb{P}\left[\frac{\mathop{\mathrm{Lah}}\nolimits(n,k)_{\frac{1}{2}}-\left(k+\frac{1}{2}\right)\log
n}{\sqrt{\left(k+\frac{1}{2}\right)\log n}}\geq\frac{\sqrt{\log
n}\left(\frac{1}{\gamma}+o(1)-\left(k+\frac{1}{2}\right)\right)}{\sqrt{k+\frac{1}{2}}}\right].$

Since $\gamma<\frac{1}{k+\frac{1}{2}}$, the last fraction on the right-hand
side goes to $+\infty$ and Theorem 3.10 implies that the probability goes to
$0$.

Finally, we consider the critical case when (4.4) holds. If the right-hand
side of (4.1) could be replaced with
$\mathbb{P}[\mathop{\mathrm{Lah}}\nolimits(n,k)_{\frac{1}{2}}\leq d]$, we
could once again use Theorem 3.10 in the following way:

$\displaystyle\mathbb{P}[\mathop{\mathrm{Lah}}\nolimits(n,k)_{\frac{1}{2}}\leq
d]$
$\displaystyle=\mathbb{P}\left[\frac{\mathop{\mathrm{Lah}}\nolimits(n,k)_{\frac{1}{2}}-\left(k+\frac{1}{2}\right)\log
n}{\sqrt{\left(k+\frac{1}{2}\right)\log
n}}\leq\frac{d-\left(k+\frac{1}{2}\right)\log
n}{\sqrt{\left(k+\frac{1}{2}\right)\log n}}\right]$
$\displaystyle=\mathbb{P}\left[\frac{\mathop{\mathrm{Lah}}\nolimits(n,k)_{\frac{1}{2}}-\left(k+\frac{1}{2}\right)\log
n}{\sqrt{\left(k+\frac{1}{2}\right)\log n}}\leq-c+o(1)\right]$
$\displaystyle\underset{{d\to\infty}}{\longrightarrow}\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{-c}\mathrm{e}^{-x^{2}/2}\mathop{}\\!{d}x.$

The justification of this replacement can be done as follows (c.f. [16,
Theorem 6.2]). By Proposition 3.18 the largest mode of the $r$-Lah
distribution $m_{n,k,r}$ for $r=1/2$ satisfies

$\displaystyle m_{n,k,\frac{1}{2}}=\left(k+\frac{1}{2}\right)\log
n+O(1)=d+c\sqrt{d}+o(\sqrt{d}).$

Thus, if $c>0$, it follows that $d<m_{n,k,\frac{1}{2}}$ for sufficiently large
$d$. As the $r$-Lah distribution is unimodal, the function
$j\mapsto\mathbb{P}[\mathop{\mathrm{Lah}}\nolimits(n,k)_{\frac{1}{2}}=j]$ is
nondecreasing for all $j\leq d$. We conclude that

$\displaystyle\mathbb{P}[\mathop{\mathrm{Lah}}\nolimits(n,k)_{\frac{1}{2}}\leq
d-2]$ $\displaystyle\leq$ $\displaystyle
2\mathbb{P}[\mathop{\mathrm{Lah}}\nolimits(n,k)_{\frac{1}{2}}\in\\{d-1,d-3,\dotsc\\}]$
$\displaystyle\leq$
$\displaystyle\mathbb{P}[\mathop{\mathrm{Lah}}\nolimits(n,k)_{\frac{1}{2}}\leq
d].$

Applying Theorem 3.10 to both sides of the inequality completes the proof for
$c>0$. The case $c<0$ is similar using (4.3), while the case $c=0$ follows by
a sandwich argument. ∎

######  Remark 4.2.

Take $k=0$ in Theorem 4.1. Then $f_{0}(C_{n}^{B})=0$ or $1$ depending on
whether $C_{n}^{B}=\mathbb{R}^{d}$ or not. In this case, Theorem 4.1 recovers
Corollary 5.4 from [18].

######  Theorem 4.3 (Strong Threshold).

For fixed $k\in\mathbb{N}_{0}$, let $n=n(d)\geq d$ be an integer sequence. If
$n(d)\leq\mathrm{e}^{d/((k+\frac{1}{2})e)}$ for all sufficiently large $d$,
then the random cone $C_{n}^{B}$ is $k$-neighbourly with probability
converging to $1$, more precisely

$\displaystyle\mathbb{P}\left[f_{k}(C_{n}^{B})=\binom{n}{k}\right]=1-O\left(n^{-\frac{1}{2}}\right).$
(4.5)

###### Proof.

On the event $f_{k}(C_{n}^{B})\neq\binom{n}{k}$ it holds that
$\binom{n}{k}-f_{k}(C_{n}^{B})\geq 1$, hence

$\displaystyle\mathbb{P}\left[f_{k}(C_{n}^{B})\neq\binom{n}{k}\right]\leq\mathbb{E}\left[\binom{n}{k}-f_{k}(C_{n}^{B})\right]=\binom{n}{k}\left(1-\frac{\mathbb{E}[f_{k}(C_{n}^{B})]}{\binom{n}{k}}\right).$

In view of (4.3) this gives us

$\displaystyle\mathbb{P}\left[f_{k}(C_{n}^{B})\neq\binom{n}{k}\right]\leq
2n^{k}\mathbb{P}\left[\mathop{\mathrm{Lah}}\nolimits(n,k)_{\frac{1}{2}}\geq(k+1/2)x_{n}\log
n\right]$

with $x_{n}\coloneqq d/((k+1/2)\log n)$. Note that $x_{n}\geq e$ by
assumption. Applying Theorem 3.19 we get

$\displaystyle\mathbb{P}\left[f_{k}(C_{n}^{B})\neq\binom{n}{k}\right]\leq
2n^{k}n^{-(k+\frac{1}{2})(x_{n}\log(x_{n})-x_{n}+1)}$

(the missing fractions can be bounded above by $1$). Since $f(x)\coloneq x\log
x-x+1$ is strictly increasing for $x>1$, we have $f(x_{n})\geq f(e)=1$. Thus

$\displaystyle\mathbb{P}\left[f_{k}(C_{n}^{B})\neq\binom{n}{k}\right]\leq
2n^{k}n^{-(k+\frac{1}{2})}=O\left(n^{-\frac{1}{2}}\right),$

which proves the statement. ∎

##  5\. Application to compressed sensing of monotone signals

Now we present an application of Theorem 4.1 to compressed sensing. The
following general setting has been introduced by Donoho and Tanner [9]. Let
$P\subseteq\mathbb{R}^{n}$ be a polyhedral set, that is, an intersection of
finitely many closed half-spaces (whose bounding hyperplanes need not pass
through the origin). For an unknown signal $x=(x_{1},\dotsc,x_{n})$ from $P$
and a Gaussian random matrix $G:\mathbb{R}^{n}\to\mathbb{R}^{d}$ with $d\leq
n$ we are interested in uniquely recovering the signal from its image $y=Gx$.
This event is denoted by $\text{Unique}(G,x,P)$ and takes place if and only if
$(x+\ker G)\cap P=\\{x\\}$. Donoho and Tanner computed the probability of
unique recovery for $P=\mathbb{R}_{+}^{n}$ (and also $P=[0,1]^{n}$) if $x$ is
$k$-sparse (meaning that it has $k$ non-zero entries) and uncovered threshold
phenomena for this probability in the linear growth regime of $n,k,d$. In the
setting when $k\in\mathbb{N}_{0}$ is constant and $d,n\to\infty$ such that
$d/n\to\delta\in[0,1]$ it is known [14, Proposition 4.3] that

$\lim_{n\to\infty}\mathbb{P}[\text{Unique}(G,x,\mathbb{R}_{+}^{n})]=\begin{cases}1,&\text{if
}\quad\delta>1/2,\\\ 0,&\text{if }\quad\delta<1/2.\end{cases}$ (5.1)

Using the above results on the $r$-Lah distribution with $r=1/2$ we will study
a similar problem for monotone sparse signals. To be precise, our aim is to
recover a monotone signal $x=(x_{1},\dotsc,x_{n})$ that belongs to the Weyl
chamber $B^{(n)}\coloneqq\\{x\in\mathbb{R}^{n}|x_{1}\geq x_{2}\geq\dotsc\geq
x_{n}\geq 0\\}$. We use the following probabilistic model for $x$. Let
$0<k\leq n$ be given together with positive numbers $a_{1},\dotsc,a_{k}$.
Select a random uniform subset $\\{i_{1},\dotsc,i_{k}\\}$ of
$\\{1,\dotsc,n\\}$ with $1\leq i_{1}<\dotsc<i_{k}\leq n$ and define the signal
$x=(x_{1},\dotsc,x_{n})$ by

$x_{m}\coloneqq\sum_{l=1}^{k}a_{l}\mathbbm{1}_{i_{l}\geq m}\qquad\text{for
}m=1,\dotsc,n.$

Note that the entries of $x$ are monotone non-increasing (and non-negative)
and the sparsity parameter $k$ gives the number of jumps in $x$. For $k=0$ we
just put $x=0$. Proposition 3.17 of [12] calculates the probability of the
unique recovery event in the above setting to be

$\mathbb{P}[\text{Unique}(G,x,B^{(n)})]=2\frac{k!}{n!\binom{n}{k}}\sum_{l=0}^{\infty}{n\brack
d-2l-1}_{\frac{1}{2}}{d-2l-1\brace k}_{\frac{1}{2}},$

for $0\leq k\leq d\leq n$, and thus it follows from (4.1) that

$\mathbb{P}[\text{Unique}(G,x,B^{(n)})]=\frac{\mathbb{E}\left[f_{k}(C_{n}^{B})\right]}{\binom{n}{k}}.$

Therefore, Theorem 4.1 yields the following threshold phenomenon for the event
of unique recovery.

######  Theorem 5.1.

Fix $k\in\mathbb{N}_{0}$. Let $d\to\infty$ and $n=n(d)\geq d$ be a function of
$d$ with

$\displaystyle\gamma\coloneqq\lim_{d\to\infty}\frac{\log\bigl{(}n(d)\bigr{)}}{d}\in[0,\infty].$

Let $x\in\mathbb{R}^{n}$ be a random signal in the Weyl chamber $B^{(n)}$
constructed as above. Finally, let $G:\mathbb{R}^{n}\to\mathbb{R}^{d}$ be a
Gaussian random matrix. Then,

$\displaystyle\lim_{d\to\infty}\mathbb{P}[\mathrm{Unique}(G,x,B^{(n)})]=\begin{cases}1,&\text{if
}\quad\gamma<\frac{1}{k+\frac{1}{2}},\\\ 0,&\text{if
}\quad\gamma>\frac{1}{k+\frac{1}{2}}.\end{cases}$

In the critical case $\gamma=\frac{1}{k+\frac{1}{2}}$, if

$\displaystyle\log\bigl{(}n(d)\bigr{)}=\biggl{(}\frac{1}{k+\frac{1}{2}}\biggr{)}\biggl{(}d+c\sqrt{d}+o\Bigl{(}\sqrt{d}\Bigr{)}\biggr{)}$

for some constant $c\in\mathbb{R}$, then

$\displaystyle\lim_{d\to\infty}\mathbb{P}[\operatorname{Unique}(G,x,B^{(n)})]=\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{-c}\mathrm{e}^{-y^{2}/2}\mathop{}\\!{d}y.$

######  Remark 5.2.

For monotone signals in the Weyl chamber
$A^{(n)}\coloneqq\\{x\in\mathbb{R}^{n}|x_{1}\geq x_{2}\geq\dotsc\geq x_{n}\\}$
of type $A$ a similar analysis is possible using Proposition 3.18 in [12] and
replacing $r=1/2$ by $r=0$ throughout. For two more examples with $r=0$, see
Propositions 3.19, 3.20 in [12].

Let us now compare this statement on unique recovery of $k$-sparse monotone
signals to the result (5.1) on unique recovery of $k$-sparse non-negative
signals, with fixed $k$. Roughly speaking, for non-negative signals, (5.1)
states that unique recovery is possible if $d$ is at least $n/2$. On the other
hand, for monotone signals, Theorem 5.1 states that unique recovery is
possible if $d$ is larger than $(k+\frac{1}{2})\log n$. Clearly, one can pass
from a non-negative signal to a monotone one by building the partial sums of
its entries, which does not change the sparsity parameter $k$. The above
results suggest that these partial sums can be compressed at a much higher
rate than the original signal.

### Acknowledgement

Supported by the German Research Foundation under Germany’s Excellence
Strategy EXC 2044 – 390685587, Mathematics Münster: Dynamics - Geometry -
Structure and by the DFG priority program SPP 2265 Random Geometric Systems.

## References

  * [1] A. D. Barbour, E. Kowalski, and A. Nikeghbali.  Mod-discrete expansions.  Probability Theory and related fields, 158(3-4):859–893, 2014.
  * [2] H. Belbachir and A. Belkhir.  Cross recurrence relations for r-Lah numbers.  Ars Combinatoria, 110:199–203, 2013.
  * [3] A. Broder.  The $r$-Stirling numbers.  Discrete Mathematics, 49(3):241–259, 1984.
  * [4] G.-S. Cheon and J.-H. Jung.  $r$-Whitney numbers of Dowling lattices.  Discrete Mathematics, 312:2337–2348, 2012.
  * [5] F. Delbaen, E. Kowalski, and A. Nikeghbali.  Mod-$\phi$ convergence.  International Mathematics Research Notices, 2015(11):3445–3485, 2015.
  * [6] D. L. Donoho.  High-dimensional centrally symmetric polytopes with neighborliness proportional to dimension.  Discrete and Computational Geometry, 35(4):617–652, 2006.
  * [7] D. L. Donoho and J. Tanner.  Neighborliness of randomly projected simplices in high dimensions.  Proc. Natl. Acad. Sci. USA, 102(27):9452–9457, 2005.
  * [8] D. L. Donoho and J. Tanner.  Counting faces of randomly projected polytopes when the projection radically lowers dimension.  Journal of the American Mathematical Society, 22(1):1–53, 2009\.
  * [9] D. L. Donoho and J. Tanner.  Counting the faces of randomly-projected hypercubes and orthants, with applications.  Discrete Computational Geometry, 43(3):522–541, 2010.
  * [10] V. Féray, P. Méliot, and A. Nikeghbali.  Mod-$\phi$ convergence.  SpringerBriefs in Probability and Mathematical Statistics, 1st edition, 2016.
  * [11] J. L. Fields.  The uniform asymptotic expansion of a ratio of two gamma functions.  In Proceedings of the International Conference on Constructive Function Theory, pages 171–176, Varna, Bulgaria, 1970.
  * [12] T. Godland and Z. Kabluchko.  Angle sums of Schläfli orthoschemes.  Discrete and Computational Geometry, 68:125–164, 2022.
  * [13] T. Godland and Z. Kabluchko.  Positive hulls of random walks and bridges.  Stochastic Processes and their Applications, 147:327–362, 2022\.
  * [14] T. Godland, Z. Kabluchko, and C. Thäle.  Random cones in high dimensions I: Donoho-Tanner and Cover-Efron cones.  Discrete Analysis, 2020(5), 2020.
  * [15] J. Jacod, E. Kowalski, and A. Nikeghbali.  Mod-Gaussian convergence: new limit theorems in probability and number theory.  Forum of Mathematics, 23(4):835–873, 2011.
  * [16] Z. Kabluchko and A. Marynych.  Lah distribution: Stirling numbers, records on compositions, and convex hulls of high-dimensional random walks.  Probability Theory and Related Fields, 184:969–1028, 2022.
  * [17] Z. Kabluchko, A. Marynych, and H. Sulzbach.  General Edgeworth expansions with applications to profiles of random trees.  Annals of Applied Probability, 27(6):3478–3524, 2017.
  * [18] Z. Kabluchko, V. Vysotsky, and D. Zaporozhets.  Convex hulls of random walks, hyperplane arrangements, and Weyl chambers.  Geometric and Functional Analysis, 27(4):880–918, 2017.
  * [19] E. Kowalski and A. Nikeghbali.  Mod-Gaussian convergence and the value distribution of $\zeta(1/2+it)$ and related quantities.  Journal of the London Mathematical Society, 86(1):391–319, 12 2009\.
  * [20] E. Kowalski and A. Nikeghbali.  Mod-Poisson convergence in probability theory and number theory.  International Mathematics Research Notices, 18:3549–3587, 2010\.
  * [21] I. Lah.  A new kind of numbers and its application in the actuarial mathematics.  Boletim do Instituto dos Actuários Portugueses, 9:7–15, 1954\.
  * [22] R. Merris.  The $p$-Stirling numbers.  Turkish Journal of Mathematics, 24:379–399, 2000.
  * [23] I. Mező.  On the maximum of $r$-Stirling numbers.  Advances in Applied Mathematics, 41(3):293–306, 2007.
  * [24] I. Mező.  Combinatorics and number theory of counting sequences.  Discrete Mathematics and Its Applications. Boca Raton, CRC Press, 2020\.
  * [25] P. Méliot and A. Nikeghbali.  Mod-Gaussian convergence and its applications for models of statistical mechanics.  In In memoriam Marc Yor—Séminaire de Probabilités XLVII, volume 2137 of Lecture Notes in Math., pages 369–425. Springer, Cham, 2015.
  * [26] G. Nyul and G. Rácz.  The $r$-Lah numbers.  Discrete Mathematics, 338(10):1660–1666, 2015.
  * [27] M. Petkovsek and T. Pisanski.  Combinatorial interpretation of unsigned Stirling and Lah numbers.  Pi Mu Epsilon Journal, 12:417–424, 2007.
  * [28] M. Shattuck.  Generalized $r$-Lah numbers.  Proc. Indian Acad. Sci. Math. Sci., 126(4):461–478, 2016.
  * [29] M. Sibuya.  Log-concavity of Stirling numbers and unimodality of Stirling distributions.  Ann. Inst. Statist. Math., 40(4):693–714, 1988.
  * [30] A. M. Vershik and P. V. Sporyshev.  Asymptotic behavior of the number of faces of random polyhedra and the neighborliness problem.  Selecta Math. Soviet., 11(2):181–201, 1992.