MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $D$ be the set of all Dyck paths on square grid of size $n\times n$. For any particular Dyck path, let $S(t)=X_1+X_2+\ldots +X_t$ store the path, where $X_i=\pm 1$. Being a Dyck path, we have $S(0)=0$ and $S(2n)=0$.

Consider picking uniformly random Dyck paths from the set $D$. Let $P_t(x)$ denote the probability distribution of $X_t$ subject to the uniform distribution on Dyck paths. Suppose that $n$ is very large and that I pick a uniformly random Dyck path conditioned on having the first $k$ steps being fixed, where $k=o(n)$. I would like to conclude that $\mathbb{P}(X_t=x | \mbox{first $k$ steps})\approx P_t(x)$ for $t>>k$. Is there a straightforward way of doing this? In other words, far away steps become asymptotically independent from the first $k$ steps. In general, is there a way of extending this to uniformly random paths of fixed length on regular graphs?

I can see that this is probably related to asking a similar question for brownian bridges. Specifically, I am very interested in seeing how one would obtain explicit bounds for the quantity $|\mathbb{P}(X_t=x | \mbox{first $k$ steps})-P_t(x)|$ in terms of $n$ and $t$

share|cite|improve this question
This reference might be useful. In particular, I would guess that Theorem 3 could be modified for a problem of this form. – Stephen DeSalvo Aug 4 '13 at 12:35

This is unfinished, but I'm not sure I will complete it and some of it may be useful.

You can count the Dyck paths which pass through each point or set of points. The number of lattice paths from $(0,0)$ to $(a,b)$ with $a\ge b$ which do not go above the diagonal is

$${a+b \choose a} - {a+b \choose a+1} = \frac{a-b+1}{a+1} {a+b \choose a}$$

by reflection. The number of Dyck paths through $(a,b)$ is

$$\frac{a-b+1}{a+1} {a+b \choose a} \frac{a-b+1}{n-b+1} {2n-a-b \choose n-a} $$

You can write that in a few ways. See this question.

The number of paths from $(a,b)$ to $(c,d)$ which do not go above the diagonal is

$${(c+d)-(a+b)\choose c-a} - {(c+d)-(a+b)\choose c-b+1}.$$

You can use these to write expressions for the average distance of a Dyck path from the diagonal before and after step $t$. The difference tells you how often step $t$ is horizontal versus vertical, $\mathbb P_t(x)$ in your notation.

Although the average area between a Dyck path and the diagonal has a nice closed form expression, I don't think these average distances do. However, it should be possible to use Laplace's method to estimate these averages.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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