¿Número esperado de lanzamientos de monedas hasta que todos los autos se muevan al final del arreglo?

Question

¿Número esperado de lanzamientos de monedas hasta que todos los autos se muevan al final del arreglo?

Matemáticas
probabilidad
valor esperado
variables aleatorias

cashwick

Imagina que tenemos una matriz de longitud $2n$ , donde la primera $n$ las entradas son un $C$ (que representa un coche de juguete) y el resto $n$ las entradas están vacías. Además, tenemos $n$ monedas justas etiquetadas $1$ a través de $n$ , donde moneda $i$ corresponde a coche $C_i$ en la matriz.

En cada paso de tiempo, volteamos todo $n$ monedas si moneda $i$ sale como cabezas, luego coche $C_i$ avanza en la matriz por un punto, pero solo si no está bloqueado por otro automóvil directamente en la ranura frente a él. De lo contrario, si se bloquea o la moneda sale cruz, el coche $C_i$ no hace nada.

La pregunta tiene dos partes:

¿Cuál es el número esperado de pasos de tiempo hasta que $n$ - $th$ coche llega al final de la matriz (llega a la ranura $2n$ )?
¿Cuál es el número esperado de pasos de tiempo hasta que todos los $n$ los coches se han movido desde el primer $n$ ranuras de la matriz hasta el último $n$ tragamonedas?

He resuelto la parte 1 de la siguiente manera. El número esperado de lanzamientos para que una moneda caiga como cara es $2$ , y el $n$ - $th$ el coche tiene que moverse $n$ ranuras para llegar al final (y nunca está bloqueado por nada), por lo que el número esperado de pasos de tiempo es $2n$ . Sin embargo, estoy perdido en el enfoque de la parte 2. Pienso que debería estar en el orden $O(n\log n$ ) pero no sé cómo proceder. Sigo encontrándome con una larga cadena de probabilidades condicionales y me pregunto si hay una forma más elegante que me estoy perdiendo.

zoidberg

creo que al menos es orden

n^{2}

$n^2$ ya que esa es la cantidad de tiempo que le toma al primer automóvil moverse un solo paso

hierba steinberg

Ver cuánto tarda el coche en

n - 1

$n-1$ para llegar a su destino y luego para el coche en

n - 2

$n-2$ y ver si hay un patrón.

ross milikan

@norfair: no, se necesita

2 n

$2n$ para que el primer auto se mueva una vez.

n

$n$ acepta

2

$2$ voltea, entonces

n - 1

$n-1$ acepta

2

$2$ volteretas, etc. Pero mientras el auto 1 está esperando, los autos delanteros se están moviendo más adelante. Creo que es lineal en

n

$n$ .

zoidberg

Sí, tiene usted razón. Por alguna razón, los estaba sumando para obtener el crecimiento cuadrático.

zoidberg

Por cierto, creo que esto está relacionado con el Proceso de Exclusión Simple Totalmente Asimétrico (o TASEP).

Respuestas (1)

¿Número esperado de lanzamientos de monedas hasta que todos los autos se muevan al final del arreglo?

creo que al menos es orden $n^2$ ya que esa es la cantidad de tiempo que le toma al primer automóvil moverse un solo paso
Ver cuánto tarda el coche en $n-1$ para llegar a su destino y luego para el coche en $n-2$ y ver si hay un patrón.
@norfair: no, se necesita $2n$ para que el primer auto se mueva una vez. $n$ acepta $2$ voltea, entonces $n-1$ acepta $2$ volteretas, etc. Pero mientras el auto 1 está esperando, los autos delanteros se están moviendo más adelante. Creo que es lineal en $n$ .
Sí, tiene usted razón. Por alguna razón, los estaba sumando para obtener el crecimiento cuadrático.
Por cierto, creo que esto está relacionado con el Proceso de Exclusión Simple Totalmente Asimétrico (o TASEP).

ross milikan · Answer 1

No tengo una buena respuesta para la segunda parte, pero podemos establecer límites. Un límite superior es $2n^2$ . Imagina que lo hacemos más difícil diciendo el $n^{th}$ coche tiene que llegar al final antes de que el $n-1^{st}$ el coche se mueve en absoluto, entonces el $n-1^{st}$ tiene que llegar al final antes de que $n-2^{nd}$ se mueve en absoluto y así sucesivamente. En la primera parte, el tiempo esperado para cada automóvil es $2n$ entonces el tiempo total esperado es $2n^2$ . Como los autos solo pueden terminar más rápido si se les permite moverse antes, este es un límite superior.

Para el límite inferior, consideremos solo automóviles $n$ y $n-1$ y pregunta la hora $n-1$ para terminar. Lo haremos más fácil diciendo que si $n$ obtiene dos espacios vacíos entre los dos autos $n-1$ Puede moverse libremente sin preocuparse por ponerse al día. Ahora deja $A(k)$ Sea el número esperado de movimientos cuando el automóvil $n-1$ tiene $k$ espacios para ir y coche $n$ está inmediatamente enfrente de él. Dejar $B(k)$ Sea el número esperado de movimientos cuando el automóvil $n-1$ tiene $k$ espacios para ir y coche $n$ tiene $k-1$ espacios para ir. Podemos escribir recurrencias acopladas

A (k) = 1 + \frac{1}{2} B (k) + \frac{1}{2} A (k) A (k) = 2 + B (k)

$A(k)=1+\frac 12B(k)+\frac 12A(k)\\A(k)=2+B(k)$ porque si los carros estan juntos solo carro

n

$n$ puede moverse y se mueve (poniendo un espacio entre ellos) si sale cara.

B (k) = 1 + \frac{1}{4} B (k - 1) + \frac{1}{4} (2 k) + \frac{1}{4} A (k - 1) + \frac{1}{4} B (k)

$B(k)=1+\frac 14B(k-1)+\frac 14(2k)+\frac 14A(k-1)+\frac 14B(k)$ porque si a los dos les sale cara estamos en

B (k - 1)

$B(k-1)$ , si solo el delantero saca cara ya no interfiere y car

n - 1

$n-1$ llegará al final en

2 k

$2k$ mas jugadas, si solo la retaguardia saca cara estamos en

A (k - 1)

$A(k-1)$ y si ninguno sale cara nos quedamos donde estamos. El sistema converge a

A (k) = 2 k + 4

$A(k)=2k+4$ desde abajo. el tiempo para el coche

n - 2

$n-2$ al menos debe ser

2 n + 8

$2n+8$ porque el coche

n - 1

$n-1$ limita el coche

n - 1

$n-1$ al menos tanto como el coche

n

$n$ limita el coche

n - 1

$n-1$ . Esto dice el tiempo para el coche

1

$1$ Por lo menos

2 n + 4 (n - 1) = 6 n - 4

$2n+4(n-1)=6n-4$ . Sospecho que no es mucho peor que esto.

¿Número esperado de lanzamientos de monedas hasta que todos los autos se muevan al final del arreglo?

cashwick

zoidberg

hierba steinberg

ross milikan

zoidberg

zoidberg

Respuestas (1)

ross milikan

¿Cómo puedo usar la desigualdad de Cauchy-Schwarz en esta función de variables aleatorias?

Varianza condicional de variables aleatorias discretas

La variable aleatoria no tiene una expectativa

Indicador de variables aleatorias de dos eventos

Uso inesperado de la linealidad de la expectativa con variable aleatoria indicadora en problemas

Encuentra VarVar\operatorname{Var} del número de vértices aislados

Valor esperado para variables aleatorias mutuamente independientes

X,Y ~ Unif(0,1) no necesariamente independiente, ¿puede P(X+Y>1)>1/2?

¿Por qué necesitamos una secuencia de variables aleatorias? ¿No es suficiente una función?

Media de una Distribución Exponencial cuyo parámetro de tasa también se distribuye exponencialmente