Número esperado de pasos antes de que tres contadores alcancen N módulo 2N al mismo tiempo

Question

Tenemos tres contadores, $i, j, k$ todos inicializados a cero. Cada paso consiste en sumar o restar uno a uno de los contadores, de forma que $(\Delta i, \Delta j, \Delta k)$ se selecciona entre $(\pm1, 0, 0), (0, \pm1, 0), (0, 0, \pm1)$ cada una con probabilidad 1/6. ¿Cuál es el número esperado de pasos antes de que todos los contadores sean N módulo 2N al mismo tiempo?

Answer 1

Todavía estoy trabajando en una solución general, pero aquí hay algunas soluciones exactas para pequeñas $N$ .

Para $N = 1..8 $ los valores exactos son 10, $\frac{416}{5}$ , $\frac{10294}{35}$ , $\frac{18481664}{25823}$ , $\frac{235115486250}{165493097}$ , $\frac{1690479776164}{681135455}$ , $\frac{25081308000562315334439801586}{6314587098176165651428105}$ , $\frac{282872889746351048352862015165111214080}{47431617359482015647230177875265569}$ .

Valores numéricos: 10, 83.2, 294.114, 715.706, 1420.7, 2481.86, 3971.96, 5963.8.

Se calcularon "por las malas", creando un gran diagrama de estados, aprovechando muchas simetrías y resolviendo un sistema de ecuaciones lineales. Hay 165 estados, por ejemplo, en el caso de $N=8$ lo que significa resolver 165 ecuaciones en 165 incógnitas. Sin duda hay una forma más inteligente de calcular esto.

Ofrezco la encuadernación $c \cdot N^3$ sin pruebas; creo que el número esperado de pasos es asintótico a este valor con $c \approx 12$ .

Añadido el 13-Nov-2010 : La siguiente tabla proporciona pruebas sólidas de la $12N^3$ límite asintótico dado anteriormente.

 N        E(N)    12(N^3)

 1        10.0        12
 2        83.2        96
 3       294.1       324
 4       715.7       768
 5      1420.7      1500
 6      2481.9      2592
 7      3972.0      4116
 8      5963.8      6144
 9      8530.2      8748
10     11743.8     12000
11     15677.6     15972 
12     20404.2     20736
13     25996.5     26364
14     32527.3     32928
15     40069.3     40500
16     48695.3     49152
17     58478.1     58956
18     69490.5     69984
19     81805.3     82308
20     95495.3     96000
21    110633.2    111132
22    127291.9    127776
23    145544.0    146004
24    165462.6    165888
25    187120.2    187500

Edición 11-Nov-2010:

He aquí el sistema de ecuaciones lineales para $N=3$ . Ostensiblemente hay $6^3 = 216$ pero por simetría puede reducirse a $20$ . Los tres subíndices de cada variable representan la distancia al estado objetivo en cada dimensión. De acuerdo con el enunciado del problema, empezamos en el nodo más alejado de la meta. Por tanto, resolvemos para $x_{3,3,3}$ aquí. (La respuesta es $\frac{10294}{35}$ ).

Muestro este tedio con la esperanza de que alguien pueda averiguar cómo generalizar.

$x_{0,0,0}=0 $

$x_{0,0,1}=\frac{1}{6} x_{0,0,0}+\frac{1}{6} x_{0,0,2}+\frac{2}{3} x_{0,1,1}+1 $

$x_{0,0,2}=\frac{1}{6} x_{0,0,1}+\frac{1}{6} x_{0,0,3}+\frac{2}{3} x_{0,1,2}+1 $

$x_{0,0,3}=\frac{1}{3} x_{0,0,2}+\frac{2}{3} x_{0,1,3}+1 $

$x_{0,1,1}=\frac{1}{3} x_{0,0,1}+\frac{1}{3} x_{0,1,2}+\frac{1}{3} x_{1,1,1}+1 $

$x_{0,1,2}=\frac{1}{6} x_{0,0,2}+\frac{1}{6} x_{0,1,1}+\frac{1}{6} x_{0,1,3}+\frac{1}{6} x_{0,2,2}+\frac{1}{3} x_{1,1,2}+1 $

$x_{0,1,3}=\frac{1}{6} x_{0,0,3}+\frac{1}{3} x_{0,1,2}+\frac{1}{6} x_{0,2,3}+\frac{1}{3} x_{1,1,3}+1 $

$x_{0,2,2}=\frac{1}{3} x_{0,1,2}+\frac{1}{3} x_{0,2,3}+\frac{1}{3} x_{1,2,2}+1 $

$x_{0,2,3}=\frac{1}{6} x_{0,1,3}+\frac{1}{3} x_{0,2,2}+\frac{1}{6} x_{0,3,3}+\frac{1}{3} x_{1,2,3}+1 $

$x_{0,3,3}=\frac{2}{3} x_{0,2,3}+\frac{1}{3} x_{1,3,3}+1 $

$x_{1,1,1}=\frac{1}{2} x_{0,1,1}+\frac{1}{2} x_{1,1,2}+1 $

$x_{1,1,2}=\frac{1}{3} x_{0,1,2}+\frac{1}{6} x_{1,1,1}+\frac{1}{6} x_{1,1,3}+\frac{1}{3} x_{1,2,2}+1 $

$x_{1,1,3}=\frac{1}{3} x_{0,1,3}+\frac{1}{3} x_{1,1,2}+\frac{1}{3} x_{1,2,3}+1 $

$x_{1,2,2}=\frac{1}{6} x_{0,2,2}+\frac{1}{3} x_{1,1,2}+\frac{1}{3} x_{1,2,3}+\frac{1}{6} x_{2,2,2}+1 $

$x_{1,2,3}=\frac{1}{6} x_{0,2,3}+\frac{1}{6} x_{1,1,3}+\frac{1}{3} x_{1,2,2}+\frac{1}{6} x_{1,3,3}+\frac{1}{6} x_{2,2,3}+1 $

$x_{1,3,3}=\frac{1}{6} x_{0,3,3}+\frac{2}{3} x_{1,2,3}+\frac{1}{6} x_{2,3,3}+1 $

$x_{2,2,2}=\frac{1}{2} x_{1,2,2}+\frac{1}{2} x_{2,2,3}+1 $

$x_{2,2,3}=\frac{1}{3} x_{1,2,3}+\frac{1}{3} x_{2,2,2}+\frac{1}{3} x_{2,3,3}+1 $

$x_{2,3,3}=\frac{1}{6} x_{1,3,3}+\frac{2}{3} x_{2,2,3}+\frac{1}{6} x_{3,3,3}+1 $

$x_{3,3,3}=x_{2,3,3}+1 $

Answer 2

He aquí un esbozo de otra derivación del tiempo de golpe para un contador (en relación con la respuesta de Mike).

Considere lo siguiente $\pm 1$ paseo aleatorio por la línea entera. Es bien sabido que el tiempo esperado que se tarda en alcanzar la distancia $N$ es $N^2$ . En nuestro caso, la distancia de alcance $N$ y alcanzando el valor $N$ modulo $2N$ es el mismo, ya que no podemos llegar a $\pm 3N$ sin pasar por $\pm N$ .

Movemos el contador especificado en la expectativa una vez cada tres pasos, y por lo tanto es $3N^2$ y no $N^2$ (porque la dirección del movimiento y esta "espera de nuestro turno" son independientes).

Este argumento demuestra que el caso de un contador es bastante especial.

Answer 3

Esta cuestión en toda su generalidad probablemente se aborde mejor mediante algún enfoque de función generadora, como señala Qiaochu. He jugado con la $N=1$ y obtuve algunos resultados interesantes que comparto a continuación. Para el $N=1$ caso, no tenemos que distinguir entre el $+1$ y el $-1$ s. De hecho, una buena visualización es pensar en una fila de bombillas, una de las cuales se enciende aleatoriamente en cada fase. Pregunta: Dado que todas están apagadas al principio, ¿cuánto tardan por término medio en encenderse?

Sea $f_k$ el número esperado de pasos para que se enciendan todas las bombillas a partir de $k$ bombillas de un total de $n$ bombillas. A continuación, tenemos las recursiones

$f_0 = 1 + f_1$

$f_k = 1 + \frac{k}{n} f_{k-1} + \frac{n-k}{n} f_{k+1}$

$f_n = 0$

Necesitamos resolver para $f_0$ . Hice trampa para resolver la recursividad resolviéndola numéricamente para varios $n$ y apelando a la OEIS. La respuesta resulta ser

$f_0 = n \sum_{j=0}^{n-1} \frac{2^j}{j+1}$ .

En el caso de $3$ bombillas, la respuesta es $10$ . No sé cómo extender este enfoque al caso de la arbitrariedad. $N$ sin ensuciarlo. No me siento muy cómodo con la generación de enfoques de solución basados en funciones. Si alguien publicara uno para este problema, me encantaría aprender las técnicas de la "functionología generadora" a través de él.

Answer 4

Aquí hay otra dirección de ataque. El número esperado de pasos antes de que un contador dado alcance $N$ es exactamente $3N^2$ .

Como en el planteamiento de I. J. Kennedy, dejemos que $x_k$ denotan el tiempo esperado antes de que un contador dado alcance $N$ dado que el contador comienza $k$ a unos pasos de $N$ . Entonces el $x_k$ 's satisfacer, por $1 \leq k \leq N-1,$ $$x_k = \frac{1}{6} (1 + x_{k+1}) + \frac{4}{6} (1 + x_k) + \frac{1}{6} (1 + x_{k-1}),$$ con condiciones de contorno $x_0 = 0$ y $x_N = \frac{2}{3} (1 + x_N) + \frac{1}{3}(1 + x_{N-1}),$ el segundo de los cuales se simplifica a $x_N = x_{N-1} + 3$ .

La ecuación de diferencia se reduce a $$x_{k+1} - 2x_k + x_{k-1} = -6,$$ y, por tanto, es lineal, no homogénea y de segundo orden. La técnica de solución es muy similar a la de la ecuación diferencial correspondiente. La ecuación característica de la ecuación en diferencias homogénea es $r^2 -2r + 1 = 0$ lo que significa que tenemos la raíz doble $r = 1$ . Así pues, la solución general de la ecuación homogénea es $y_k = A(1)^k + B k (1)^k = A + Bk$ . A continuación, utilizamos el método de los coeficientes indeterminados con $z_k = Ck^2$ como nuestro candidato para encontrar una solución particular a la ecuación no homogénea. El resultado es $C = -3$ . Así pues, la solución general de la ecuación en diferencias es $$x_k = A + Bk - 3k^{2}.$$ Ahora, utilizamos las condiciones de contorno para hallar $A$ y $B$ . Estos rendimientos $A = 0$ y $$A + BN - 3N^2 = A + B(N-1) - 3(N-1)^2 + 3.$$ Resolviendo esto, tenemos $B = 6N$ . Así pues, nuestra solución es $$x_k = 6Nk - 3k^2,$$ lo que significa $$x_N = 3N^{2}.$$

No tengo tiempo ahora para seguir con esto, pero tal vez alguien más puede utilizar esto para encontrar un límite superior razonable para el tiempo hasta que los tres contadores golpean $N$ simultáneamente como quiere el OP. En particular, sin embargo, si toma del orden de $N^2$ pasos de media para que un contador alcance $N$ por primera vez parece que debería tomar más del orden de $N^3$ pasos de media para que los tres alcancen $N$ juntos.