How can I prove this bijection between random walks?

Solution 1:

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