Dados explotando en un grupo de dados

Question

Dicen que el papel $n$ idénticos, la feria de dados, cada uno con $d$ lados (cada lado viene con la misma probabilidad $\frac{1}{d}$). En cada uno de los troqueles, las caras están numeradas del $1$ $d$sin repetición de número, como era de esperar. De manera ordinaria, $d$ colindado mueren de la piscina.

Todos los dados en el resultado que se muestra que un número igual o mayor que el umbral de número de $t$ se dice que muestran un éxito. Cada morir, que muestra el resultado máximo de $d$ es hecho rodar otra vez, lo que llamamos la "explosión". Si la re-hecho rodar los dados muestran éxitos, el número de éxitos que se añade al recuento de visitas. Dados que mostrar la máxima después de volver a rodar rodar de nuevo y sus éxitos contado hasta que ninguno de mostrar un resultado máximo. Dado que los valores de

$$ d\ ...\ \text{Number of sides on each die}\ \ d>0 $$ $$ n\ ...\ \text{Number of dies rolled}\ \ n\ge 0$$ $$ h\ ...\ \text{Number of hits, we want the probability for}$$ $$ t\ ...\ \text{Threshold value for a die to roll a hit}\ \ 0 < t \le d$$

what is the probability to get exactly exactly $h$ hits? Lets call it: $$p(d,n,t,h) = p_{d,n,t,h}$$ Se puede derivar una fórmula para esta probabilidad?

Ejemplo roll:

Que rollo 7 de seis caras de los dados y el recuento de esos éxitos que mostrar un 5 o 6. En este ejemplo, $d=6$, $n=7$, $t=5$. El resultado de un rollo puede ser 6,5,1,2,3,6,1. Que de tres hits hasta el momento, pero tenemos que rodar los dos seises de nuevo (explotan). Este tiempo es 6, 2. Uno de los más afectados, y uno de los más mueren a rodar. Estamos a cuatro hits en este punto. La última morir para volver a rodar muestra 6 de nuevo, volver a rodar otra vez. En la última re-roll muestra una 4 - no más éxitos. Que da cinco hits en total y el rollo es completa. Así, por este rollo $h=5$.

Caso Simple para un solo die $n=1$:

Si somos sólo un dado con el mismo umbral como es arriba, así ($d=6$, $n=1$, $t=5$), las probabilidades se pueden calcular fácilmente:

$$ p_{6,1,5,0} = \frac{4}{6} \quad \text{(Probability for exactly 0 hits - roll 1-4 on the first roll, no explosion here)} $$ $$ p_{6,1,5,1} = \frac{1}{6} + \frac{1}{6} \cdot \frac{4}{6} \quad \text{(Probability for exactly 1 hit - roll either a 5 or a result of 1-4 after a 6)} $$ $$ p_{6,1,5,2} = \frac{1}{6} \cdot \frac{1}{6} + \frac{1}{6} \cdot \frac{1}{6} \cdot \frac{4}{6} \quad \text{(Probability for exactly 2 hits - either a 6 and 5 or two sixes and 1-4)} $$ $$ p_{d,1,t,h\ge 1} = \left(\frac{1}{d}\right)^{h-1}\frac{d-t}{d} + \left( \frac{1}{d} \right)^h \cdot \frac{t-1}{d} \quad \text{(Probability for exactly $h\ge 1$ hits - either $h-1$ maximum rolls and non-maximal success or $h$ maximum rolls and a non-success )} $$

Without Explosion:

For none-exploding dice the probability would just be binomially distributed:

$$ p^\text{non-exploding}_{d,n,t,h} = \binom{n}{h} \left( \frac{d-t+1}{d} \right)^h \left( 1 - \frac{d-t+1}{d} \right)^{n-h} $$

---

Edit1: In the mean time I found Probability of rolling $n$ successes on an open-ended/exploding dice roll. However I'm afraid, I don't fully get the answer there. E.g. the author says $s = n^k + r$, which does not hold for his examples. Also I'm not sure how to get $s$, $k$ and $r$ from my input values stated above (which are $d$, $n$, $h$ and $s$).

Edit2: If one had the probability for $b$ successes via explosions, given that the initial role had $l$ successes prior to the explosions, one could just subtract all those probabilities for all values of $b$ from the value for the pure binomial distributions with $l$ successes and add the respective value to the pure binomial probability of $b+l$ éxitos. Es solo una idea. Supongo que esto debe ser algo como una combinación de la geométrica y la distribución binomial.

Answer 1

ETA: OK, creo que he solucionado el problema. Fuera por un error...

Creo que esto se puede hacer con la generación de funciones. La generación de la función de un dado, está dada por

$$ F(z) = \frac{t-1}{d} + \frac{(d-t)z}{d} + \frac{zF(z)}{d} $$

Podemos interpretar esto como sigue: La probabilidad de que no haya golpes en el morir es $\frac{t-1}{d}$, lo $F(z)$ tiene que a medida que el coeficiente de $z^0 = 1$. La probabilidad de que exista un hit y el morir no "explotar" (repito) es $\frac{d-t}{d}$, lo $F(z)$ tiene que a medida que el coeficiente de $z^1 = z$. En el resto de $\frac{1}{d}$ de los casos, el morir explota y la situación es exactamente como era en el principio, excepto que no es un hit que ya a nuestro crédito, es por eso que contamos $zF(z)$: $F(z)$ nos lleva de vuelta al principio, por así decirlo, y la multiplicación por $z$ se ocupa de la existente éxito.

Esta expresión puede ser resuelto por $F(z)$ a través de simples álgebra para producir

$$ F(z) = \frac{t-1+(d-t)z}{d-z} $$

cuyas $z^h$ coeficiente da la probabilidad de $h$ de aciertos. Por ejemplo, para el caso sencillo en el $n = 1, d = 20, t = 11$:

\begin{align} F(z) & = \frac{10+9z}{20-z} \\ & = \frac{10+9z}{20} \left(1+\frac{z}{20}+\frac{z^2}{20^2}+\cdots\right) \\ & = \left( \frac{1}{2} + \frac{9}{20}z \right) \left(1+\frac{z}{20}+\frac{z^2}{20^2}+\cdots\right) \\ \end{align}

y, a continuación, podemos obtener la probabilidad de que no se $h$ hits de la $z^h$ coeficiente de $F(z)$

$$ P(H = h) = \frac{1}{2\cdot20^h}+\frac{9}{20^h} = \frac{19}{2\cdot20^h} \qquad h > 0 $$

con el caso especial

$$ P(H = 0) = \frac{1}{2} $$

En general, podemos obtener la expectativa de que el número de visitas $\overline{H}$

$$ \overline{H} = F'(1) = \frac{d(d-t)+t-1}{(d-1)^2} = \frac{d+1-t}{d-1} $$

---

Ahora, para $n$ dados, tenemos

$$ [F(z)]^n = \left[ \frac{t-1+(d-t)z}{d-z} \right)^n $$

Podemos escribir esto como $N(z)M(z)$, donde

\begin{align} N(z) & = [t-1+(d-t)z]^n \\ & = \sum_{k=0}^n \binom{n}{k} (t-1)^{n-k}(d-t)^kz^k \end{align}

y

\begin{align} M(z) & = \left(\frac{1}{d-z}\right)^n \\ & = \frac{1}{d^n} \left( 1+\frac{z}{d}+\frac{z^2}{d^2}+\cdots \right)^n \\ & = \sum_{j=0}^\infty \binom{n+j-1}{j} \frac{z^j}{d^{n+j}} \end{align}

por lo que podemos obtener de una forma cerrada para $P(H = h)$ de la $z^h$ coeficiente de $[F(z)]^n = N(z)M(z)$

\begin{align} P(H = h) & = \sum_{k=0}^{\max\{h, n\}} \binom{n}{k} \binom{n+h-k-1}{h-k} \frac{(t-1)^{n-k}(d-t)^k}{d^{n+h-k}} \\ & = \frac{(t-1)^n}{d^{n+h}} \sum_{k=0}^{\max\{h, n\}} \binom{n}{k} \binom{n+h-k-1}{h-k} \left[ \frac{d(d-t)}{t-1} \right]^k \end{align}

Por ejemplo, para $n = 1, d = 6, t = 5$ (en el ejemplo de la OP), la expresión anterior los rendimientos

$$ P(H = h) = \frac{5}{3 \cdot 6^h} \qquad h > 0 $$

con el caso especial

$$ P(H = 0) = \frac{2}{3} $$

lo cual coincide con las conclusiones extraídas en los comentarios a la OP.

La expectativa de que el número de visitas puede ser obtenida mediante la evaluación de las $\frac{d}{dz} [F(z)]^n$$z = 1$, pero debido a la linealidad de la expectativa, se obtiene más directa $n$ multiplicado por el número esperado de entradas para un dado, es decir,

$$ \overline{H} = \frac{n(d+1-t)}{d-1} $$

Yo creo que todo esto se verifica, pero algunos de verificación independiente (o refutación, según corresponda), sería bueno.

Answer 2

Cada morir produce un cierto número de visitas de forma independiente de la otra muere. Denotan por $p_r$ $(r\geq0)$ la probabilidad de que un determinado morir produce exactamente $r$ de aciertos. Entonces $$p_0={t-1\over d},\qquad p_1={d-t \over d}+{1\over d} p_0\ ,$$ ya que la tirada de bonificación (después de una $d$) no debe resultar en un éxito. Para $r>1$ hits necesitamos $r-1$ rollos de una $d$ y exactamente uno de los más afectados. De ello se sigue que tenemos $$p_r={1\over d^{r-1}}p_1={1\over d^r}(d-t+p_0)\qquad(r\geq1)\ .$$ Considere la posibilidad de la generación de la función $$f(x):=\sum_{r=0}^\infty p_r x^r=p_0+(d-t+p_0){x/d\over 1-x/d}=p_0{1+\alpha x \over 1-\beta x}$$ con $$\alpha:={d-t\over d p_0},\qquad \beta:={1\over d}\ .$$ La probabilidad de $p_r^{(n)}$ de la obtención de un total de $r$ de aciertos con $n\geq1$ dados es el coeficiente de $x^r$ en la expansión de $\bigl(f(x)\bigr)^n$. Ahora $$\bigl(f(x)\bigr)^n=p_0^n \sum_{j=0}^n {n\choose j}(\alpha x)^j\sum_{k=0}^\infty {n+k-1\choose k}(\beta x)^k\ .$$ Al recoger los términos de obtener $$p_r^{(n)}=p_0^n\sum_{j=0}^r C_j\>\alpha^j\beta^{r-j}$$ con cierta combinatoria coeficientes de $C_j$. No sé si una simplificación es posible.

El número esperado $E^{(n)}$ de aciertos se puede encontrar más simplemente de la siguiente manera: Vamos a $E$ ser el número esperado $E$ de éxitos que usted puede aterrizar con un solo dado. Entonces $$E={t-1\over d}\cdot 0+{d-t\over d}\cdot 1+{1\over d}(1+E)\ .$$ El razonamiento detrás de esto es la siguiente: Si los primeros resultados de la tirada es uno de $\{1,\ldots,t-1\}$ no hay ningún golpe, y el morir es muerto. Si los primeros resultados de la tirada en uno de $\{t,\ldots, d-1\}$ no es un hit, y el morir es muerto. Si el primer rollo resultados en $d$ no es un hit, y además nos da la oportunidad de darse cuenta de $E$ más éxitos con este morir.

De ello se desprende que $$E={d-t+1\over d-1}\ ,$$ a partir de la cual obtenemos $$E^{(n)}=n \>{d-t+1\over d-1}$$ cuando hay $n$ dados en el juego.

Answer 3

Fijar $d$ y $t$ y abreviar $p_{d,n,t,h}$ $p_{n,h}$. A continuación:

$$p_{n,h}=\sum_{i=0}^{h}\sum_{j=0}^{i}q_{n,i,j}p_{j,h-i}$$ where $ p_ {0,0} = 1$ y $q_{n,i,j}$ denota la probabilidad de golpes de $i$ y $j$ maximals lanzando dados de $n$.

$q_{n,i,j}$ Encontramos la expresión:

$$q_{n,i,j}=\frac{n!}{j!\left(i-j\right)!\left(n-i\right)!}\times d^{-n}\left(h-t\right)^{i-j}\left(t-1\right)^{n-i}$$