Número esperado de intentos para elegir x valores únicos

Question

Ha pasado mucho tiempo desde que lidié con la probabilidad, así que pensé que iba a preguntar aquí. Estoy muestreando elementos de forma independiente y uniforme y con la repetición de una población. Dado que la población es de tamaño n, ¿cuántos intentos (en expectativa) me llevaría reunir x elementos únicos?

Gracias :)

Answer 1

Si tenemos $n$ cosas de las que estamos eligiendo, ver que siempre tenemos $1$ único elemento después de que el primer sorteo. A partir de aquí, ahora estamos tratando con una Distribución Geométrica con probabilidad de éxito que se $\dfrac{n-1}{n}$. El número esperado de trata aquí es $\dfrac{n}{n-1}$. Así, el número esperado de sorteos hasta que usted consigue $2$ únicos elementos de una piscina de tamaño $n$ es $$E(1)+E(2) = 1+\dfrac{n}{n-1}$$

Donde $E(m) = \dfrac{n}{n-m+1}$ es el número esperado de sorteos después de encontrar el $(m-1)^{th}$ único elemento hasta que hayas encontrado la $m^{th}$ único elemento. Tomamos $E(1) = \dfrac{n}{n-1+1} = 1$ a ser el número esperado de sorteos hasta el primer elemento único, que es sólo el primer sorteo.

Este patrón se generalizará, con el valor esperado de sorteos hasta que usted ha $x \le n$ únicos elementos es $$\sum_{i=1}^x E(i) = E(1)+E(2)+\dots+E(x)$$

Answer 2

Si ya ha recolectado $k$ artículos únicos, la probabilidad de que el próximo artículo sea diferente es ${n-k\over n}.$ Tenemos una distribución geométrica, por lo que el número esperado de sorteos hasta que obtengamos un artículo diferente es ${n\over n-k}.$ El número esperado de sorteos hasta que obtengamos $x$ artículos diferentes es $$\sum_{k=0}^{x-1}{n\over n-k}=n\sum_{k=0}^{x-1}{1\over n-k}$ $

Answer 3

No es 100% seguro que esta es la solución correcta, pero creo que, básicamente, tienen que utilizar una secuencia geométrica de las variables aleatorias (https://en.wikipedia.org/wiki/Geometric_distribution)

Así que supongamos $n$ = 10. Si $x = 1$, entonces estamos interesados en el número de ensayos para dibujar un valor único. Esperemos que no necesitamos demostrar que usted sólo necesita una prueba para ello.

Ahora, si $x = 2$, luego tenemos el número de ensayos para dibujar un único valor ($y_1$) y, a continuación, el número de ensayos para dibujar otro único valor de $(y_2)$. El primer éxito que sucede en el primer ensayo con probabilidad 1, y luego la probabilidad de que se tarda $k$ más ensayos para obtener el segundo éxito está dado por $P(y_2 = k) = (1 - 9/10)^k(9/10)$, ya que vamos a dibujar un segundo valor único con una probabilidad de 9/10.

Observe que cada prueba es independiente de aquí, y lo único que cambia de juicio a prueba es la probabilidad de éxito, es $1$ para el primer ensayo, $(n-1)/n$ para todas las pruebas hasta llegar a nuestro segundo éxito, y así sucesivamente. Así que, básicamente, tenemos $x$ geométrica de las variables aleatorias aquí, y queremos encontrar la expectativa de que su suma.

Para $i \in 1, \dots, x$, vamos a $y_i$ denotar el caso de que hemos llegado a un valor único. Debido a $y_i$ es una variable aleatoria de Bernoulli con probabilidad de éxito $p_i = (n-i+1)/n$, tenemos

\begin{align} E[\text{Number of trials}] &= \sum_{i = 1}^x E[y_i]\\ &= \sum_{i = 1}^x\frac{1}{p_i}\\ &= \sum_{i = 1}^x\frac{n}{n-i+1} \end{align}