Paths on a grid that don’t go below $0$ or above $l$ before reaching their target.

catalan-numberscombinatoricsprobabilityrandom walk

A gambler tosses a coin repeatedly, gaining $1\$$ on heads and losing $1\$$ on tails.

The number of ways he can reach $l\$$ after $t+l$ heads and $t$ tails without ever crossing $l\$$ is given by $C_t^{(l)}={2t+l \choose t}\frac{l}{2t+l}$. This is shown here: Probability that random walk will reach state $k$ for the first time on step $n$. The generating function for this sequence is discussed here: Proof of identity about generalized binomial sequences..

This also happens to be the number of paths where he reaches $l\$$ after $2t+l$ tosses without ever going below $0\$$. This can be easily seen by reversing the paths and becomes Bertrand's ballot problem.

Now, how about paths where both conditions are satisfied. This means he can't go below $0\$$ or above $l\$$ at any time during his path?

Best Answer

The problem can be solved in a similar way to the Bertrand's ballot problem.

Preliminarily we consider alternative reflections of the point $(0,0)$ in two lines $y=x+a$ and $y=x+b$. It can be easily shown that the $k$-th reflection has the coordinates: $$ (-1)^k\left(\left\lceil\frac k2\right\rceil a -\left\lfloor\frac k2\right\rfloor b,\left\lfloor\frac k2\right\rfloor b-\left\lceil\frac k2\right\rceil a\right),\tag1 $$ if the point is first reflected about $y=x+a$. If it is first reflected about $y=x+b$, $a$ and $b$ in (1) are to be interchanged.

Let us represent the toss sequence as a lattice path on the Cartesian plane as follows:

  1. Start the path at $(0, 0)$.
  2. Each head is a move right 1 unit.
  3. Each tail is a move up 1 unit.

Our aim is to hit the point $(p,q)=(t+l,t)$ never crossing the lines $y=x$ and $y=x-l$. The overall number of paths is $\binom{2t+l}t$ which should be decreased by the number of paths which cross at least once the above mentioned lines.

To compute the number of the 'bad' paths we proceed very similar to the procedure described in the link given in the beginning of the answer. The end point of every path crossing the line $y=x$ from below lies on the line $y=x+1$, and the end point of every path crossing the line $y=x-l$ from above lies on the line $y=x-l-1$.

For each 'bad' path $P$, define a new path $P′$ by reflecting the part of $P$ up to the first point it touches the line across it. $P′$ is a path from $(−1, 1)$ to $(p, q)$ if we touch the line $y=x+1$ or from $(l+1,-l-1)$ to $(p, q)$ if we touch the line $y=x-l-1$ (cf. (1) with $k=1,a=1,b=-l-1$).

This is however not yet the end of story, since there can exist the paths which cross both $y=x+1$ and $y=x-l-1$. By the above counting each such path will be count as 'bad' twice. So we need to add number of such paths, which can be computed as follows. Assume a path $P'$ with already reflected initial part (about the boundary line it meets first) crosses the other boundary line. Define a new path $P''$ by reflecting the part of $P'$ up to the first point it touches the second boundary line across the line. The initial point of all such paths (which cross both boundary lines in the same order) will be reflection of the point $(0,0)$ first about the first line and then about the second one. Observe that the initial point is again $2t+l$ steps apart from the final point $(p,q)$. This process of reflecting can be repeated for the longer paths which repeatedly cross the upper and lower boundary lines in alternating order.

Substituting in (1) $a=1,b=-l-1$ one obtains that the $y$-coordinate of the $k$-th reflection of the point $(0,0)$ is $$ \begin{cases} -(-1)^k\left\{k+\left\lfloor\frac k2\right\rfloor l\right\},& \text{if the first reflection is across }y=x+1\\ \hphantom{-}(-1)^{k}\left\{k+\left\lceil\frac k2\right\rceil l\right\},& \text{if the first reflection is across }y=x-l-1 \end{cases}. $$

With this at hand the final expression for the number of ways for reaching the final point without crossing the boundary lines reads: $$ \binom{2t+l}t+\sum_{k\ge1}(-1)^k \left[\binom{2t+l}{t+(-1)^k\left\{k+\left\lfloor\frac k2\right\rfloor l\right\}} +\binom{2t+l}{t-(-1)^k\left\{k+\left\lceil\frac k2\right\rceil l\right\}} \right]. $$