5
$\begingroup$

It is known that the expected number of returns of a Dyck path of semilength $n$ to the $x$-axis is $3n/(n+2)$, so it tends to 3 as $n\to\infty$. (This was proved in the Dyck path context by Deutsch in Equation (6.23) of his 1999 paper "Dyck path enumeration", but in the equivalent context of ordered trees, the result dates back to at least Dershowitz and Zaks' 1980 paper "Enumerations of ordered trees", where it is Corollary 4.1.)

The computations necessary to compute the exact value of this expected value are not difficult, and there is a fairly intuitive explanation of why the answer should tend to 3, given that Dyck paths are counted by the Catalan numbers, which are approximately $4^n$.

Instead I ask is there a simple and intuitive explanation for why the expected number of returns of a Dyck path should be finite in the first place?

(In the language of Chapter V.2 of Flajolet and Sedgewick's Analytic Combinatorics, I am essentially asking for an intuitive explanation of why the Catalan numbers do not form a supercritical sequence.)

$\endgroup$
4
$\begingroup$

I am not sure that the following qualifies for a simple and intuitive explanation, but it may shed some light from a probabilistic perspective in a more general context of random trees:

  • as in the Dershowitz and Zaks' paper, the number returns of a random uniform Dyck path of semilength $𝑛$ to the $𝑥$-axis has the same distribution as the outdegree of a uniform random plane tree with $2n$ edges.

  • it is well known that a uniform random plane tree with $2n$ edges has the same distribution as a Bienaymé-Galton-Watson random tree with geometric $1/2$ offspring distribution, conditioned to have $2n$ edges.

Now consider a more general critical offspring distribution $\mu$ (a probability distribution on the non-negative integers with mean $1$), and assume that: $\mu(0)+\mu(1)<1$ (to avoid trivial cases), $\mathbb{P}(T \text{ has } n \text{ vertices})>0$ for every $n$ sufficiently large (to avoid periodicity) and that the variance of $\mu$ is finite (these assumptions are satisfied for the geometric $1/2$ offspring distribution).

Let $T$ be a non-conditioned Bienaymé-Galton-Watson tree with offspring distribution $\mu$ (roughly speaking, one starts with an ancestor which has a random number of children distributed according to $\mu$, then each one of its children has an independent random number of children distributed according to $\mu$, and so on) and let $T_n$ be a Bienaymé-Galton-Watson tree with offspring distribution $\mu$ conditioned on having $n$ vertices (which is well defined for $n$ suffficiently large).

By using the coding of BGW trees by the so-called Lukasiewicz path (see e.g. Section 1.1 here), if $(S_n)_{n \geq 0}$ is a random walk on the integers starting from $0$ and with jump distribution given by ${S}_1=\mu(i+1)$ for $i \geq -1$, and using the cyclic lemma (see e.g. Section 5 here), one gets that

\begin{eqnarray*} \mathbb{P}(\text{degree root}(T_n) =k) & = \mu(k) \frac{\mathbb{P}(\text{a random forest with } k \text { trees has } n-1 \text{ vertices})}{\mathbb{P}(T \text{ has n vertices})} \\ & = \mu(k) \frac{ \frac{k}{n-1} \mathbb{P}(S_{n-1}=-k)}{\frac{1}{n}\mathbb{P}(S_n=-1)}. \end{eqnarray*}

By the local limit theorem, there exists a constant $C>0$ such that $\frac{\mathbb{P}(S_{n-1}=-k)}{\mathbb{P}(S_n=-1)} \leq C$ for every $n$ sufficiently large and $k \geq 1$, so that for every $n$ sufficiently large and $k \geq 1$ $$ \mathbb{P}(\text{degree root}(T_n) =k) \leq C k \mu(k).$$ It follow that $\mathbb{E}[\text{degree root}(T_n)]$ is bounded since $\mu$ has finite variance.

Also, another reason that the expected number of returns of a Dyck path of semilength $𝑛$ to the $𝑥$ tends to $3$ is that $3$ is the expectation of a size-biased geometric $1/2$ random variable. Indeed (see this survey for details):

  • Large random Bienaymé-Galton-Watson trees with critical offspring distribution converge in distribution for the local topology to the so-called Kesten's infinite random tree.

  • In this infinite random tree, the outdegree of the root follows a size biased distribution.

  • As a consequence, the number of returns of a Dyck path of semilength $𝑛$ to the $𝑥$-axis converges in distribution to a size-biased geometric $1/2$ random variable, and one can see that this convergence also holds in expectation.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.