Dgdrxrt

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.

Let us introduce some notations for the paths we are considering. We will say that $omega$ is a path if $$omega: mathbbN to mathbbZ$$ 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
$$mathrmnmin(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 mathbbN$. 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: $$mathrmpmin(omega^prime) = m_0 < barm_1leq ldots leq barm_r(omega) -1 leq m_r(omega)$$
  where $m_0$ is the largest time such that $omega^prime(m_0) = 0$ and $barm_i$ is a local minimum for $omega^prime$ and $omega^prime(j) > omega^prime(barm_i)$ for $ barm_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 $barm_i$ define $$m_i = max j leq barm_i : omega^prime(j-1)< omega^prime (j) = omega^prime (barm_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 [barm_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 $barm_i$ no reflection kick in):
  $$ omega(i) = omega(barm_r(omega)-1)+(omega^prime(i)-omega^prime(barm_r(omega)-1) ), qquad forall i in [m_r(omega)-1, barm_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 :)