Robot pintando una pista circular.

Question

Una pista circular de longitud $2n$ metros de ha $2n$ teletransportadores igualmente espaciados a lo largo de la pista. Cada teletransportador, cuando se activa, instantáneamente teletransporta al objeto dentro de la antipodally frente teletransportador.

Comenzando en la primera teletransportación, un robot comienza a mover las agujas del reloj a lo largo de la de la pista a una tasa de $1$ metro/segundo. A medida que se mueve a lo largo de la pista, el robot de pinturas de la pista roja. Cuando el robot llega a un teletransportador, el teletransportador activa con una probabilidad de $1/2$ y no se activa con probabilidad de $1/2$. El robot sigue avanzando hacia la derecha después de haber sido transportado.

¿Cuál es el número esperado de segundos hasta que la totalidad de la pista es pintado de rojo?

Por heurística, sospecho que la cantidad es asintótica a $n\log_{2} (n)$, pero estoy teniendo problemas para demostrar esto (o el cálculo de un resultado exacto). Cualquier ayuda sería muy apreciada.

Answer 1

Nota: esta es una respuesta parcial. Este problema ha $n$-segundo ciclos largos, y es difícil decir donde en el ciclo de el robot va a terminar. Te doy el número esperado de ciclos. Por lo tanto, este será un poco más grande que la verdadera respuesta. Lo más probable es que se pierda por menos de la mitad de un ciclo, ya que el segmento está pintado último es uniformemente al azar si ese segmento está solo en su ciclo, pero si varios segmentos que están pintadas en el último ciclo, entonces es el último segmento que cuenta.

Par el antipodal pista de segmentos de dos-por-dos en $n$ pares. La etiqueta de cada par con un número entero de$1$$n$, en el orden por el cual el robot visitas. Ahora, en (o, más bien, a la derecha después de) cualquier entero tiempo de $i$, el robot ha comenzado la pintura de uno de los segmentos en el par número $i+1$ (reducción del modulo $n$), y que uno que se está $50$-$50$.

Deje que la variable aleatoria $X_i$ $1\leq i \leq n$ ser el número de veces que el robot pasa a través de par de número de $i$ (reducción del modulo $n$) antes de los dos segmentos están pintadas, menos uno. Entonces es geométricamente distribuidos con el parámetro $p$: $$ P(X_i = k) = \frac1{2^k},\quad P(X_i \leq k) = \frac{2^k-1}{2^k} $$ y queremos que la expectativa de mayor uno de ellos. Tras esta respuesta tenemos $$ E[\max_i(X_i)] = \sum_{k \geq 1}\left(1-\left(\frac{2^k-1}{2^k}\right)^n\right) $$ (No sé si esa suma tiene una forma cerrada). Agregar $1$ a, y se obtiene el número esperado de ciclos completos.