Una pregunta básica de combinatoria/probabilidad

Question

Suponga que tiene un conjunto $A = \{1, 2, 3, 4, 5, 6, 7\}$ .

Se hace un muestreo con reemplazo sobre A (uniformemente al azar), y se obtiene un multiconjunto/bolsa $B$ de tamaño $5$ . Por ejemplo, B podría ser $\{2, 3, 4, 5, 6\}$ o $\{2, 2, 3, 3, 4\}$ .

Entonces, ¿cuál es la probabilidad de que haya al menos $3$ elementos distintos en $B$ ?

En general, si tiene $A = \{1, 2, 3, ..., n\}$ se hace un muestreo con reemplazo sobre $A$ y conseguir un multiset/bolsa $B$ de tamaño $k$ ¿cuál es la probabilidad de que haya al menos m elementos distintos en B? (suponiendo que $n > k > m$ ).

Answer 1

Es más fácil hacer el cálculo de que hay exactamente $m$ cubos con al menos una bola. $k$ no tiene por qué ser inferior a $n$ .

Tiene una recurrencia con $P(n,k,m)=\frac{n-m+1}{n}P(n,k-1,m-1)+\frac{m}{n}P(n,k-1,m)$ a partir de $P(n,0,0)=1$ .

Así que para su ejemplo con $n=7$ se obtiene algo así, con cada columna sumando a $1$ .

n=7     k:  0       1       2       3       4       5       6       7       8
m:                                      
0       1.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000
1       0.000   1.000   0.143   0.020   0.003   0.000   0.000   0.000   0.000
2       0.000   0.000   0.857   0.367   0.122   0.037   0.011   0.003   0.001
3       0.000   0.000   0.000   0.612   0.525   0.312   0.161   0.077   0.035
4       0.000   0.000   0.000   0.000   0.350   0.500   0.464   0.357   0.248
5       0.000   0.000   0.000   0.000   0.000   0.150   0.321   0.428   0.459
6       0.000   0.000   0.000   0.000   0.000   0.000   0.043   0.129   0.233
7       0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.006   0.024

Así que para $k=5$ basta con sumar las cifras adecuadas en la columna correspondiente para obtener una respuesta de aproximadamente $0.962099\ldots$