5
$\begingroup$

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$

$\endgroup$
1

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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