Number of walks

Question

How many walks (asymptotically) of length $2n$ with up or right steps from $(0,0)$ to $(n,n)$ are there such that the walk is always between the lines $y=x+k$ and $y=x-k$?

Answer 1

The number is very small. Here is a possible approach. Here we assume $n\gg k$ and we denote a walk with the constraints you mention as admissible. Given any walk of length $L$ and $j\in \{1,\dotsc, L\}$ we denote by $(H_j, V_j)$ the location at time $j$. Thus $H_j$ is the number of horizontal steps taken up to the moment $j$ and similarly, and $V_j$ is the number of vertical steps taken up to the time $j$. A path is admissible if $-k\leq V_j-H_j\leq k$, $\forall j$. $V_{2n}=H_{2n}=n$.

To a walk $W$ in the lattice $\newcommand{\bZ}{\mathbb{Z}}$ $\bZ^2$ we associate a walk $W'$ in the lattice $\bZ$ starting at $0$ as $0$. If at time $j$ in $W$ we take a vertical steps, then in $W'$ we move one unit to the right. If at time $j$ in $W$ we take a horizontal step, then in $W'$ we take a step to the left.

Now think of the walks in $\mathbb{Z}^2$ as random walks where the horizontal/vertical steps have the same probability. We have thus associated to a random walk $W$ in $\bZ^2$ a standard one-dimensional walk $W'$ on $\bZ$. The walk $W$ is admissible if and only if the corresponding walk $W'$ starts and ends at $0$ and never leaves the interval $[-k,k]$. Denote by $T(W')$ the first moment steps outside the interval $[-k,k]$. The probability that $T(W')> 2n$ is known. Walks in the interval $[-k-1,k+1]$ with absorbing boundary seem relevant. (I have to leave.)

Edit. Had a busy weekend. I have two comments.

1. Ira Gessels's comment answers the original question more precisely than my speculations above.

2. My above speculations can still be used to provide an asymptotic estimate for $n$ large. More precisely if $W_k(n)$ is the number of walks from $(0,0)$ to $(n,n)$ that do not cross the lines $y=x\pm k$, then

$$ W_k(n)\sim \left(\; 2\cos\frac{\pi}{2k+2}\;\right)^{2n}\;\;\mbox{as}\;\;n\to \infty. $$

This approach also yields an explicit expression in terms of Chebyshev polynomials for the generating function of the number of walks from $(0,0)$ to $(n,n)$ that do cross the lines $y=x\pm k$; see (3). Here are the details.

Denote by $p_k(n)$ the probability that a random walk on $\bZ$ starts and ends at $0$ after $2n$ steps and never reaches the locations $\pm(k+1)$. Form the generating series

$$ P_k(x)=:\sum_{n\geq 0} p_k(n)x^{2n}. $$

Using the idea of the random walk on $[-(k+1),(k+1)]$ with absorbing boundary one can give an explicit description of $P_k(x)$ as a rational function.

For any natural number $m$ denote by $Q_m$ the $m\times m$ symmetric matrix with entries

$$q_{ij}=\begin{cases}\frac{1}{2}, &|i-j|=1\\ 0, & |i-j|\neq 1. \end{cases}. $$

Then $p_k(n)$ is equal to the $(k+1,k+)$-entry of the matrix $Q_{2k+1}^{2n}$, i.e., the entry of this odd-sized matrix located dead in the center. (This is not hard to see. Alternatively, check any book on Markov chains. $Q$ corresponds to the transient part of this Markov chain.)

This shows that $P_k(x)$ is the $(k+1,k+1)$ entry of the matrix $(1-xQ)^{-1}$ and from the expression of a the entries of the inverse of a matrix in terms of the minors of the matrix we deduce

$$P_k(x)=\frac{\det(1-xQ_k)^2}{\det(1-xQ_{2k+1})}. $$

The special shape of the matrices $Q_m$ leads to a recursive computations of the determinants of $1-xQ_m$. Hint: the matrix $1-xQ_m$ is a Jacobi matrix and, if $D_m(x):=\det(1-xQ_m)$, then

$$D_m(x)=D_{m-1}(x)-\frac{x^2}{4} D_{m-2}(x). $$

This leads to an explicit, albeit complicated expression of $P_k(x)$ in terms of Chebyshev polynomials; see (2).

In any case the above expression shows that the asymptotic behavior of $p_{k}(n)$ is determined by the eigenvalues of $Q_{2k+1}$. It is not hard to see that the spectrum of this symmetric matrix is contained in $(-1,1)$. $\DeclareMathOperator{\spec}{spec}$ If

$$\Lambda_k=\max\bigl\{\; |\lambda|;\;\;\lambda\in\spec(Q_{2k+1})\;\bigr\}<1, $$

then we deduce that

$$ p_k(n)=O(\Lambda_k^{2n}), \;\;n\to\infty. $$

I believe that

$$p_k(n) \sim C_k\Lambda_k^{2n}, $$

so the asymptotics of the number of walks you asked about would be

$$\sim C (2\Lambda_k)^{2n}. $$

The spectrum of $Q_m$ is known. More precisely

$$\spec Q_m =\Bigl\{ \cos \frac{k\pi}{m+1};\;\;k=1,\dotsc, m\;\Bigr\}. $$

For details see these beautiful answers to a MO question. Thus

$$ p_k(n) \sim C_k\Bigl(\cos\frac{\pi}{2k+2}\Bigr)^{2n}, \tag{1} $$

for some constant $C_k$ described explicitly in (4) below.

Remark. Let us denote by $W_k(n)$ the number of East-North walks in the lattice $\bZ^2$ which start at $(0,0)$, end at $(n,n)$ and do not cross the lines $y=x\pm k$. We form the generating series

$$W_k(x)=\sum_{n\geq 0} W_k(n)x^{2n}. $$

Then

$$W_k(x) =P_k(2x). $$

Let us express $P_k(x)$ in terms of the characteristic polynomials $\Delta_m(x)$ of the matrices $Q_m$. We have

$$D_m(x)=\det(1-xQ_m)= x^m \det(x^{-1}-Q_m) =x^m \Delta_m(x^{-1}). $$

We have

$$\Delta_m(x)= x\Delta_{m-1}(x)-\frac{1}{4}\Delta_{m-2}(x). $$

In particular, if $S_m(x)=2^{m} \Delta_m(x)$, then we deduce that

$$S_m(x)= 2xS_{m-1}(x) -S_{m-2}(x). $$

This is precisely the recurrence relation satisfied by the Chebyshev polynomials $T_m(x)$, $U_m(x)$ defined by

$$ T_m(\cos \theta)=\cos(m\theta),\;\;U_m(\cos\theta)=\frac{\sin(m+1)\theta}{\sin\theta}. $$

Note that

$$ S_1(x) =2x=U_1(x), \;\; S_2(x)=4x^2-1=U_2(x). $$

Hence $S_m(x)=U_m(x)$ so that

$$\Delta_m(x)=\frac{1}{2^m} U_m(x),\;\; D_m(x)=\left(\frac{x}{2}\right)^m U_m(1/x), $$

$$ D_m(2x)= x^m U_m\left(\frac{1}{2x}\right), $$

$$P_k(x)=\frac{4}{x^2}\frac{U_k(1/x)^2}{U_{2k+2}(1/x)},\;\;\tag{2} $$

$$ W_k(x)= \frac{U_{k}\bigl(\frac{1}{2x}\bigr)^2}{x^2 U_{2k+2}\bigl(\frac{1}{2x}\bigr)}. \tag{3} $$

We can say something about the constant $C_k$ in (1) by observing that

$$ D_m(x) =A_m\prod_{j=1}^m\left(1-x\cos\frac{j\pi}{m+1}\right), $$

for some constant $A_m$. More precisely

$$ A_m=2^{-m}\times \mbox{ the leading coefficient of $U_m$}=1.$$

Then

$$ P_k(x)= \frac{A_k^2}{A_{2k+2}}\frac{\prod_{j=1}^k (1-x\cos\frac{j\pi}{k+1})}{\prod_{\ell=1}^{k+1}(1-x\cos \frac{(2\ell-1)\pi}{2k+2})}. $$

This shows that

$$ C_k=\frac{A_k^2}{A_{2k+2}}=1.\tag{4} $$

Update 2. As I suspected all along, this problem has been thoroughly investigated. There is a comprehensive discussion of this and other problems in Chapter XIV, Sect. 4,5 vol 1 of Feller's book. This problem also makes its appearance in the Kolmogorov-Smirnov statistics test; see Chap I, Sec. 12, vol. 2 of Feller's book on probability., or Feller's article On the Kolmogorov-Smirnov limit theorems for empirical distributions, Ann. Math. Statistics, 19(1948), 177-189.