"El problema de "¿Cuánto he visto ya del panorama general?

Question

TL;DR / Formulación teórica

Sea $X_1, X_2, ..., X_k$ sea una secuencia de variables aleatorias i.i.d. con $X_i \sim \mathcal{U}\{1, 2, ..., n\}$ (distribución uniforme discreta). El parámetro $n$ es desconocido. Sea $U$ sea el número de único observados en la secuencia. Dado $k$ y $U$ cómo calcular $n$ ?

---

El problema

Sea $A = \{a_1, a_2, ..., a_n\}$ ser un conjunto de "conceptos" que tendrá que aprender, por ejemplo, para un curso universitario.

Como aún no ves el panorama general del tema, no tienes ni idea de lo grande que es. $n$ es, y desea estimar $n$ .

Dentro de unos días, hablará con $k$ diferentes personas - cada vez es una discusión individual con un amigo que estudió el tema antes, y que se supone que domina todos los $n$ conceptos a la perfección. Cada amigo elige un concepto uniformemente al azar en el conjunto $A$ y te habla de ello.

Al final del $k$ discusiones, se escribe $u$ el número de único conceptos vistos.

Objetivo: cómo calcular $n$ en función de $k$ y $u$ ?

Ejemplo 1: si entre $k=15$ un concepto ha sido discutido dos veces (1 repetición), otro concepto ha sido discutido tres veces (2 repeticiones), y todos los demás sólo una vez, entonces el número total de repeticiones es $3$ y el número de conceptos únicos tratados es $u=12$ . Entonces puedes imaginarte que si continuaras con más discusiones, aparecerían muchos nuevos conceptos no vistos. Así $n$ es probablemente grande.

Ejemplo 2: si entre $k=15$ debates, se ha debatido un concepto $10$ veces, otra $3$ veces, y otros dos conceptos una vez cada uno, entonces $u = 4$ . Como muchas personas hablaron del mismo concepto (¡aunque lo eligieron al azar!), da la impresión de que probablemente haya visto la mayor parte de todo el tema. Así, $n$ no es tan grande.

Cómo calcular $n$ ?

---

Otras aplicaciones

A) Eres nuevo en la ciudad y no sabes lo grande que es ( $n$ ) lo es. Cada vez que vas a un bar ves gente nueva que no habías visto antes =>. $k \approx u$ => $n$ es probablemente grande. Si, por el contrario, siempre ves a las mismas personas una y otra vez ( $u$ mucho menor que $k$ ), entonces $n$ es probablemente pequeño.

B) Estás escribiendo un libro, y preguntas $k$ amigos para que lo corrijan. Cada amigo informa $1$ error al azar entre los errores que ha visto. Si el número total de único errores vistos por los lectores es mucho mucho menos que $k$ es decir, muchas repeticiones en los errores comunicados, significa que probablemente ha cubierto la mayoría de los errores (suponiendo que la distribución sea uniforme, etc.).
Si, por el contrario, cada corrector señala un error que nadie más ha señalado, es una mala noticia para usted: ¡probablemente haya muchos más errores que encontrar en el libro!

Answer 1

He aquí dos enfoques (hay otros)

A. La probabilidad de ver $u$ valores únicos al elegir $k$ de $n$ con sustitución es $$\dfrac{S_2(k,u)\, n!}{n^k(n-u)!}$$ donde $S_2(k,u)$ es un Número de Stirling del segundo tipo . Así que se podría estimar $n$ tomando el valor que maximiza esta probabilidad para un determinado $k$ y $u$ . Este será el mayor número entero $n$ para lo cual $n (n-1)^k \ge (n-u) n^k$

B. El número esperado de valores únicos observados al elegir $k$ de $n$ con sustitución es $$E[u] = n\left(1-\left(1- \frac1n\right)^k\right) .$$ Así que se podría estimar $n$ tomando el valor que daría el valor observado de $u$

Como ejemplo numérico, supongamos que tiene $k=10$ muestras y observar $u=6$ casos singulares. Entonces el método A podría sugerir una estimación de $n=8$ mientras que el método B sugeriría una estimación de unos $8.296887$

Answer 2

Notas adicionales a la respuesta de Henry (tuve que escribirla para entender la parte B.):

Sea $$\Omega = \{ (x_1, x_2, ..., x_k), \textrm { with } x_i \in [\![1,n]\!] \},$$ $$B_j= \{ (x_1, x_2, ..., x_k),\textrm{ with }x_i \in [\![1,n]\!] -\{j\} \}$$ y $$C_j= \{ (x_1, x_2, ..., x_k),\textrm{ with at least one }x_i = j \}.$$ Entonces $P(C_j)= 1 - P(B_j) = 1 - \frac{(n-1)^k}{n^k} = 1 - (1 - 1/n)^k$ .

Ahora dado $(X_1, X_2, ..., X_k)$ variables aleatorias i. i. d. (cada una uniforme en $[\![1,n]\!]$ ), sea $U$ sea la variable aleatoria que da el número de valores únicos entre ellos.

Con la notación $$Y_j = \left\{ \begin{array}{ll} 1 & \mbox{if } X_1 =j \mbox{ or }X_2 =j \mbox{ or ... or } X_k =j \\ 0 & \mbox{else} \end{array} \right.$$ que tenemos: $U = \sum_{j=1}^n Y_j$ y:

$$E[U] = \sum_{j=1}^n E[Y_j] = \sum_{j=1}^n 0P(Y_j=0) + 1P(Y_j=1) = \sum_{j=1}^n P(C_j)=n(1 - (1 - 1/n)^k).$$