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

- start at $0$
- stay in $[0,n]\cap\mathbb{Z}$ for precisely $m$ steps.
- (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.