How can I prove this bijection between random walks?

Let

$$R_n$$ be the set of simple random walk paths such that $$S_n=0.$$

$$P_n$$ be the set of simple random walk paths such that $$\forall i \in \{1,2,...,n\},$$ $$S_i > 0$$.

$$N_n$$ be the set of paths such that $$\forall i \in \{1,2,...,n\}, S_i \geq 0$$.

Assume that all random walk paths start at the origin.

How can I show that there is a bijection between $$P_{2n}$$ and $$N_{2n-1}$$ and that there is a bijection between $$R_{2n}$$ and $$N_{2n}$$. Basically I want to show that a path in $$R_{2n}$$ with minimum value $$k$$ corresponds to a path in $$N_{2n}$$ with terminal value $$2k$$.

For this I'm thinking about cutting or shifting or reflecting paths. I don't think probability matters here. But I'm stuck on formulating the proofs.

If we have sequence $$S_0,S_1,...,S_n$$ which is represented by a polygonal line with segments $$(k-1,S_{k-1}) \rightarrow (k,S_k)$$ a path is a polygonal line that is a possible outcome of simple random walk.

• Please define these "random walk paths" that you are using; I don't think this is common terminology. – darij grinberg Apr 1 at 23:42
• Sorry. if we have sequence $S_0,S_1,...,S_n$ which is represented by a polygonal line with segments $(k-1,S_{k-1}) \rightarrow (k,S_k)$ a path is a polygonal line that is a possible outcome of simple random walk – user477465 Apr 1 at 23:46
• @Winther yes it is – user477465 Apr 1 at 23:47

Let us introduce some notations for the paths we are considering. We will say that $$\omega$$ is a path if $$\omega: \mathbb{N} \to \mathbb{Z}$$ satisfies $$\omega(i+1)-\omega(i)= \pm 1, \qquad \omega(0) = 0.$$ Then all the required definitions translate to this setting.

As a warmup, let us start with the bijection between $$P_{2n}$$ and $$N_{2n -1}$$. Since any $$\omega \in P_{n}$$ satisfies by definition $$\omega(i) \geq 1$$ for $$i \geq 1$$ we can define the map: $$\varphi : P_{2n} \to N_{2n-1}, \qquad \varphi(\omega)(i) = \omega(i+1)-1.$$ This is gust a left shift operation, where we eliminate the first line. The inverse is a right shift, where we simply push the whole pathe one line up.

Now, let us pass to the more involved exercise: The bijection $$R_{2n} \to N_{2n}$$.

For a given path $$\omega \in R_{2n}$$ we define $$\mathrm{nmin}(\omega) = \{ m_1, \ldots , m_{r(\omega)} \}$$

where $$m_1 \leq \ldots \leq m_{r(\omega)}$$ are all local minima such that $$\omega(m_j) <0$$ and $$\omega(m_j) < \omega(m_{k})$$ for $$j > k.$$ With local minimum we mean $$\omega(i-1) > \omega(i) < \omega(i+1)$$.

We now define $$\psi : R_{2n} \to N_{2n}$$ in the following way:

• $$\psi(\omega)(i) = |\omega(i)|$$ for $$0 \leq i \leq m_1$$.
• Now we attach the path between $$m_1$$ and $$m_2$$ and reflect it about $$\omega(m_1)$$. By this we mean: $$\psi(\omega)(i) = |\omega(m_1)| + |\omega(i) - \omega(m_1)|, \qquad \forall i \in [m_1, m_2].$$
• We iterate this procedure until we reach $$m_{r(\omega)}$$ and then iterate it one last time between $$m_{r(\omega)}$$ and $$2n.$$

Clearly we have produced a path in $$N_{2n}$$. We have to provide an algorithm to recover a path $$\omega$$ from a path $$\omega^{\prime}$$ in $$N_{2n}$$. We leave it as an exercise to see that this is indeed an inverse to $$\psi$$. The algorithm essentially follows the path backwards:

• Define $$m = \omega^\prime(2n)/2 \in \mathbb{N}$$. Eventually $$-m$$ will be the global minimum of our path.
• Define $$m_{r(\omega)}$$ the first time such that $$\omega(m_{r(\omega)})=m.$$
• Define the set of increasing positive minima: $$\mathrm{pmin}(\omega^\prime) = \{ m_0 < \bar{m}_1\leq \ldots \leq \bar{m}_{r(\omega) -1} \leq m_{r(\omega)}\}$$ where $$m_0$$ is the largest time such that $$\omega^\prime(m_0) = 0$$ and $$\bar{m}_i$$ is a local minimum for $$\omega^\prime$$ and $$\omega^\prime(j) > \omega^\prime(\bar{m}_i)$$ for $$\bar{m}_i < j$$. It may well be that this set is empty: This corresponds to the global minimum being the first negative local minimum in $$\omega$$.

• For any $$\bar{m}_i$$ define $$m_i = \max \{j \leq \bar{m}_i : \omega^\prime(j-1)< \omega^\prime (j) = \omega^\prime (\bar{m}_i)\}$$

• If $$m = 0$$ we set $$\omega = \omega^\prime$$. Otherwise let $$\omega(i) = \omega^{\prime}(i) -\omega^\prime(2n), \qquad \forall i \in [m_{r(\omega)}, 2n].$$

• Then we iterate the following procedure (first step is backwards reflection until we find the previous minimum value): $$\omega(i) = \omega(m_{r(\omega)})+(\omega^\prime(m_{r(\omega)}) -\omega^\prime(i)), \qquad \forall i \in [\bar{m}_{r(\omega)-1}, m_{r(\omega)}].$$ And (second step, we follow the given path, until we reach the next local minima: Between $$m_i$$ and $$\bar{m}_i$$ no reflection kick in): $$\omega(i) = \omega(\bar{m}_{r(\omega)-1})+(\omega^\prime(i)-\omega^\prime(\bar{m}_{r(\omega)-1}) ), \qquad \forall i \in [m_{r(\omega)-1}, \bar{m}_{r(\omega)-1}].$$
• Finally, $$\omega(i) = \omega^\prime(i)$$ on $$[0, m_0]$$ and $$\omega(i) = -\omega^\prime(i)$$ on $$[m_0, m_1]$$.

I think a picture does the job in th best way. I do not know how to produce one. Hopefully I did not forget some tricky detail in the description above :)