# Weighted Lower Bound Formal
Construction:

$G_1$: n rings with length l

$G_2$: n rings with length 2l.

The Adjacency Matrices:

$$G_1 = \frac{1}{4} R_1 + \frac{1}{2nl} 11^\top, \quad G_2 = \frac{1}{4}R_2 + \frac{1}{4nl} 11^\top, $$
where $R_1$ denotes unnormalized adjacency matrix of $n$-disjoint rings of lenght $l$ and $R_2$ denotes unnormalized adjacency matrix of $n$-disjoint rings of lenght $2l$.

fix a label, denote n rings by $r_1$, $r_2$, ... $r_n$, and denote each node in it (in clock-wise direction) as $1,2,3,\cdots, l$. So given pair $(r_i, i)$ uniquely refer to some node in $G_1$.

In $G_2$ we similarly consider labeling the rings, but now we label the nodes by $1,\cdots, l, -1,\cdots, -l$.

Now I will define $\phi$, which is mapping for any $T$-length path in $G_2$ to same-length path in $G_1$. Given any $T>0$. $w\in\{0,1\}$ denote whether we take a heavy edge ($w=1$) or light edge ($w=0$).

Consider any path $\{(r_{i_t}, j_t), w_t\}_{t\in[T]}$ in $G_2$ with length $T$, we let
\begin{align*}
\phi(\{(r_{i_t}, j_t), w_t\}_{t\in[T]}) = \{(r_{i_t}, |j_t|), w_t\}_{t\in[T]}.
\end{align*}

We observe the following two (relatively straightforward) facts about this mapping:
1) whenever $\{(r_{i_t}, j_t), w_t\}_{t\in[T]}$ gives a valid random-walk path in $G_2$, its image $\{(r_{i_t}, |j_t|), w_t\}_{t\in[T]}$ must be a valid random walk in $G_1$.
2) $\phi$ may map multiple different paths in $G_2$ to some same path in $G_1$.

We use $\phi^{-1}(\{(r_{i_t}, |j_t|), w_t\}_{t\in[T]})$ to denote all valid random walks with length $T$ in $G_2$ that map to the only random walk of form $\{(r_{i_t}, |j_t|), w_t\}_{t\in[T]}$ in $G_1$.

Now we prove the following lemma: given our random walk oracle,
$$P_{G_2}(\phi^{-1}(\{(r_{i_t}, |j_t|), w_t\}_{t\in[T]})) = P_{G_1}(\{(r_{i_t}, |j_t|), w_t\}_{t\in[T]}).$$

First I will show: assuming this probability equation is true, then we are done. We consider the lazy labeling scheme.
~~We use event $E$ to denote the good event which consist of any length-$T$ path that didn't go through any full ring in $G_1$ and didn't come back to a same ring whenever it leaves that ring, or correspondingly on $G_2$ that its image after applying $\phi$ in G_1 satisfy these properties.

Claim: we have $P_{G_1}(\text{same transcrip after lazy labeling}|E) = P_{G_2}(\text{same transcrip after lazy labeling}|E)$.

Proof of Claim. Given any $T$-length path in $G_1$ $p_1 = \{(r_{i_t}, j_t), w_t\}_{t\in[T], j_t>0}$ and for any $p_2\in\phi^{-1}(p_1)$. Because $p_1$ never visits the same ring,we must have the lazy labeling for $p_1$ is exactly the same as the lazy labeling of $p_2$ as long as they don't go through the entire ring and don't visit the same ring once again. This means $P_{G_1}(p_1) = P_{G_2}(\phi^{-1}(p_1))$, and consequently
\begin{align*}
P_{G_1}(\text{transcrip A after lazy labeling}|E) & = \sum_{p_1~\text{gives}~\text{transcrip}~A}P_{G_1}(p_1|E)\\
& = \sum_{p_1~\text{gives}~\text{transcrip}~A}P_{G_2}(\phi^{-1}(p_1)|E)\\
& = P_{G_2}(\text{transcrip A after lazy labeling}|E).
\end{align*}
Essentially we sum up all the $p_1$ corresponding to a certain pattern of the lazy labeling to prove this claim.

___________end of proof of Claim___________

Proof of Lemma. It suffices to show the conditioning probability at each step is the same.

For the initial point, the probability of we choosing in $G_1$ and $G_2$ are both $1/(nl)$. Then for the next step, we consider two cases, when $w_1$ is a heavy edge or $w_1$ is a light edge. If $w_1$ is a heavy edge then $j_2$ ($|j_2|$) must be a neighbor of $j_1$ ($|j_1|$), consequently the conditional probabilities of getting there for both $G_1$ and $G_2$ are $1/4$. Similarly, if $w_1$ is a light edge, then $|j_1|$ arrives at $|j_2|$ with probability $1/2nl$ in $G_1$, while in $G_2$ any vertex corresponding to $|j_1|$ (may be either $j_1$ or $-j_1$) arrives at $j_2$ or $-j_2$ with probability $1/4nl+1/4nl = 1/2nl$. Making the same argument recursively for all $T$ transitions from the first node to the last node, we prove the probability must be the same.

___________end of proof of Lemma___________