Asintóticamente, cuántos estudiantes al azar tengo que marcar antes de que ' he marcado dos estudiantes consecutivos

Question

De fondo

El motivtion para esta pregunta viene de las observaciones realizadas por un colega mientras él estaba haciendo la tarea y la grabación de las marcas de este año.

Su procedimiento de registro de las marcas es la siguiente. La tarea se coloca en su carpeta por los estudiantes antes de la fecha límite, (presumiblemente) en un "random" con el fin de. Una vez que pase la fecha límite, que recoge la carpeta, y comienza a marcar. Él toma la primera secuencia de comandos desde la carpeta, marcas y registros de la marca en el margen de la hoja. A continuación se toma el siguiente script, marcas y registros. Y así sucesivamente...

Mientras hace esto, se dio cuenta de que, sorprendentemente, rápidamente han entrado marcas para dos días consecutivos de los estudiantes en la lista. Por ejemplo, en una clase de 20 alumnos, sólo llevo 4 o 5 secuencias de comandos en promedio.

Esto llevó a que algunas de las preguntas a partir de él en la distribución de este número:

• ¿Cuál es la expectativa y la desviación estándar?
• Hay una fórmula explícita para cualquier tamaño de la clase? (O de una recurrencia de la relación, o cualquier otra buena manera de calcular?)
• ¿Cómo se comportan asintóticamente para grandes clases?

El programa de instalación de Problema

Vamos a frase el problema un poco más de precisión, por lo que puedo explicar lo que hemos logrado hacer.

Supongamos que usted tiene una línea de $ N $ cajas, inicialmente vacía. Seleccione uniformemente al azar un cuadro de vacantes, y a llenar. Repita esto hasta que dos cuadros consecutivos se han llenado, luego se detendrá. (Los cuadros que forman una línea, y no envuelva alrededor, por lo que los dos cuadros son no considera consecutivos). El valor de la variable aleatoria discreta $ X_N $ es el número de lleno en las cajas.

En particular, estamos buscando ahora

• Explícito fórmulas para$ E(X_N) $$ \operatorname{Var}(X_N) $, (o de relaciones de recurrencia, o lo que sea), y
• el comportamiento asintótico de estos

Ejemplo: Cuando $ N = 3 $, hay maneras posibles para terminar con dos cuadros consecutivos son

• Final, luego de en medio con una probabilidad de $ \frac{2}{3} \frac{1}{2} = \frac{1}{3} $ $ X_3 = 2 $
• Medio, luego terminar con una probabilidad de $ \frac{1}{3} 1 = \frac{1}{3} $$ X_3 = 2 $, o
• Extremo, el otro extremo y, finalmente, medio con una probabilidad de $ \frac{2}{3} \frac{1}{2} 1 = \frac{1}{3} $$ X_3 = 3 $.

Por lo tanto, tenemos la distribución completa de la $ X_3 $, y podemos calcular que $ E(X_3) = 2 \frac{2}{3} + 3 \frac{1}{3} = \frac{7}{3} = 2.\overline{3} $, et cetera.

Trabajo Actual

Me las he arreglado para dar una explícita (aunque desagradable) fórmula para $ E(X_N) $. A grandes rasgos, esto es el análisis de cómo el proceso puede terminar con $ n+1 $ cajas llenas, mirando a la configuración de un paso antes de la final, y romper esta en varios tipos. (No termina llena, un final lleno, ambos extremos se llena y varios números, $ k $, de 'triples' como $ \blacksquare \square \blacksquare $.) Puedo contar el número de cada tipo de configuración estándar utilizando técnicas combinatorias y, a continuación, trabajar la probabilidad de acabar con $ n+1 $ cajas llenas. Obtengo:

\begin{align} E(X_N) &= \sum_{n=1}^{\left\lfloor \frac{N+1}{2} \right\rfloor} \sum_{k=0}^{n-1} (n+1) \binom{n-1}{k} \Bigg[ (2n-k) \binom{N-2n}{n-k} + 2(2n-k-1) \binom{N-2n}{n-k-1} \\ & {} \quad + (2n-k-2) \binom{N-2n}{n-k-2} \Bigg] \left( n! \frac{(N-n)!}{N!} \frac{1}{N-n} \right) \, , \end{align}

y del mismo modo que yo pueda obtener la varianza. (Todavía se puede ver algo de mi enfoque se refleja en la estructura de la fórmula.)

Con esto, podemos calcular $$ E(X_{20}) = 153641/33592 \aprox 4.5737377947 \, , $$ with standard deviation $ \aprox 1.6291544998 $, lo que corrobora sus observaciones iniciales.

A partir de aquí, podemos calcular el primer millar de valores de $ E(X_N) $, para conseguir una sensación para el behaivour en un gran $ N $. El resultado es el siguiente:

Así, a primera vista, se parece quizá $ E(X_N) \sim N^{1/2} $ (más o menos una pequeña potencia). Pero es en este punto estoy atascado.

Preguntas

Mi preguntas específicas acerca de este problema son:

Hay un más claro/más compacto/más elegante fórmula para calcular explícitamente $ E(X_N) $?

• Se puede hacer a través de una recurrencia de la relación?
• ¿Qué tipo de técnicas se adaptan bien a este tipo de cálculo?

¿Qué tan precisa es mi suposición de que $ E(X_N) \sim \sqrt{N} $?

• Puedo determinar el comportamiento asintótico de la fórmula explícita?
• Si no, ¿cómo puedo encontrar el comportamiento asintótico?

Por último, (aunque no estoy esperando que en cualquier lugar cerca de una respuesta completa) ¿cómo es que todo este generalizar más complicados arreglos de cajas?

• Dicen que hacer esto en un $ N\times M $ cuadrícula, y paramos cuando nos rellenar dos casillas adyacentes (incluyendo diagonalmente, incluyendo o no en diagonal).
• O, más en general, al azar de llenado en los vértices de un grafo, con los bordes de la determinación de adyacencia.
• Lo que si algunos cuadros tienen varias partes, por lo que se pueden llenar en un número de veces?

Answer 1

En primer lugar demostrar que $$E(X_N)=\sum_{i=0} P(X_N>i)=\sum_{i=0}^{\left\lceil\frac{N+1}{2}\right\rceil} P(X_N>i)$$

y que (ecuación 1)

$$P(X_N>i)=\frac{\binom{N-i+1}{i}}{\binom{N}{i}}$$

Que da una buena fórmula de recurrencia para calcular todo con facilidad :

$$P(X_N>0)=1$$ $$P(X_N>i+1)=P(X_N>i)\frac{(N-2i)(N-2i+1)}{(N-i)(N-i+1)}$$

Ahora, utilizando la ecuación 1, y la aproximación de stirling, usted puede demostrar que

$$P(X>\alpha.\sqrt{N})\approx e^{-\alpha^2}$$

Que debe ser suficiente para demostrar que $E(X_N)=O(\sqrt{N})$.

Finalmente, para la cuadrícula de la pregunta, parece ser una pregunta abierta relacionada con la Difícil Plaza de la Entropía

Answer 2

La derivación para $\mathbb{E}\left(X_n\right)$ puede ser más sencillo.

Vamos a pensar en conseguir la probabilidad de tener exactamente dos casillas adyacentes lleno, de una fila $n$ cajas de $k$ cajas están llenas, que se puede hacer de la siguiente manera:

Primero, necesitamos obtener el número de maneras de llenado $k$ cuadros no hay dos casillas adyacentes están llenas, que resulta ser $\binom{n-k+1}{k}$ maneras.

Por lo tanto, la probabilidad de tener al menos un par adyacente llena es: \begin{align*} \mathbb{P}_k\left(\text{at least one}\right) &= 1-\frac{\dbinom{n-k+1}{k}}{\dbinom{n}{k}} \end{align*}

Del mismo modo, cuando se $k-1$ cuadros están llenos: \begin{align*} \mathbb{P}_{k-1}\left(\text{at least one}\right) &= 1-\frac{\dbinom{n-k+2}{k-1}}{\dbinom{n}{k-1}} \end{align*}

Por lo tanto, la probabilidad de que haya exactamente un par adyacente de cajas, que está lleno de, al $k$ cajas están llenas de entre $n$ cajas de:

\begin{align*} P\left(n,k\right) &= \mathbb{P}_{k}\left(\text{at least one}\right)-\mathbb{P}_{k-1}\left(\text{at least one}\right) \\ &= \frac{\dbinom{n-k+2}{k-1}}{\dbinom{n}{k-1}} - \frac{\dbinom{n-k+1}{k}}{\dbinom{n}{k}} \end{align*}

A partir de aquí, la búsqueda de la expectativa es simple: \begin{align*} \mathbb{E}\left(X_n\right) &= \sum_{i=2}^{\lfloor(n+3)/2\rfloor} i\cdot P(n,i) \end{align*}

Para $n=20$, \begin{align*} \mathbb{E}\left(X_{20}\right) &= \sum_{i=2}^{11} i\cdot P(20,i) = \frac{153641}{33592} \end{align*}

Puede que no sea capaz de responder a sus otras preguntas, por ahora, pero creo que la fórmula anterior puede hacer que sea más fácil.