# Weighted Ring$(l)$ v/s Ring$(2l)$

Consider a ring of size $l$ and a ring of size $2l$, where $l$ is an odd number, with transition probability:
$$ P_{n \to n \pm 1} = \frac{1}{2} - \frac{1}{l}. $$

## Computing Wasserstein Distance:

Note that the first $l-1$ moments of the two rings are the same. The $l$-th moment of the ring$(2l)$ is $0$ because $l$ is an odd number and probability of returning to the starting node after $l$ steps is $0$. In the ring$(l)$ the random walk of length $l$ returns only if it takes $l$ steps forward. Therefore, the $l$-th moment of ring$(l)$ is
$$ \left( \frac{1}{2} -\frac{1}{l} \right)^{l} = \frac{1}{2^l} \left( 1 - \frac{2}{l}\right)^l. $$
To lower bound the Wasserstein distance, let our test function $L_l$ be the degree-$l$ Legendre polynomial normalized to have $1$-Lipschitzness (whose leading coefficient is ${2l \choose l} 2^{-l}/l^2$). Therefore, we get that the Wasserstein distance is
$$ W_1(\text{ring}(l), \text{ring}(2l)) = | \int_{-1}^{1} L_l(x) (\text{ring}(l) - \text{ring}(2l))~ \text{d}x | \geq \frac{1}{\sqrt{\pi}} \frac{0.036}{l^{2.5}}.$$

## Computing the Difference of Moments
Note that all the even moments are the same in ring$(l)$ and ring$(2l)$, and only the odd moments differ. Consider moments like $(2t+1) l + 2i$, where $t$ and $i$ are some integers, and $i < l$.

Since we are interested only in the difference between the moments, we look at all the possible ways in which the moments can differ from random walk perspective.

Since we are looking at the odd moment, it is $0$ in ring$(2l)$. The odd moments are non-zero in ring$(l)$ because it can complete the ring exactly $l, 3l, 5l ,\dots, (2t+1)l$ times. To compute this, we look at the ways $(2t+1) l + 2i$ can exactly sum up to $l, 3l, 5l ,\dots, (2t+1)l$.
The way $(2t+1) l + 2i$ sums up to $(2k+1)l$ is when it takes $(k+t)l+l+i$ steps forward and $(t-k)l+i$ steps backward. Therefore, we get the following expression for the difference in moments:

$$ \sum_{k=0}^{t} 2 {(2t+1)l + 2i \choose (k+t)l+l+i} \cdot \left( \frac{1}{2} - \frac{1}{l} \right)^{((2t+1)l + 2i)} .$$

We try to upper bound this expression. Note that the largest quantity in the expression is for $k=0$ and for therefore an upper bound for the above quantity would be

$$ 2(t+1) \cdot {(2t+1)l + 2i \choose tl+l+i} \cdot \left( \frac{1}{2} - \frac{1}{l} \right)^{((2t+1)l + 2i)} .$$

Approximating the above expression using Sterling's approximation, we get that

$$ \leq \frac{2(t+1)}{\sqrt{\pi (tl+i)}} \cdot \left( 1+ \frac{(tl+i)}{(tl+i)+l} \right)^{(tl+i)+l} \cdot \left( 2 + \frac{l}{(tl+i)} \right)^{(tl+i)} \cdot \left( \frac{1}{2} - \frac{1}{l} \right)^{((2t+1)l + 2i)} $$

#### Bounding the above expression, we get:

$$ \begin{align}
& \leq \frac{2(t+1)}{\sqrt{\pi (tl+i)}} \cdot \left( 1+ \frac{(tl+i)}{(tl+i)+l} \right)^{(tl+i)+l} \cdot \left( 2 + \frac{l}{(tl+i)} \right)^{(tl+i)} \cdot \left( \frac{1}{2} - \frac{1}{l} \right)^{((2t+1)l + 2i)} \\
(\star) & \leq \frac{2(t+1)}{\sqrt{\pi (tl+i)}} \cdot 2^{tl +i +l} \left( 1-\frac{1}{2(t+1+i/l)} \right)^{(t+1+i/l)l}~ \cdot 2^{tl+i} ~ \left( 1 + \frac{1}{2(t+i/l)}\right)^{(t+i/l)l} \\ & \qquad \qquad \cdot~2^{-2tl-l-2i} e^{-4t-2-4i/l}
\end{align}$$

We now bound $(\star)$:
Let $x = (t+i/l)$, then we can write $(\star)$ as:
$$ \begin{align}
(\star) & \leq \frac{2(t+1)}{\sqrt{\pi (tl+i)}} \cdot 2^{tl +i +l} \left( 1-\frac{1}{2(t+1+i/l)} \right)^{(t+1+i/l)l}~ \cdot 2^{tl+i} ~ \left( 1 + \frac{1}{2(t+i/l)}\right)^{(t+i/l)l} \\ & \qquad \qquad \cdot~2^{-2tl-l-2i} e^{-4t-2-4i/l} \\
& = \frac{2(t+1)}{\sqrt{\pi (tl+i)}} \cdot \left( 1-\frac{1}{2(x+1)} \right)^{(x+1)l} \cdot \left( 1+\frac{1}{2x} \right)^{xl} \cdot e^{-4t-2-4i/l} \\
& = \frac{2(t+1)}{\sqrt{\pi (tl+i)}} \cdot \left( {\left( 1-\frac{1}{2(x+1)} \right) \left(1+\frac{1}{2x}\right)} \right)^{xl} \left( 1-\frac{1}{2(x+1)} \right)^{l} \cdot e^{-4t-2-4i/l} \\
& = \frac{2(t+1)}{\sqrt{\pi (tl+i)}} \cdot \left( 1 + \frac{1}{4x(x+1)}\right)^{xl} \left( 1-\frac{1}{2x} \right)^{l} \cdot e^{-4t-2-4i/l} \\
& \leq \frac{2(t+1)}{\sqrt{\pi (tl+i)}} \cdot e^{\frac{l}{4(x+1)}} ~ e^{\frac{-l}{2(x+1)}} \cdot e^{-4t-2-4i/l} \\
& = \frac{2(t+1)}{\sqrt{\pi (tl+i)}} \cdot ~ e^{\frac{-l}{4(x+1)}} \cdot e^{-4(x+1)} ~ e^{2} \\
& = \frac{2e^2(t+1)}{\sqrt{\pi (tl+i)}} \cdot ~ e^{\frac{-l}{4(x+1)}} \cdot e^{-4(x+1)} \\
& = \frac{2e^2(t+1)}{\sqrt{\pi (tl+i)}} \cdot ~ e^{\frac{-l}{4(t+1+i/l)}} \cdot e^{-4(t+1+i/l)}
\end{align}$$

Therefore, we get that difference of $(2tl+l+2i)$-th moment is at most (which is achieved for $(t+1+i/l) = \sqrt{l}/4$):
$$ \begin{align}
m_{(2tl+l+2i)}(\text{ring}(l), \text{ring}(2l)) & \leq \frac{2e^2(t+1)}{\sqrt{\pi (tl+i)}} \cdot ~ e^{-2\sqrt{l}}, \\
& \leq 9\left(\sqrt{\frac{t}{l}} +1\right) \cdot ~ e^{-2\sqrt{l}},
\end{align}$$
and the Wasserstein distance is
$$ W_1(\text{ring}(l), \text{ring}(2l)) \geq \frac{0.036}{\sqrt{\pi}} \cdot \frac{1}{l^{2.5}}.$$