Random walk on the lamplighter group

Question

Consider a random walk on the lamplighter group with the following generating set: move left, move right, and toggle lamp. Start at the origin, with all lamps off. What is the probability that, after $t$ steps, the lamp at the origin is on?

I started by letting $g(b,k,t)$ denote the number of words of length $t$ that set the lamp at the origin to $b$ and the lamplighter at position $k$. Thus we have the recurrence relation \begin{align*} g(b,k,0)&=[b=0][k=0] \\ g(b,k,t+1)&=g(b,k-1,t)+g(b,k+1,t)+g(b \oplus [k=0],k,t) \end{align*}

where $[\cdot]$ is the Iverson bracket and $\oplus$ is xor. Then I let $f(b,t)$ denote the number of words of length $t$ that set the lamp at the origin to $b$: $$f(b,t) = \sum_{k \in \mathbb{Z}} g(b,k,t)$$

The answer to my question is $f(1,t) \cdot 3^{-t}$, since $3^t$ is the total number of words of length $t$. After some simplification, I obtained the following recurrence relation for $f$: \begin{align*} f(b,0) &= [b=0] \\ f(b,t+1) &= 3 f(b,t) - g(b, 0, t) + g(b \oplus 1, 0, t) \end{align*}

I'm trying to get rid of the remaining $g$ terms. $g(0,0,t)$ and $g(1,0,t)$ represent the number of $t$-length words that return to the origin while leaving its lamp off or on, respectively. I suspect I might be able to use Motzkin paths to solve for these. The number of $t$-length words that return to the origin is the $t$th central trinomial coefficient. That is,

$$g(0,0,t)+g(1,0,t) = \sum_{i=0}^t \binom{t}{i} \binom{i}{t-i}$$

The first few coefficients are

\begin{array}{c|c|c} & b = 0 & b = 1 \\ t=0 & 1 & 0 \\ t=1 & 0 & 1 \\ t=2 & 3 & 0 \\ t=3 & 2 & 5 \\ t=4 & 15 & 4 \\ t=5 & 22 & 29 \\ t=6 & 93 & 48 \\ t=7 & 196 & 197 \\ t=8 & 659 & 448 \\ t=9 & 1650 & 1489 \end{array}

EDIT: Let $L_k$ denote the set of words that shift the lamplighter by $k$. Then $$[z^n]L_k(z) = \binom{n}{k}_2$$

where the RHS is the entry in row $n$ and column $k$ of the trinomial triangle. Let $L_k^-$ be the subset of $L_k$ such that the lamp at $k$ (or, equivalently in number, the lamp at the last position) is not toggled. Based on further investigation, it seems to be the case that $$L_k^-(z) = L_k(z) \frac{1+z L_0(z)}{1+2z L_0(z)}$$

Is there a simple explanation for this relationship? I sense some kind of recursive definition of $L_k^-$ in terms of $L_k$, $L_0$, and $L_k^-$ itself.

Answer 1

To derive a probability generating function, let $x$ track the total number of steps and let $y$ track the number of times the lamp at the origin has been toggled. First, we repeatedly do one of two things at the origin – with probability $\frac13$, toggle the lamp, and otherwise, go for a walk until we return. The probability generating function for one such action is

\begin{eqnarray*} && \frac13xy+\frac13x^2\sum_{n=0}^\infty C_n\left(\frac x2\right)^{2n}\left(\frac23\left(1+\frac x3+\left(\frac x3\right)^2+\cdots\right)\right)^{2n+1} \\ &=& \frac13xy+\frac13x^2\sum_{n=0}^\infty C_n\left(\frac x2\right)^{2n}\left(\frac{\frac23}{1-\frac x3}\right)^{2n+1} \\ &=& \frac13xy+\frac23\frac{x^2}{3-x}\sum_{n=0}^\infty C_n\left(\frac x2\right)^{2n}\left(\frac2{3-x}\right)^{2n} \\ &=& \frac13xy+\frac23\frac{x^2}{3-x}\sum_{n=0}^\infty C_n\left(\frac x{3-x}\right)^{2n} \\ &=& \frac13xy+\frac23\frac{x^2}{3-x}C\left(\left(\frac x{3-x}\right)^2\right) \\ &=& \frac13xy+\frac23\frac{x^2}{3-x}\frac{1-\sqrt{1-4\left(\frac x{3-x}\right)^2}}{2\left(\frac x{3-x}\right)^2} \\ &=& \frac13\left(xy + 3-x-\sqrt{(3-x)^2-4x^2}\right)\;, \end{eqnarray*}

where the $C_n$ are the Catalan numbers and

$$ C(x)=\sum_{n=0}^\infty C_nx^n=\frac{1-\sqrt{1-4x}}{2x} $$

is their generating function. We can take any number of these actions, so we need to form the geometric series, yielding

$$ \frac1{1-\frac13\left(xy + 3-x-\sqrt{(3-x)^2-4x^2}\right)}\\=\frac3{-xy+x+\sqrt{(3-x)^2-4x^2}}\;. $$

After taking any number of these actions at the origin, we can optionally go for a walk without returning to the origin, optionally toggling non-origin lamps along the way. Ignoring for now the toggling of lamps, we can find the probability generating function $g(z)$ for simple symmetric random walks that never return to the origin by writing the probability generating function $(1-z)^{-1}$ for all walks as the product of g(z) with a geometric series for walks that return to the origin:

\begin{eqnarray*} \frac1{1-z} &=& g(z)\cdot\frac1{1-\frac{z^2}2\sum_{n=0}^\infty C_n\left(\frac z2\right)^{2n}} \\ &=& g(z)\cdot\frac1{1-\frac{z^2}2C\left(\frac{z^2}4\right)} \\ &=& \frac{g(z)}{\sqrt{1-z^2}}\;, \end{eqnarray*}

so

$$ g(z)=\sqrt{\frac{1+z}{1-z}}\;. $$

To account for the fact that after each step in this random walk we can toggle the non-origin lamp we're at any number of times, we need to substitute $x\cdot\frac23\left(1+\frac x3+\left(\frac x3\right)^2+\cdots\right)=\frac{2x}{3-x}$ for $z$:

\begin{eqnarray*} g(x)&=&\sqrt{\frac{1+\frac{2x}{3-x}}{1-\frac{2x}{3-x}}} \\ &=& \sqrt{\frac{1+\frac x3}{1-x}}\;. \end{eqnarray*}

Thus, the complete probability generating function with $y$ counting the number of times the lamp at the origin is toggled and $x$ counting the number of steps is

$$ \frac{3\sqrt{\frac{1+\frac x3}{1-x}}}{-xy+x+\sqrt{(3-x)^2-4x^2}}\\ = \frac{\sqrt{3(3+x)/(1-x)}}{-xy+x+\sqrt{3(3+x)(1-x)}}\;. $$

But we don't actually want to know the number of times the lamp at the origin is toggled, only whether it's on or off, so we evaluate at $y=1$ and $y=-1$ and take half the difference to extract the sum of the terms with odd powers of $y$ that correspond to the lamp being on:

$$ \frac12\left(\frac{\sqrt{3(3+x)/(1-x)}}{\sqrt{3(3+x)(1-x)}}-\frac{\sqrt{3(3+x)/(1-x)}}{2x+\sqrt{3(3+x)(1-x)}}\right)\\ = \frac12\left(\frac1{1-x}-\frac1{1-x+\frac{2x}{\sqrt{3(3+x)/(1-x)}}}\right)\;. $$

This is the probability generating function for the probability of the lamp at the origin being on; the coefficient of $x^n$ is the probability for the lamp to be on after $n$ steps. Letting Wolfram|Alpha compute the series expansion yields

$$ \frac x3+2\cdot\left(\frac x3\right)^2+9\cdot\left(\frac x3\right)^3+24\cdot\left(\frac x3\right)^4+83\cdot\left(\frac x3\right)^5+242\cdot\left(\frac x3\right)^6+\cdots\;, $$

and the first four terms are readily verified by a hand count.

The first term, $\frac12\frac1{1-x}$, represents the long-term average probability $\frac12$, and the second term represents the deviation from that equilibrium. The singularity at $x=1$ is of the form $\frac{\sqrt3}2\frac1{\sqrt{1-x}}$, and the coefficients in the series for $\frac1{\sqrt{1-x}}$ are asymptotic to $\frac1{\sqrt{\pi n}}$, suggesting that the deviation of the probability from $\frac12$ is asymptotic to $\sqrt{\frac3{4\pi n}}$. This is confirmed by direct computation of the probabilities (using this Java code). The following diagram shows a log-log plot of the deviations of the probabilities from $\frac12$ as a function of $n$; the line shows the above asymptotic behaviour.

P.S.: We can expand in powers of $\sqrt{1-x}$ to generate an asymptotic series for the deviation of the probability from $\frac12$. The next singular term is $\sqrt{27/4}\sqrt{1-x}$, with coefficients asymptotic to $\sqrt{27/(4\pi n^3)}$, so the asymptotic series begins with

$$ \sqrt{\frac3{4\pi n}}-\sqrt{\frac{27}{4\pi n^3}}+O\left(n^{-5/2}\right)\;. $$

Here's the log-log plot again, with the green line showing these first two terms:

Edit in response to the edit in the question:

You can derive this equation for $L_k^-(z)$ by reducing everything to the number $S_k$ of walks that shift by $k$ and never touch the lamp at $k$. To get to $k$, you first have to get there without touching the lamp at $k$, and then you can append any number of repetitions of toggling the lamp at $k$, going for a walk and returning. Thus (suppressing the argument $z$ to reduce the clutter)

$$ L_k=S_k\left(1+zS_0+(zS_0)^2+\cdots\right)=\frac{S_k}{1-zS_0}\;. $$

$L_k^-$ is the even part of this series, in which the lamp is toggled an even number of times:

$$ L_k^-=S_k\left(1+(zS_0)^2+(zS_0)^4+\cdots\right)=\frac{S_k}{1-z^2S_0^2}\;. $$

So

$$ L_k=(1+zS_0)L_k^-\;, $$

that is, every walk to $k$ is either a walk to $k$ with the lamp at $k$ ending up off or such a walk plus a toggle at $k$ plus a return walk without toggle at $k$.

Thus your equation is equivalent to

$$ \frac{1+zL_0}{1+2zL_0}=\frac1{1+zS_0}\;, $$

which you can verify by substituting $L_0$ in terms of $S_0$ from above.

Answer 2

Motkzin paths indeed seem promising.

Consider that a word which ends at the origin must be of the form $(M0^*)^*$ where $M$ denotes a Motzkin path and $0$ denotes the lamp toggle. Alternatively, and perhaps more usefully, it must be of the form $0^*(M'0^*)^*$ where $M'$ denotes a non-empty Motkzin path.

The Motkzin numbers have g.f. $$A(x) = \frac{1 - x - \sqrt{1-2x-3x^2}}{2x^2}$$ but the offset is not quite what we want and we need to double to account for the first move being to the right or to the left, so for non-empty Motzkin paths we get g.f. $$A'(x) = 2x^2A(x) = 1 - x - \sqrt{1-2x-3x^2}$$

If we have $p$ non-empty Motkzin paths, that corresponds to $A'(x)^p$. Then we have $p+1$ gaps into which to insert the toggles at the origin, and we want an alternating sum because we're building towards $g(0, 0, t) - g(1, 0, t)$, so we want to convolve with a multinomial sequence $$\sum_{i=0}^\infty (-1)^i \binom{p+i}{p} x^i$$ Finally we sum over $p$ to get $$\begin{eqnarray}g(0, 0, t) - g(1, 0, t) &=& [x^t] \sum_p \sum_{i=0}^\infty (-1)^i \binom{p+i}{p} x^i A'(x)^p \\ &=& [x^t] \sum_{i=0}^\infty (-x)^i \sum_p \binom{p+i}{p} A'(x)^p \\ &=& [x^t] \sum_{i=0}^\infty \frac{(-x)^i}{(1 - A'(x))^{i+1}} \\ &=& [x^t] \frac{1}{1 - A'(x)} \sum_{i=0}^\infty \left(\frac{-x}{1 - A'(x)}\right)^i \\ &=& [x^t] \frac{1}{1 - A'(x)} \frac{1}{1 - \left(\frac{-x}{1 - A'(x)}\right)} \\ &=& [x^t] \frac{1}{1 + x - A'(x)} \\ &=& [x^t] \frac{1}{2x + \sqrt{1-2x-3x^2}} \\ \end{eqnarray}$$

---

Now to get a recurrence we set $G(x) = \frac{1}{2x + \sqrt{1-2x-3x^2}}$ or $$G(x)\left( 2x + \sqrt{1-2x-3x^2} \right) = 1$$

I'm not entirely sure what the best way is to tackle that square root, but factoring as $1 - 2x - 3x^2 = (1 - 3x)(1 + x)$ seems like a plausible option.

Then $$G(x)\left( 2x + \sum_{i=0}^\infty \binom{1/2}{i}(-3x)^i \sum_{j=0}^\infty \binom{1/2}{j}x^j \right) = 1$$ A change of variables probably helps: let $n = i + j$ and $$G(x)\left( 2x + \sum_{n=0}^\infty \sum_{i=0}^n \binom{1/2}{i}\binom{1/2}{n-i} (-3)^i x^n \right) = 1$$

Extracting a couple of small values of $n$ from the sum we get $$\sum_{n=0}^\infty \sum_{i=0}^n \ldots = 1 - x + \sum_{n=2}^\infty \sum_{i=0}^n \binom{1/2}{i}\binom{1/2}{n-i} (-3)^i x^n$$ which substituting back in gives

$$G(x)\left( 1 + x + \sum_{n=2}^\infty \sum_{i=0}^n \binom{1/2}{i}\binom{1/2}{n-i} (-3)^i x^n \right) = 1$$

So comparing coefficients of $x^0$ we have $g_0 = 1$, and comparing coefficients of $x^1$ we have $g_0 + g_1 = 0$, or $g_1 = -1$.

Comparing coefficients of $x^t$ we have $$[x^t]G(x)\left( 2x + \sum_{n=0}^\infty \sum_{i=0}^n \binom{1/2}{i}\binom{1/2}{n-i} (-3)^i x^n \right) = [t = 0]$$ giving recurrence $$\sum_{n=0}^t g_{t-n} \left( 2[n = 1] + \sum_{i=0}^n \binom{1/2}{i}\binom{1/2}{n-i} (-3)^i \right) = [t = 0]$$

However, this is no more efficient to calculate than your original recurrence for $g(b,k,t)$, so the main interest is in using the generating function to analyse asymptotic behaviour.

---

Postscript: we can use $G$ to derive the generating function $F$ for $f(0, t)$ as follows: $$\begin{eqnarray*} f(0,0) &=& 1 \\ f(0,t+1) &=& 3 f(0,t) - [x^t]G(x) \end{eqnarray*}$$ So $g_t x^t$ in $G$ becomes $-g_t x^{t+1} -3g_t x^{t+2} - 3^2 g_t x^{t+3} - \ldots = g_t x^t \frac{-x}{1-3x}$ and $$F(x) = \frac{1 - xG(x)}{1-3x}$$