Paseo aleatorio en el grupo de farolero

Question

Considere la posibilidad de un paseo aleatorio en el lamplighter grupo con la siguiente generación del sistema: mover a la izquierda, mover a la derecha, y cambiar la lámpara. Inicio en el origen, con todas las lámparas apagadas. ¿Cuál es la probabilidad de que, después de $t$ pasos, la lámpara en el origen es?

Empecé por dejar a $g(b,k,t)$ denotar el número de palabras de longitud $t$ que establece la lámpara en el origen a $b$ y el farolero en la posición $k$. Así pues, tenemos la relación de recurrencia \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*}

donde $[\cdot]$ es la Iverson soporte y $\oplus$ es xor. Entonces dejo $f(b,t)$ denotar el número de palabras de longitud $t$ que establece la lámpara en el origen a $b$: $$f(b,t) = \sum_{k \in \mathbb{Z}} g(b,k,t)$$

La respuesta a mi pregunta es $f(1,t) \cdot 3^{-t}$, ya que el $3^t$ es el número total de palabras de longitud $t$. Después de cierta simplificación, he obtenido la siguiente relación de recurrencia para $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*}

Estoy tratando de deshacerse de los restantes $g$ términos. $g(0,0,t)$ $g(1,0,t)$ representan el número de $t$-longitud palabras que volver al origen, dejando su lámpara o desactivar, respectivamente. Tengo la sospecha de que podría ser capaz de utilizar Motzkin caminos para resolver estos. El número de $t$-longitud palabras que volver al origen es el $t$th central trinomio coeficiente. Es decir,

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

Los primeros son los coeficientes de

\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: Vamos a $L_k$ denota el conjunto de palabras que cambian el lamplighter por $k$. Entonces $$[z^n]L_k(z) = \binom{n}{k}_2$$

donde el lado derecho es la entrada en la fila $n$ y la columna $k$ de la trinomio triángulo. Deje $L_k^-$ ser el subconjunto de $L_k$ de manera tal que la lámpara a $k$ (o, de manera equivalente en número, la lámpara en la última posición) no es conmutado. Basado en la investigación posterior, parece ser el caso de que $$L_k^-(z) = L_k(z) \frac{1+z L_0(z)}{1+2z L_0(z)}$$

Hay una explicación simple para esta relación? Tengo la sensación de algún tipo de definición recursiva de $L_k^-$ en términos de $L_k$, $L_0$, y $L_k^-$ sí.

Answer 1

Para obtener una probabilidad de generación de función, vamos a $x$ rastrear el número total de pasos y deje $y$ el seguimiento del número de veces que la lámpara en el origen ha sido conmutada. En primer lugar, que en repetidas ocasiones que hacer una de dos cosas en el origen – con una probabilidad de $\frac13$, interruptor de la lámpara, y de lo contrario, ir a dar un paseo hasta la vuelta. La probabilidad de generación de función para una acción que es

\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*}

donde el $C_n$ son los números de catalán y

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

es su generación de función. Podemos tomar cualquier número de estas acciones, por lo que necesitamos para formar la serie geométrica, dando

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

Después de tomar cualquier número de estas acciones en el origen, opcionalmente podemos ir a dar un paseo sin tener que regresar al origen, opcionalmente, la alternancia no-origen de las lámparas a lo largo del camino. Ignorando por ahora que la conmutación de lámparas, podemos encontrar la probabilidad de generación de función $g(z)$ simple simétrica paseo aleatorio que nunca volver a los orígenes por escrito la probabilidad de generación de función $(1-z)^{-1}$ para todos los sectores como el producto de g(z) con una serie geométrica para los paseos que volver al origen:

\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*}

así

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

Para explicar el hecho de que después de cada paso en este camino aleatorio podemos alternar el no-origen de la lámpara estamos en cualquier número de veces, necesitamos sustituto $x\cdot\frac23\left(1+\frac x3+\left(\frac x3\right)^2+\cdots\right)=\frac{2x}{3-x}$$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*}

Por lo tanto, la probabilidad de generación de función con $y$ contando el número de veces que la lámpara en el origen se activa y $x$ contando el número de pasos es

$$ \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)}}\;. $$

Pero que en realidad no quieres saber el número de veces que la lámpara en el origen se activa, sólo si está encendido o apagado, por lo que evaluamos en $y=1$ $y=-1$ y tome la mitad de la diferencia para extraer la suma de los términos con potencias impares de $y$ que corresponden a la lámpara está en:

$$ \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)\;. $$

Esta es la probabilidad de generación de función de la probabilidad de la lámpara en el origen está en; el coeficiente de $x^n$ es la probabilidad de que la lámpara después de $n$ pasos. Dejar de Wolfram|Alpha calcular la expansión de la serie de los rendimientos

$$ \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\;, $$

y los cuatro primeros términos son fácilmente verificado por un lado contar.

El primer término, $\frac12\frac1{1-x}$, representa el promedio de largo plazo de probabilidad $\frac12$, y el segundo término representa la desviación de equilibrio. La singularidad en $x=1$ es de la forma $\frac{\sqrt3}2\frac1{\sqrt{1-x}}$, y los coeficientes de la serie de $\frac1{\sqrt{1-x}}$ son asintóticas a $\frac1{\sqrt{\pi n}}$, lo que sugiere que la desviación de la probabilidad de $\frac12$ es asintótica a $\sqrt{\frac3{4\pi n}}$. Esto es confirmado por la directa cálculo de las probabilidades (el uso de este código de Java). El siguiente diagrama muestra un log-log de la trama de las desviaciones de las probabilidades de $\frac12$ como una función de la $n$; la línea muestra el anterior comportamiento asintótico.

P. S.: podemos ampliar en potencias de $\sqrt{1-x}$ a generar una serie asintótica para la desviación de la probabilidad de $\frac12$. El siguiente término en singular es $\sqrt{27/4}\sqrt{1-x}$, con coeficientes de asintótica $\sqrt{27/(4\pi n^3)}$, por lo que la forma asintótica de la serie comienza con

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

Aquí está el log-log de la parcela, de nuevo, con la línea verde muestra estos dos primeros términos:

Edición en respuesta a la edición en la pregunta:

Puede derivar esta ecuación para $L_k^-(z)$ por la reducción de todo a la número $S_k$ de los paseos que cambio por $k$ y nunca toque la lámpara en $k$. Para llegar a $k$, primero tiene que llegar sin tocar la lámpara en $k$, y entonces usted puede agregar cualquier número de repeticiones de cambio de la lámpara en $k$, pasando de un pie y volver. Por lo tanto (suprimir el argumento de $z$ a reducir el desorden)

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

$L_k^-$ es la parte de esta serie, en la que la lámpara se activa un número par de veces:

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

Así

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

es decir, cada pie a $k$ es un paseo a $k$ con la lámpara en la $k$ terminan en off o un pie, además de una alternancia en$k$, además de una vuelta a pie sin necesidad de alternar en $k$.

Por lo tanto su ecuación es equivalente a

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

que se puede comprobar mediante la sustitución de $L_0$ en términos de $S_0$ desde arriba.

Answer 2

Motkzin rutas de hecho parece prometedor.

Considere la posibilidad de que una palabra que termina en el origen debe ser de la forma $(M0^*)^*$ donde $M$ denota una Motzkin ruta de acceso y el $0$ indica que la lámpara de alternar. Por otra parte, y quizás más útil, debe ser de la forma $0^*(M'0^*)^*$ donde $M'$ denota una no-vacío Motkzin camino.

El Motkzin números tienen g.f. $$A(x) = \frac{1 - x - \sqrt{1-2x-3x^2}}{2x^2}$$ pero el desplazamiento no es exactamente lo que queremos y necesitamos el doble de cuenta de la primera mover a la derecha o a la izquierda, así que para no vacío Motzkin caminos obtenemos g.f. $$A'(x) = 2x^2A(x) = 1 - x - \sqrt{1-2x-3x^2}$$

Si tenemos $p$ no vacío Motkzin caminos, que corresponde a $A'(x)^p$. Luego tenemos a $p+1$ deficiencias en la que insertar los tornillos en el origen, y queremos una alternancia de suma porque estamos construyendo $g(0, 0, t) - g(1, 0, t)$, por lo que queremos convolución con una multinomial secuencia $$\sum_{i=0}^\infty (-1)^i \binom{p+i}{p} x^i$$ Finalmente nos suma más de $p$ para obtener $$\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}$$

---

Ahora para obtener una recurrencia nos pusimos $G(x) = \frac{1}{2x + \sqrt{1-2x-3x^2}}$ o $$G(x)\left( 2x + \sqrt{1-2x-3x^2} \right) = 1$$

No estoy del todo seguro de cuál es la mejor manera de hacer frente a que la raíz cuadrada, pero el factoring como $1 - 2x - 3x^2 = (1 - 3x)(1 + x)$ parece una opción a considerar.

A continuación, $$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$$ Un cambio de variables probablemente ayuda: vamos a $n = i + j$ $$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$$

La extracción de un par de pequeños valores de $n$ a partir de la suma tenemos $$\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$$ que la sustitución de nuevo en da

$$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$$

Para la comparación de los coeficientes de $x^0$ tenemos $g_0 = 1$, y la comparación de los coeficientes de $x^1$ tenemos $g_0 + g_1 = 0$ o $g_1 = -1$.

La comparación de los coeficientes de $x^t$ hemos $$[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]$$

Sin embargo, esto no es más eficaz para calcular que el original de recurrencia para $g(b,k,t)$, por lo que el interés principal está en el uso de la generación de la función para analizar el comportamiento asintótico.

---

Posdata: podemos usar $G$ a derivar la generación de la función $F$ $f(0, t)$ como sigue: $$\begin{eqnarray*} f(0,0) &=& 1 \\ f(0,t+1) &=& 3 f(0,t) - [x^t]G(x) \end{eqnarray*}$$ Por lo $g_t x^t$ $G$ hace $-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}$ $$F(x) = \frac{1 - xG(x)}{1-3x}$$