13
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Please define these "random walk paths" that you are using; I don't think this is common terminology. $\endgroup$ – darij grinberg Apr 1 at 23:42
  • $\begingroup$ 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 $\endgroup$ – user477465 Apr 1 at 23:46
  • $\begingroup$ @Winther yes it is $\endgroup$ – user477465 Apr 1 at 23:47
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.