9
$\begingroup$

A Catalan path of semilength $n$ is a path from $(0,0)$ to $(2n,0)$ that proceeds by taking northeast (1,1) or southeast (1,-1) steps, and never goes below the $x$-axis. The area of a path $P$ is the area beneath the path and above the $x$-axis. So, for example, the path of semilength 3 that goes $(0,0)-(1,1)-(2,2)-(3,1)-(4,0)-(5,1)-(6,0)$ has area $5$.

The sum of the area of all Catalan paths of semilength $n$ is known to be $4^n - \binom{2n+1}{n}$, so that the average area of a path is on the order of $n^{3/2}$.

In an application I'm working on, I've found that it would be useful to have upper bounds on how many paths have area significantly greater than $n^{3/2}$. The largest possible area is $n^2$, and from Markov's inequality I can say that a vanishing proportion of paths have area greater than $n^2/1000$, say; specifically, there are no more than $O\left(4^n/n^2\right)$ such paths (whereas there are $\Theta\left(4^n/n^{3/2}\right)$ paths in total).

I suspect that there are far fewer paths with large area, and for my application I need a much lower upper bound. Are there quantitative results for this problem?

I can translate the problem into that of estimating the number of partitions of the number $N$ into at most $c\sqrt{N}$ parts each of size at most $c\sqrt{N}$, which in turn becomes a problem of estimating a coefficient of a Gaussian polynomial, but I'm not aware of quantatitive results here, either.

$\endgroup$
  • $\begingroup$ The maximum area is $n^2$, I think. $\endgroup$ – T. Amdeberhan May 13 '17 at 3:45
  • 1
    $\begingroup$ Bernoulli excursion is another name (more popular among probabilists) for Catalan path. Look at A Bernoulli Excursion and Its Various Applications by Takács for quantitative results on the area statistic of the Bernoulli excursion as well as its scaling limit, the (normalized) Brownian excursion. $\endgroup$ – HMPanzo May 13 '17 at 3:53
  • $\begingroup$ What might be of help here is the Large deviations theory. $\endgroup$ – Ivan Izmestiev May 13 '17 at 7:14
  • 1
    $\begingroup$ An update to my answer: today I learned that the distribution has been already investigated and it is of Airy-type. See the article "Analytic Variations on the Airy Distribution" by Flajolet and Louchard: algo.inria.fr/flajolet/Publications/FlLo01.pdf $\endgroup$ – Sergey Dovgal May 15 '17 at 16:09
5
$\begingroup$

Notice that the number of Catalan paths of area at least $cn^{\frac{3}{2}+\varepsilon}$ is less than the number of all paths that deviate from the horizontal axis by at least $n^{\frac{1}{2}+\varepsilon}$. Let $(S_k, k\geq 0)$ be the one-dimensional simple random walk starting from the origin. We need to find an upper bound for the following probability: $$P\big[\max_{k\leq 2n}S_k > n^{\frac{1}{2}+\varepsilon}\big].$$

Now, one may use e.g. a Chernoff's bound for the Binomial distribution (together with the Reflection Principle if you don't want an extra polynomial term in front, see e.g. Chapter III of the Feller's book) to obtain that the above probability is upper bounded by $\exp(-c'n^{\varepsilon})$. So, the total number of such paths is at most $4^n\exp(-c'n^{\varepsilon})$.

$\endgroup$
5
$\begingroup$

An attempt to provide the whole distribution using analytic combinatorics (though one answer is already accepted). In particular, we can obtain the first and the second moment using this technique (and maybe some more by induction if you want a limiting distribution and not only first two moments).

The generating function for Catalan paths $$ Cat(z) = \sum_{n \geq 0} c_n z^n $$ satisfies an equation $$ Cat(z) = z^2 Cat(z) + 1 \enspace , \quad Cat(z) = \dfrac{1 - \sqrt{1 - 4z^2}}{2z^2} $$ where 1 corresponds to an empty path, then $z Cat(z) \cdot z$ corresponds to $ \nearrow$ times Catalan path times $\searrow$, then another Catalan path $Cat(z)$. The idea is to mark the area inside Catalan path, i.e. consider a bivariate generating function $$ C(z,u) = \sum_{n, k \geq 0} c_{n,k}z^n u^k \enspace , $$ where $ c_{n,k}$ is equal to the number of Catalan paths of semilength $n$ and area $k$. An equation here is the following one: $$ C(z,u) = z^2 u C(zu^2, u)C(z,u) + 1 $$ Explanation: the first part which starts from $\nearrow \ldots \searrow$ is a Catalan path of area $k + 2n + 1$, where $k$ is the area of upper part, $n$ is the semilength and $1$ is because you glue two parts of a triangle. For that reason, $$ uC(zu^2,u) = u\sum_{n, k \geq 0} c_{n,k}(zu^2)^n u^k = \sum_{n,k \geq 0} c_{n,k} z^n u^{k + 2n + 1} \enspace . $$ The second Catalan part is glued without chantings, i.e. we count already existing area as an additional summand.

Next step is to obtain the moments from the functional equation. Though the equation cannot be solved explicitly, we can still obtain some information. Recall that k-th factorial moment is given by $$ \dfrac{[z^n] \partial_u^k C(z,u) |_{u=1}}{[z^n] Cat(z)} $$ I denote $ C^\square(z) = \partial_u C(z,u)|_{u=1} $, $ C^{\square\square}(z) = \partial^2_u C(z,u)|_{u=1} $ for brevity. Let's take a derivative then: $$ C^\square(z) = z^2 C^2(z) + z^2 C^\square(z) C(z) + z^2(2C_z + C^\square)C(z) \enspace , $$ where $ C_z(z) := \partial_z C(z) $. Thus, $C^\square(z)$ can be explicitly expressed through $C(z) $ and $\partial_z C(z)$, and that's how you can obtain (already present) result on expectation of the area.

Then you can repeat and obtain explicit expression for the second derivative, thus having a bound for the variance. In principle, you can try to derive some general pattern on the moments of this distribution (or more concretely, on the singularity $\rho(u)$ and nature of singularity of complex function $C^{k\square}(z)$), and apply Theorem IX.8 from Analytic Combinatorics of Flajolet and Sedewick. I believe that some of the summands in the functional equation will be negligible which will simplify the analysis.

UPD: Actually, it happens that corresponding distribution is of area Airy type. See the article "Analytic Variations on the Airy Distribution" by Flajolet and Louchard: http://algo.inria.fr/flajolet/Publications/FlLo01.pdf

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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