¿Cuál es un límite inferior estricto para el tiempo de recogida de cupones?

Question

En el clásico El problema del coleccionista de cupones es bien sabido que el tiempo $T$ necesarios para completar un conjunto de $n$ cupones elegidos al azar satisface $E[T] \sim n \ln n $ , $Var(T) \sim n^2$ y $\Pr(T > n \ln n + cn) < e^{-c}$ .

Este límite superior es mejor que el dado por la desigualdad de Chebyshev, que sería aproximadamente $1/c^2$ .

Mi pregunta es: ¿existe un correspondiente mejor que Chebyshev límite inferior para $T$ ? (por ejemplo, algo como $\Pr(T < n \ln n - cn) < e^{-c}$ ) ?

Answer 1

Aporto esto como segunda respuesta, ya que el análisis es completamente elemental y proporciona exactamente el resultado deseado.

Propuesta Para $c > 0$ y $n \geq 1$ , $$ \mathbb{P}(T < n \log n - c n ) < e^{-c} \>. $$

La idea que subyace a la prueba es sencilla:

1. Representa el tiempo que transcurre hasta que se recogen todos los cupones como $T = \sum_{i=1}^n T_i$ donde $T_i$ es el tiempo que $i$ th (hasta ahora) único se recoge el cupón. En $T_i$ son variables aleatorias geométricas con tiempos medios de $\frac{n}{n-i+1}$ .
2. Aplicar una versión del límite de Chernoff y simplificar.

Prueba

Para cualquier $t$ y cualquier $s > 0$ tenemos que $$ \mathbb{P}(T < t) = \mathbb{P}( e^{-s T} > e^{-s t} ) \leq e^{s t} \mathbb{E} e^{-s T} \> . $$

Desde $T = \sum_i T_i$ y el $T_i$ son independientes, podemos escribir $$ \mathbb{E} e^{-s T} = \prod_{i=1}^n \mathbb{E} e^{- s T_i} $$

Ahora que $T_i$ es geométrica, digamos con probabilidad de éxito $p_i$ entonces un simple cálculo muestra $$ \mathbb{E} e^{-s T_i} = \frac{p_i}{e^s - 1 + p_i} . $$

En $p_i$ para nuestro problema son $p_1 = 1$ , $p_2 = 1 - 1/n$ , $p_3 = 1 - 2/n$ etc. Por lo tanto, $$ \prod_{i=1}^n \mathbb{E} e^{-s T_i} = \prod_{i=1}^n \frac{i/n}{e^s - 1 + i/n}. $$

Vamos elija $s = 1/n$ y $t = n \log n - c n$ para algunos $c > 0$ . Entonces $$ e^{s t} = n e^{-c} $$ y $e^s = e^{1/n} \geq 1 + 1/n$ , dando como resultado $$ \prod_{i=1}^n \frac{i/n}{e^s - 1 + i/n} \leq \prod_{i=1}^n \frac{i}{i+1} = \frac{1}{n+1} \> . $$

Uniendo todo esto, obtenemos que $$ P(T < n \log n - c n) \leq \frac{n}{n+1} e^{-c} < e^{-c} $$

como desee.

Answer 2

Aunque @cardinal ya ha dado una respuesta que da precisamente el límite que estaba buscando, he encontrado un argumento similar al estilo de Chernoff que puede dar un límite más fuerte:

Propuesta : $$ Pr (T \leq n \log n - c n) \leq \exp(- \frac{3c^2}{\pi^2} ) \> . $$ (esto es más fuerte para $c > \frac{\pi^2}{3}$ )

Prueba :

Como en la respuesta de @cardinal, podemos utilizar el hecho de que $T$ es una suma de variables aleatorias geométricas independientes $T_i$ con probabilidades de éxito $p_i = 1 - i/n$ . De ello se deduce que $E[T_i] = 1/p_i$ y $E[T] = \sum_{i=1}^{n} E[T_i] = n \sum_{i=1}^n \frac{1}{i}\geq n \log n$ .

Definir ahora nuevas variables $S_i : = T_i - E[T_i]$ y $S : = \sum_i S_i$ . Podemos escribir $$ \Pr (T \leq n \log n - c n) \leq \Pr (T \leq E[T] - c n) = \Pr (S \leq - c n) $$ $$ = \Pr\left(\exp(-s S ) \geq \exp( s cn) \right) \leq e^{-s c n} E\left[ e^{-s S} \right] $$

Calculando las medias, tenemos

$$ E[e^{-s S}] = \prod_i E[e^{-s S_i}] = \prod_i \frac{e^{s / p_i} } {1 + \frac{1}{p_i} (e^s -1)} \leq e^{\frac{1}{2}s^2\sum_i p_i^{-2}} $$ donde la desigualdad se deduce del hecho de que $e^s - 1\geq s$ y también $\frac{e^z}{1+z}\leq e^{\frac{1}{2}z^2}$ para $z\geq 0$ .

Así, puesto que $\sum_i p_i ^{-2} = n^2 \sum_{i=1}^{n-1} \frac{1}{i^2} \leq n^2 \pi^2/6$ podemos escribir \begin{align*} \Pr( T \leq n \log n - c n ) \leq e^{\frac{1}{12} (n \pi s)^2 - s c n}. \end{align*}

Minimizar los excesos $s>0$ obtenemos finalmente $$ \Pr( T \leq n\log n -cn ) \leq e^{-\frac{3 c^2 }{\pi^2}} $$

Answer 3

Nota importante : He decidido eliminar la prueba que di originalmente en esta respuesta. Era más larga, más computacional, utilizaba martillos más grandes, y demostraba un resultado más débil en comparación con la otra prueba que he dado. En general, un enfoque inferior (en mi opinión). Si estás realmente interesado, supongo que puedes mirar las ediciones.

Los resultados asintóticos que cité originalmente y que aún se encuentran más abajo en esta respuesta muestran que a medida que $n \to \infty$ podemos hacer algo mejor que el límite demostrado en la otra respuesta, que se mantiene para todos $n$ .

---

Los siguientes asintótica los resultados se mantienen

$$ \mathbb{P}(T > n \log n + c n ) \to 1 - e^{-e^{-c}} $$

y

$$ \mathbb{P}(T \leq n \log n - c n ) \to e^{-e^c} \>. $$

La constante $c \in \mathbb{R}$ y los límites se toman como $n \to \infty$ . Obsérvese que, aunque están separados en dos resultados, son prácticamente el mismo resultado, ya que $c$ no está obligado a ser no negativo en ninguno de los casos.

Véase, por ejemplo, Motwani y Raghavan, Algoritmos aleatorios págs. 60-63 para una prueba.

---

También : David tiene la amabilidad de proporcionar una prueba de su límite superior en los comentarios a esta respuesta.

Answer 4

Benjamin Doerr da (en el capítulo " Análisis de la heurística de búsqueda aleatoria: Tools from Probability Theory" en el libro "Theory of Randomized Search Heuristics", véase el enlace para un PDF en línea) una demostración algo sencilla de

Propuesta Sea $T$ sea el tiempo de parada del proceso de recogida de cupones. Entonces $\Pr[T\le (1-\epsilon)(n-1)\ln n]\le e^{-n^{\epsilon}}$ .

Esto parece dar la asíntota deseada (de la segunda respuesta de @cardinal), pero con la ventaja de ser cierto para todo $n$ y $\epsilon$ .

He aquí un esbozo de prueba.

Esbozo de prueba: Sea $X_i$ sea el caso de que el $i$ -ésimo cupón se recoge en el primer $t$ sorteos. Así, $\Pr[X_i=1]=(1-1/n)^t$ . El hecho clave es que el $X_i$ están correlacionadas negativamente, para cualquier $I\subseteq[n]$ , $\Pr[\forall i\in I, X_i=1]\le\prod_{i\in I}\Pr[X_i=1]$ . Intuitivamente, esto está bastante claro, ya que sabiendo que el $i$ -ésimo cupón del primer $t$ sorteos haría menos probable que el $j$ -ésimo cupón también se extrae en el primer $t$ sorteos.

Se puede demostrar la afirmación, pero ampliando el conjunto $I$ en 1 en cada paso. Entonces se reduce a demostrar que $\Pr[\forall i\in I, X_i=1|X_j=1]\le\Pr[\forall i\in I,X_i=1]$ para $j\notin I$ . Equivalentemente, al promediar, se reduce a mostrar que $\Pr[\forall i\in I, X_i=1|X_j=0]\ge\Pr[\forall i\in I,X_i=1]$ . Doerr sólo da un argumento intuitivo para ello. Una vía para demostrarlo es la siguiente. Se puede observar que condicionado a la $j$ cupón que viene después de todos los cupones en $I$ que la probabilidad de extraer un nuevo cupón de $I$ después del sorteo $k$ hasta ahora es ahora $\frac{|I|-k}{n-1}$ en lugar del anterior $\frac{|I|-k}{n}$ . Así que descomponiendo el tiempo para recoger todos los cupones como una suma de variables aleatorias geométricas, podemos ver que condicionando el $j$ -cupón a continuación $I$ aumenta las probabilidades de éxito, por lo que hacer el condicionamiento sólo hace más probable recoger antes los cupones (por dominancia estocástica: cada variable aleatoria geométrica aumenta, en términos de dominancia estocástica, por el condicionamiento, y esta dominancia puede aplicarse luego a la suma).

Dada esta correlación negativa, se deduce que $\Pr[T\le (1-\epsilon)(n-1)\ln n]\le (1-(1-1/n)^t)^n$ que da el límite deseado con $t=(1-\epsilon)(n-1)\ln n$ .

Nota añadida en la prueba: El enlace anterior está obsoleto. Una nueva versión de este resultado con una demostración completa (es decir, incluyendo la declaración de correlación negativa) se puede encontrar en el Teorema 1.9.3 en B. Doerr. Probabilistic Tools for the Analysis of Randomized Optimization Heuristics. En B. Doerr y F. Neumann, editores, Theory of Evolutionary Computation: Recent Developments in Discrete Optimization, páginas 1-87. Springer, 2020 .