Efficiently sampling over closed walks on a triangle; A078008

Question

OEIS A078008, the coefficients of the generating function $\frac{1-x}{(1+x)(1-2x)}$, gives the number of walks of length $n$ on a triangle that return to the original vertex.

For fixed $n$, is there an efficient algorithm for sampling uniformly over the distribution of all walks of length $n$?

Answer 1

Say that the vertices of the triangle are $A$, $B$, and $C$.

We will sample a uniformly random $A$-to-$A$ walk of length $n$ if we choose every step with probability proportional to the number of walks that end at $A$ after $n$ steps, and which take that step. So, for example, if we're at vertex $B$ and we want to end up at $A$ after $3$ more steps, then we should go to $A$ with probability $\frac23$ and to $C$ with probability $\frac13$. That's because we want to choose uniformly from the walks $BABA$, $BACA$, and $BCBA$; $2$ of those walks go to $A$ next, and $1$ goes to $C$ next.

To implement this, we need to know the number of walks of each type. In closed form, the $n^{\text{th}}$ term of A078008 is $\frac{2^n + 2(-1)^n}{3}$. That's the number of walks of length $n$ starting at $A$ and ending at $A$. Accordingly, out of the $2^n$ total walks of length $n$, there are $\frac{2^n - (-1)^n}{3}$ that start at $A$ and end at $B$, and the same time for any other pair of distinct vertices.

So, the rule we end up following is this:

1. Suppose there are $n$ steps left and we are at vertex $A$. By symmetry, we go to $B$ or $C$ with equal probability.
2. Suppose there are $n$ steps left and we are at vertex $B$. If we go to $A$, there are $\frac{2^{n-1} + 2(-1)^{n-1}}{3}$ ways to finish the walk. If we go to $C$, there are $\frac{2^{n-1} - (-1)^{n-1}}{3}$ ways to finish the walk. So we should go to $A$ with probability $$\frac{\frac{2^{n-1} + 2(-1)^{n-1}}{3}}{\frac{2^{n-1} + 2(-1)^{n-1}}{3} + \frac{2^{n-1} - (-1)^{n-1}}{3}} = \frac{2^{n-1} - 2(-1)^n}{2^n - (-1)^n}$$ and to $C$ otherwise.
3. The rule from vertex $C$ is the same as from vertex $B$ by symmetry, except of course that if we decide not to go to $A$, the alternative is to go to $B$.

Here's a sample of this algorithm: say we want to sample a random length-$6$ walk.

1. We start at $A$ and flip a fair coin; say we go to $C$.
2. From $C$, we use the formula above with $n=5$, so we have a $\frac{2^4 + 2}{2^5 + 1} = \frac{6}{11}$ chance to go to $A$ and a $\frac{5}{11}$ chance to go to $B$. Say we go to $B$.
3. From $B$, we use the formula above with $n=4$, so we have a $\frac{2^3 - 2}{2^4 - 1} = \frac25$ chance to go to $A$ and a $\frac35$ chance to go to $C$. Say we go to $A$.
4. From $A$, we are equally likely to go to $B$ or $C$; say we go to $C$.
5. From $C$, we use the formula above with $n=2$, so we have a $\frac{2^1-2}{2^2-1} = 0$ chance to go to $A$. We are guaranteed to go to $B$.
6. From $B$, we use the formula above with $n=1$, so we have a $\frac{2^0+2}{2^1+1} = 1$ chance to go to $A$. We are guaranteed to end at $A$, which makes sense because that's the kind of walk we're sampling from!