SHORT VERSION: Find appropriate Coupling
Suppose we have a random walk on the natural numbers, where we go to the left with probability $p_L \geq \frac{1}{6}$, to the right with probability $p_R\leq \frac{2}{3}$ and stay with probability $p_S\in [\frac{1}{6}, \frac{1}{2}]$.
How can we find probabilities of going to the left $p_L'$ and to the right $p_R'$ (probability of staying set to 0) such that $p_L'$ is large but is worse than $p_L$ in the sense of going to the left is easier in the first (with $p$) than in the second case (with $p'$).
In our solution it is written $p_L' = \frac{1}{5}$ and $p_R'=\frac{4}{5}$, but I have no idea why this is true.
LONG VERSION
Suppose we have a fixed string $s^*\in \{1,2,3\}^3 \setminus \{111,222,333\}$.
Now let $s\in \{111,222,333\}$ be a string. We pick one of the three indices uniformly at random and change the value to one of the other two uniformly at random, resulting in $s'$.
We are interested in the number of bits in which $s$ and $s^*$ and $s'$ and $s^*$ differ (in the following called their distance), or stated differently, in how the difference of these two distances evolves.
We know that $s$ and $s^*$ must differ in at least one position (as $s$ has all the same numbers and $s^*$ does not). The probability of $s'$ having one position more coinciding with $s^*$ than $s$ thus is bounded by $\geq \frac{1}{3}\frac{1}{2}=\frac{1}{6}$ (picking the correct index and switching to the correct number).
We know that $s$ and $s^*$ can have at most $2$ coinciding positions. The probability that $s'$ has larger distance to $s^*$ than $s'$ thus is upper bounded by $\leq \frac{2}{3}$.
The probability that $s$ and $s'$ have the same distance to $s^*$ is not that easy to get. If $s$ and $s^*$ differ at one position, it is $\frac{1}{3}\frac{1}{2}=\frac{1}{6}$, if they differ at 2 positions,it is $\frac{2}{3}\frac{1}{2}=\frac{1}{3}$ and if they differ at all positions it is $\frac{3}{3}\frac{1}{2}=\frac{1}{2}$, namely the probability of picking one position in which they differ and switching to the "wrong" color such that $s'$ and $s^*$ differ also in this position.
In total, we decrease the distance with probability $\geq \frac{1}{6}$, we increase it with probability $\leq \frac{2}{3}$ and we stay with probability $\geq \frac{1}{6}$ or $\leq \frac{1}{2}$.
Now the goal is to combine these bounds into easier probabilities (of decreasing and increasing the distance (not staying)) such that our true probability of decreasing the distance is at least the resulting probability in our estimate (something like a Coupling).
The claim is that $\frac{1}{5}$ of decreasing and $\frac{4}{5}$ of increasing works. But why is this worse (in the sense of having smaller probability of decreasing) than the actual example we are considering?
Thank you very much for your help. If you need it more formal, please write a comment and I will adapt it.
Remark (Background): This example comes from a randomized algorithm for finding a 3-coloring of a graph without monochromatic triangles, and we want to approximate the distance of the current coloring to one such 3-coloring without monochromatic triangles by a random walk on the natural numbers, where the current position indicates the number of colors in which the two colorings (the current and the fixed one) differ.