Probabilidad de que exactamente y de n tiradas de un dado de r caras sean únicas

Question

Considere un $r$ -un dado que se tira por un lado $n$ tiempos. ¿Cuál es la probabilidad de que de los $n$ rueda exactamente $y$ de los rollos son únicos?

Por ejemplo, considere $n = 2$ y $r = 3$ . Las posibilidades son

0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2

En este caso, $P(y = 0) = 1/3$ , $P(y = 1) = 0$ y $P(y = 2) = 2/3.$

Me parece que esto debería ser un problema bastante sencillo de resolver, pero por mi vida no he podido resolverlo (necesito esta información para acotar el comportamiento de un algoritmo en el que estoy trabajando).

Answer 1

Hay una forma eficiente y sencilla, $O(n)$ solución.

Al expandir el polinomio

$$f_{n,r} = \left(x_1+x_2+\cdots+x_r\right)^n = \sum_{i_1,i_2,\ldots,i_r} \binom{n}{i_1,i_2,\ldots,i_r} x_1^{i_1}x_2^{i_2}\cdots x_r^{i_r},$$

para cada uno de los $\binom{r}{y}$ subconjuntos de $y$ de las variables habrá un término como este

$$\binom{n}{1,1,\ldots,1,i_{y+1},\ldots, i_r}\left(x_1x_2\cdots x_y\ x_{y+1}^{i_{y+1}}\cdots x_r^{i_r}\right)$$

cuyo coeficiente da el número de veces al menos $y$ de las variables aparecen una sola vez. Este coeficiente se puede encontrar diferenciando $f_{n,r}$ con respecto a cada uno de esos $y$ variables, estableciendo los valores de esas variables a $0$ y estableciendo los valores de los restantes $r-y$ variables a $1$ porque

$$\frac{\partial^y}{\partial x_1\partial x_2\cdots \partial x_y}\left(x_1x_2\cdots x_y\ x_{y+1}^{i_{y+1}}\cdots x_r^{i_r}\right) = x_{y+1}^{i_{y+1}}\cdots x_r^{i_r}$$

evalúa a $1$ y todos los demás términos tienen al menos uno de los primeros $y$ variables como un factor, de ahí que evalúen a $0$ .

Calculando esta derivada para la expresión original de $f_{n,r}$ produce (utilizando el factorial descendente notación para el coeficiente)

$$\eqalign{&\frac{\partial^y}{\partial x_1\partial x_2\cdots \partial x_y} \left(x_1+x_2+\cdots+x_r\right)^n \\&= n(n-1)\cdots(n-y+1)\left(x_1+x_2+\cdots+x_r\right)^{n-y} \\ &= n_{(y)}\left(x_1+x_2+\cdots+x_r\right)^{n-y}. }$$

Cuando $y$ de la $x_i$ igual $0$ y el resto $r-y$ igual $1$ el lado derecho se evalúa como

$$ n_{(y)}(r-y)^{n-y}.$$

Multiplicando por $\binom{r}{y}$ para tener en cuenta todas las combinaciones posibles de $y$ variables y aplicando el Principio de inclusión exclusión ("PIE") produce el número de veces $y$ las variables aparecen exactamente una vez, que es

$$\binom{r}{y}\sum_{j=y}^{\min(r,n)} (-1)^{j-y} (r-j)^{n-j} n_{(j)}\binom{r-y}{j-y}.$$

Dividiendo esto por $r^n$ da las probabilidades asociadas. El esfuerzo computacional es $O(\min(r,n)-y)$ .

¡Nada es gratis! Como en la mayoría de las aplicaciones de la PIE, se trata de una suma alternada de términos que pueden variar radicalmente de tamaño, siendo el resultado final mucho menor que los términos más grandes. Puede haber una pérdida catastrófica de precisión, por lo que se necesita aritmética de alta precisión (o, mejor aún, racional exacta). Con eso disponible, la implementación es notablemente corta. Aquí está en Mathematica :

p[n_, k_] := n^k; p[n_, 0] := 1;
f[n_, d_, k_] := Binomial[d,k]  
            Sum[(-1)^(j-k) Binomial[d-k,j-k] FactorialPower[n,j] p[d-j,n-j],{j,k,Min[d,n]}]

Como ejemplo, vamos a trazar la distribución completa para un $n$ y $r$ :

With[{n = 100, r = 100}, DiscretePlot[f[n, r, y]/r^n, {y, 0, Min[n, r]}]]

---

Como ejemplo, consideremos el caso $n=4$ , $r=3$ y los valores de $y$ de $0$ a través de $3$ . La expansión de $f_{4,3}$ es

$$x_1^4+x_2^4+x_3^4 \\\color{blue}{+4 x_2 x_1^3+4 x_3 x_1^3+4 x_1 x_2^3+4 x_3x_2^3+4 x_1 x_3^3+4 x_2x_3^3}\\+6 x_2^2 x_1^2+6 x_2^2 x_3^2+6 x_3^2 x_1^2\\\color{red}{+12 x_1 x_2 x_3^2 +12 x_1 x_2^2 x_3 +12 x_1^2 x_2 x_3}.$$

Considere el cálculo para $y=1$ .

• Los términos con exactamente una $x_1$ en ellos son

  $$\color{blue}{4 x_1 x_2^3+4 x_1 x_3^3}+\color{red}{12 x_1 x_2 x_3^2 +12 x_1 x_2^2 x_3}.$$

  Estos coeficientes suman $4+4+12+12=32$ . Así, estimaríamos el número total de términos con una sola de las $x_i$ sería $3\times 32=96$ .

• Todavía no hemos terminado. Los términos con una $x_1$ y otro $x_i$ en ellos son

  $$\color{red}{12 x_1 x_2 x_3^2 + 12 x_1 x_2^2 x_3}.$$

  Esto nos dice que cuando contamos el $x_1$ términos anteriores, hemos contado de más por $12+12 = 24$ . Por lo tanto, el sobreconteo total es $3\times 24 = 72$ .

• Nosotros son hecho ahora, porque no hay términos posibles con exactamente una instancia de tres lados.

En consecuencia, el recuento de $y=1$ es

$$96 - 72 + 0 = 24.$$

En efecto, se trata de la suma de los coeficientes de

$$\color{blue}{4 x_2 x_1^3+4 x_3 x_1^3+4 x_1 x_2^3+4 x_3x_2^3+4 x_1 x_3^3+4 x_2x_3^3}.$$

Answer 2

Definir $F(n, k)$ para ser el número de formas de asignar $k$ opciones para $n$ de manera que cada opción aparezca como 0 o como $\geq 2$ tiempos. Entonces la probabilidad de que veas exactamente $y$ valores únicos cuando se tira un $k$ -dados de lado $n$ tiempos es:

$$ Pr(Y=y) = \frac{{k\choose y}{n\choose y}y!F(n-y, k-y)}{k^n} $$

Básicamente, hay ${k \choose y}$ formas de seleccionar el $y$ opciones únicas de todos $k$ opciones, ${n\choose y}$ formas de seleccionar el $y$ rollos para estas opciones únicas, y $y!$ ordenamientos de la $y$ opciones dentro de estos rollos.

Lo único que queda es calcular $F(n, k)$ . Hay algunos casos sencillos y luego una definición recursiva:

\begin {align*} F(0, k) &= 1 & \forall ~k \geq 0 \\ F(1, k) &= 0 & \forall ~k \geq 0 \\ F(n, 0) &= 0 & \forall ~n \geq 1 \\ F(n, k) &= F(n, k-1) + \sum_ {i=2}^n {n \choose i}F(n-i, k-1) & \forall ~n \geq 2, k \geq 1 \end {align*}

El paso recursivo selecciona una opción arbitraria y considera por separado el número de asignaciones para las que aparece $0, 2, 3, \ldots, n$ tiempos. Esta formulación permite el cálculo de todo el pmf en $O(n^2k)$ lo que debería ser mucho más eficiente que sumar sobre todas las particiones válidas de la distribución multinomial. Aquí hay una implementación en R:

uniquePMF <- function(n, k) {
  F <- matrix(0, nrow=n+1, ncol=k+1)
  F[1,] <- 1
  for (.k in 1:k) {
    for (.n in 2:n) {
      F[.n+1,.k+1] <- F[.n+1,.k] + sum(choose(.n, 2:.n)*F[.n-(2:.n)+1,.k])
    }
  }
  out <- sapply(0:min(n, k), function(y) choose(k, y)*choose(n, y)*factorial(y)*F[n-y+1,k-y+1]) / k^n
  names(out) <- 0:min(n, k)
  out
}

Esto devuelve los resultados calculados a mano para el $n=2, k=3$ caso:

uniquePMF(2, 3)
#         0         1         2 
# 0.3333333 0.0000000 0.6666667

También puede manejar cómodamente instancias más grandes (aquí $n=k=100$ ):

plot(0:100, uniquePMF(100, 100), xlab="y", ylab="Pr(Y=y)")

Answer 3

Se trata básicamente de un problema generalizado de cobro de cupones. No creo que vayas a encontrar una solución fácil de forma cerrada para él. En general, la distribución de lanzamientos de dados es multinomial:

$$\binom{n}{a_1,a_2,\cdots,a_r}(1/r)^n,$$

donde $a_i$ representa el número de veces $i$ se enrolla, y $a_1+\cdots+a_r=n$ . Entonces la respuesta es:

$$(1/r)^n\sum\binom{n}{a_1,a_2,\cdots,a_r},$$

donde la suma es sobre todas las combinaciones de $a_i$ tal que exactamente $y$ de ellos son distintos de cero. Es decir, estás viendo todas las particiones de $n=a_1+\cdots+a_r$ tal que exactamente $y$ son distintos de cero. Se puede utilizar alguna simetría para simplificar esto aún más, simplemente sumando sobre todas las combinaciones de $n=a_1+\cdots+a_y$ con $a_i>0$ para $i=1,2,\cdots,y$ y $a_i=0$ para $i>y$ y, a continuación, contabilizar su multiplicidad mediante $\binom{n}{a_1}\binom{n-a_1}{a_2}\cdots$ .