Tiempo medio para encontrar un duplicado con independencia pares

Question

Asumir un proceso en el que las muestras uniformemente al azar en el rango de $[1,\ldots,n]$. Estoy interesado en el tiempo de espera para encontrar un duplicado dado sólo que el proceso de muestreo es de a pares independientes. Que es que me gustaría encontrar el tiempo de espera hasta que una muestra coincide con una de las muestras tomadas antes.

Una manera de calcular el tiempo de espera es $$E=\sum_{x=1}^\infty P(X \geq x).$$ Here $$ X es una variable aleatoria que representa el tiempo en el que el primer duplicado se encuentra.

Si las muestras fueron totalmente independientes, entonces tendríamos que $$\sum_{x=1}^\infty P(X \geq x) = \sum_{x=1}^\infty \prod_{i=1}^{x-1} (1-i/n).$$ Podemos enlazado a esta cantidad con el hecho de que $e^{-2x} \leq 1-x \leq e^{-x}$ al $0 \leq x \leq 0.5$ y, a continuación, vinculado a la suma resultante mediante una integral. Esto le da un asintótica obligado de $\Theta(\sqrt{n})$ pasos.

¿Cómo realizar un análisis similar donde sólo tenemos pares de la independencia y también preferentemente obtener un resultado asintótico en lugar de sólo un límite superior?

EDIT: Después de Henry gran respuesta, realmente me gustaría saber un límite inferior así como el límite superior que le ha dado. En particular, ¿el límite inferior para totalmente independiente de muestreo de $\Omega(\sqrt{n})$ también se aplican a este pairwise caso independiente? O, alternativamente, puede alguien pensar que de un pairwise proceso independiente que tiene una media de menos de orden $\sqrt{n}$?

Answer 1

El peor de los casos es $O(n)$. Claramente por encasillar a los argumentos de la expectativa no puede exceder $n+1$, pero hay ejemplos en los que se supera el $n$.

Suponga que las muestras se $S_1, S_2, \ldots$ y

• que $S_1$ tiene una distribución uniforme en $\{1,2,\ldots,n\}$,

• que con una probabilidad de $\frac{1}{n}$ $S_1 = S_2 = \cdots = S_{n} $ y con una probabilidad de $\frac{n-1}{n}$ $S_j$ tener una distribución uniforme en $\{1,2,\ldots,n\} - \{S_1,\ldots , S_{j-1} \}$ $2 \le j \le n$ y

• que $S_{n+1}$ tiene una distribución uniforme en $\{1,2,\ldots,n\}$ independientemente de todas las demás,

entonces hay una probabilidad de $\frac{1}{n}$ que usted necesita un tamaño de muestra de $2$ y una probabilidad de $\frac{n-1}{n}$ usted necesita un tamaño de muestra de $n+1$ encontrar un valor duplicado. Esto le da una expectativa de $n+\frac{1}{n}$$O(n)$.

Answer 2

Un simple límite inferior de la prueba fue dada en http://mathoverflow.net/questions/102079/bounds-for-duplicate-finding-with-limited-independence por Douglas Zare. Puedo incluir un poco copia editada por la integridad.

El número esperado de duplicados entre los primeros a $m$ es una cota superior para la probabilidad de un duplicado en el primer $m$. Para $m=c\sqrt{n}$ el número esperado de duplicados en $c/2$, por lo que la probabilidad de que la primera duplicado es mayor que $\sqrt{n}$ es mayor que $1/2$, lo que significa que el esperado primer duplicado es mayor que $\sqrt{n}/2$.

Answer 3

Este es el generalizado problema de cumpleaños. Es de su $n$ $d$ en el artículo.