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$?



Number of walks
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](https://mathoverflow.net/questions/91161/eigenvectors-and-eigenvalues-of-tridiagonal-matrix/91229#91229) 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.


