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.
 A: 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 :)
