Choose uniformly from fixed-length paths in $[0,n]\cap\mathbb{Z}$ with fixed start and end

Question

Let $X_k$ be a symmetric (discrete time) random walk on $\mathbb{Z}$ and let $m,n\in\mathbb{N}$. I want to chose uniformly from the paths of $X_k$, which

1. start at $0$
2. stay in $[0,n]\cap\mathbb{Z}$ for precisely $m$ steps.
3. (optional: chosing only among those that leave to the left or chosing only among those that leave to the right)

Of course m will be chosen such that this path space is not empy.

I'll give my thoughts below, of course those may be skipped if the answer is known to someoone.

---

Thoughts so far: All paths of length $m$ have the same probability (namely $0.5^m$) and, if we use the requirement 3., they all have the same number of steps to the right $m_r$ (and hence of steps to the left $m_l$). I also think I could compute the number of such paths because I know how to calculate $\mathbb{P}(X_{m+1}=n+1 | X_0=0 ; X_{[0,m]}\in[0,n])$ and I could calculate the quotient of that number and $0.5^m$.

Of course we can not simply use the urn problem and draw left and right steps (without placing back) from the known totals, because this would allow paths that temporarily leave the interval. A possible fix might be to not allow drawing a step to the left, for example, when one has drawn such that the walk would stay at $0$ before the next step, but I'm not sure that this would generate samples that are uniformly distributed among the paths that fullfil the criteria given above.

My other idea was to try to find some scheme that counts through all possible paths, one could then simply chose some number from 1 to the (known) total number of paths. One idea to count all paths (with fixed end point), would be to start with

+-+-+-+...-+-++....++++++

++--+-+...-+-++....++++++

++-+--+...-+-++....++++++

...

+++++...----++....++++++

+-+-+-+...-++-+....++++++

...

(+ means one step to the right) But that looks like a lot of work and I'm not sure I can find some way to express the bijection between the numbers from 1 to the total amount of such paths and the paths.

Answer 1

You can use a "dynamic programming" solution. For anyone unfamiliar with this terms, the basic idea is that there are an exponential in $n,m$ number of possible paths, so it takes too long to enumerate them all. But we can express everything we need to know about the problem using a small "state" consisting of where the walk currently is located and how many steps are left. Specifically, we compute the number of paths that reach the end goal starting from each state. To do so, we use induction starting with the base cases of having $0$ steps left, then solve all the cases with $1$ step left, and so on. Because there are only $nm$ cases, this is computationally feasible relative to enumerating paths.

I'll focus on paths that leave from, say the left side. The right-side case is exactly analogous, and the case where they can leave from both sides should be easy by solving each case separately and "adding" them together.

What we want is to be able to compute $$ K(a,b) $$ which is defined as "the number of distinct paths starting from location $a$ that stay in $\{0,\dots,n\}$ for precisely $b$ steps before exiting through the left side." In particular, this will give us $K(0,m)$ which is the total number of paths you care about.

This allows us to sample a walk iteratively: if we are at location $a$ after taking $m-b$ steps (having $b$ remaining), then move right with probability $\frac{K(a+1,b-1)}{K(a+1,b-1) + K(a-1,b-1)}$. (This relies on all paths being equally likely, thanks to symmetry of the random walk.)

Now we can compute these via dynamic programming. Say we care about paths leaving from the left side. First the "base case" where $b=0$, where we should be at location $-1$ (having just exited). There is one valid path from that location and zero valid paths from all others. \begin{align} K(-1,0) &= 1 \\ K(a,0) &= 0 & (a \geq 0) \end{align} Then in the general case, we get this: \begin{align} K(-1,b) &= K(n+1,b) = 0 & (b > 0) \\ K(a,b) &= K(a-1,b-1) + K(a+1,b-1) & (0 \leq a \leq n, b > 0) \end{align} It says there are zero paths going through $-1$ or $n+1$ at any point other than $b=0$. For $0 \leq a \leq n$, the number of paths going through location $a$ with $b$ steps remaining is the sum of the consequences of the two choices, i.e. the paths through $a-1$ or through $a+1$ with $b-1$ steps remaining.

In psuedocode:

# computing K
K = two-dimensional array
K(-1,0) = 1
for a in {0,...,n+1}:
  K(a,0) = 0
for b in {1,...,m}:
  K(-1,b) = 0
  K(n+1,b) = 0
  for a in {0,...,n}:
    K(a,b) = K(a-1,b-1) + K(a+1,b-1)

# sample a random walk
a = 0  # starting point
for j in {1,...,m}:
  r = rand()  # uniform[0,1]
  if r < K(a-1,m-j-1)/(K(a-1,m-j-1) + K(a+1,m-j-1)):
    print("move left")
    a -= 1
  else:
    print("move right")
    a += 1

Warning: My solution may have an off-by-one error depending how you define "stays in $\{0,\dots,n\}$ for exactly $m$ steps."