Que tiene la mano superior en un generalizado juego de Riesgo?

Question

Así que, he jugado a un juego de Riesgo , el otro día por primera vez desde que yo era muy pequeña. Estaba frustrado al descubrir que no podía calcular (al menos en mi cabeza) si el atacante o el defensor tiene la parte superior mano en grandes batallas. Basado en cómo el juego desplegado, yo supuse que el atacante tiene la ventaja, y más tarde me lo verificó mediante el cálculo del número esperado de muertes en una ronda de "combate". Pero, mi enfoque era sólo por fuerza bruta el cálculo en una hoja de cálculo. Tengo la curiosidad de si existe un enfoque más elegante y también pensé que podría ser bueno para pedir una pregunta más general.

Deje $A$ $B$ dos jugadores. Deje $a,b,n,k$ ser enteros positivos con $k \leq a,b$. El juego es la siguiente. Persona $A$ $a$ dados. Persona $B$ $b$ dados. Todos los dados tienen $n$ lados etiquetados $1,2,\ldots,n$. Ambos jugadores tiran todos sus dados, extracto de su $k$ más alto de los rollos (con repetición) y ordenarlos en (débilmente) orden decreciente. Decir $a_1,\ldots,a_k$ $A$'s $k$ mejor rollos y $b_1,\ldots,b_k$ $B$'s $k$ mejor de los rollos. $A$ sufre una "víctima" para cada índice $i \in \{1,2,\ldots,k\}$ con $a_i \leq b_i$. $B$ sufre una "víctima" para cada índice $i \in \{1,2,\ldots,k\}$$a_i > b_i$. Tenga en cuenta que el reproductor de $B$ gana cuando los rollos están atadas.

Lo que se espera que el número de casulties que $A$ sufre en términos de $a,b,n,k$? Nota de la linealidad de las expectativas, se espera que el número de víctimas que $A$ sufre más el número esperado de víctimas que $B$ sufre suma a $k$.

Answer 1

Para un juego de Riesgo, donde el atacante tiene 3 ejércitos y el defensor tiene 2, me funcionó de esta manera. Creo que se puede generalizar fácilmente para otros valores de $a$$n$. Otros valores de $b$, el contar un poco más difícil, pero aún dentro de alcance (creo). Otros valores de $k$, sin embargo, hacer que mi método de recuento mucho más difícil (creo).

Si consideramos los tres dados del atacante como se distinguen, entonces el espacio de lo posible rollos para el atacante tiene el tamaño de $6^3$. Es como un gigantesco $6\times6\times6$ cubo en sí - una dimensión para cada uno de los troqueles. Por ejemplo, el atacante del rollo puede ser un $(2,5,4)$ o $(4,6,6)$. Cada rollo tiene la misma probabilidad: $\frac{1}{6^3}$.

Podemos romper este cubo en conchas que voy a tratar de definir. El más pequeño de cáscara contiene el singleton $(1,1,1)$. El siguiente shell contiene todas las tiradas posibles, donde el alto morir es un 2. (Este shell, por tanto, ha $7$ elementos que rodean $(1,1,1)$.) Continuar de esta manera hasta la capa externa, la cual contendrá todas las tiradas posibles donde la mayor morir es un 6. Geométricamente, este último shell es de tres caras del cubo. Cada uno de los anteriores shell también puede ser visto como el que tiene tres caras (con la posible excepción de $S_1$.) Para ser más precisos, $$S_i = \{(a,b,c)|\max\{a,b,c\}=i\}$$ para $i =1\ldots6$. La probabilidad de lanzar en shell $i$ $$P(S_i)=\frac{i^3-(i-1)^3}{6^3}$$ Cada shell $S_i$ ha subconjuntos $S_{i,j}$ donde $j$ es el segundo más alto del rollo (posiblemente igual a $i$). Geométricamente, $S_{i,j}$ se compone de segmentos de línea que se ejecuta a lo largo de las tres caras de $S_i$. $S_{i,i}$ se compone de las tres aristas que convergen a la principal esquina en $S_i$. Para $j$ menos que $i$, $S_{i,j}$ se compone de tres "flechas", una en cada cara de $S_i$, cada una apuntando a la principal esquina de $S_i$. La siguiente imagen ilustra el cubo de la posible atacante rollos, $S_6$, $S_{6,6}$, y $S_{6,3}$.

Encontramos que para el atacante del rollo, con $j$ menos de $i$, \begin{align*} P(S_{i,i}) & = \frac{3i-2}{i^3-(i-1)^3}\frac{i^3-(i-1)^3}{6^3}=\frac{3i-2}{6^3}\\ P(S_{i,j}) & = \frac{6j-3}{i^3-(i-1)^3}\frac{i^3-(i-1)^3}{6^3}=\frac{6j-3}{6^3}\ \end{align*}

Ahora empezamos a considerar la posibilidad de que el defensor de la tira, condicionado a lo $S_{i,j}$ el atacante ha rodado en. Similar al cubo que se prevé para el atacante, el defensor tiene un $6\times 6$ plaza de tiradas posibles.

Vamos a empezar a contar el número de ejércitos que el atacante pierde. Deje $X$ ser esta variable aleatoria, que puede tomar los valores $0$, $1$, o $2$.

Supongamos que el atacante ha rodado en $S_{i,i}$. Si el defensor de los dados son menos de $i$ (lo que ocurrirá con $P=\frac{(i-1)^2}{6^2}$), el atacante se perderá cero ejércitos. Si el defensor de dados se $\geq i$ (lo que ocurrirá con $P=\frac{(7-i)^2}{6^2}$) que el atacante se perderá dos ejércitos. En todas las demás situaciones ($P=\frac{2(i-1)(7-i)}{6^2}$), cada jugador pierde un ejército.

Ahora supongamos que el atacante ha rodado en $S_{i,j}$$j<i$. El atacante pierde ninguna ejércitos si el defensor más alto de morir es menos de $i$ y el otro dado es menor que $j$. Esto define una forma de "L" de la región de la defensa de la plaza de posibilidades. Esta región ha $P=\frac{(i-1)^2-(i-j)^2}{6^2}$. Del mismo modo, el atacante se perderá dos ejércitos exactamente cuando el defensor tiene su alta mueren al menos $i$ y otros mueren al menos $j$. Esto define una forma de "L" de la región en el otro lado de la plaza. ($P=\frac{(7-j)^2-(i-j)^2}{6^2}$). Esto deja tres regiones rectangulares en la plaza donde cada jugador pierde un ejército ($P=\frac{2(j-1)(7-i)+(i-j)^2}{6^2}$).

En total, ahora, las probabilidades para cada valor de $X$ se puede calcular a través de la suma: \begin{align*} P(X=0)&=\sum_{i=1}^6\left(P(S_{i,i})\frac{(i-1)^2}{6^2}+\sum_{j=1}^{i-1}P(S_{i,j})\frac{(i-1)^2-(i-j)^2}{6^2}\right)\\ &=\sum_{i=1}^6\left(\frac{3i-2}{6^3}\frac{(i-1)^2}{6^2}+\sum_{j=1}^{i-1}\frac{6j-3}{6^3}\frac{(i-1)^2-(i-j)^2}{6^2}\right)\\ P(X=1)&=\sum_{i=1}^6\left(P(S_{i,i})\frac{2(i-1)(7-i)}{6^2}+\sum_{j=1}^{i-1}P(S_{i,j})\frac{2(j-1)(7-i)+(i-j)^2}{6^2}\right)\\ &=\sum_{i=1}^6\left(\frac{3i-2}{6^3}\frac{2(i-1)(7-i)}{6^2}+\sum_{j=1}^{i-1}\frac{6j-3}{6^3}\frac{2(j-1)(7-i)+(i-j)^2}{6^2}\right)\\ P(X=2)&=\sum_{i=1}^6\left(P(S_{i,i})\frac{(7-i)^2}{6^2}+\sum_{j=1}^{i-1}P(S_{i,j})\frac{(7-j)^2-(i-j)^2}{6^2}\right)\\ &=\sum_{i=1}^6\left(\frac{3i-2}{6^3}\frac{(7-i)^2}{6^2}+\sum_{j=1}^{i-1}\frac{6j-3}{6^3}\frac{(7-j)^2-(i-j)^2}{6^2}\right)\\ \end{align*}

Cada uno de estos puede ser reducido mediante la suma de las fórmulas de \begin{align*} \sum_{n=1}^m\ 1& =m\\ \sum_{n=1}^m\ n&=\frac{1}{2}m(m+1)\\ \sum_{n=1}^m\ n^2&=\frac{1}{6}m(m+1)(2m+1)\\ \sum_{n=1}^m\ n^3&=\frac{1}{4}m^2(m+1)^2\\ \sum_{n=1}^m\ n^4&=\frac{1}{30}m(m+1)(2m+1)(3m^2+3m-1) \end{align*}

Después de la aplicación de estos, podemos encontrar: \begin{align*} P(X=0)&=\frac{2890}{6^5}\\ P(X=1)&=\frac{2611}{6^5}\\ P(X=2)&=\frac{2275}{6^5} \end{align*}

Estas de acuerdo con el decimal probabilidades informó aquí. Así, el número esperado de víctimas es $$0\frac{2890}{6^5}+1\frac{2611}{6^5}+2\frac{2275}{6^5}=\frac{7161}{6^5}$$

Answer 2

He aquí una respuesta. No es muy bonito, pero es exacto. Deje que la variable aleatoria $C_A$ denotar el número de Jugador de $A$ (el atacante)'s bajas. Entonces

$\begin{align} E[C_A] = &\sum_{j=0}^{k-1} \sum_{i=1}^n \sum_{l=0}^j \sum_{m=0}^j \binom{b}{l} \binom{a}{m} \left( \left(1 - \frac{i}{n}\right)^l \left( \frac{i}{n}\right)^{b-l} - \left(1- \frac{i-1}{n}\right)^l \left(\frac{i-1}{n}\right)^{b-l} \right) \\ & \times \left(1 - \frac{i}{n}\right)^m \left(\frac{i}{n}\right)^{a-m}. \end{align} $

Derivation:

In a particular random roll of the dice, we order $$'s dice from largest to smallest and $B$'s dice from largest to smallest. This is equivalent to taking two random samples - of size $$ in $$'s case and size $b$ in $B$'s case - from the discrete uniform distribution on $\{1, 2, \ldots, n\}$ and computing their order statistics.

If $X_{(j)}$ and $Y_{(j)}$ denote the order statistics from $$'s dice rolls and from $B$'s dice rolls, respectively, then $$ suffers a casualty each time $X_{(a-j)} \leq Y_{(b-j)}$, for $0 \leq j \leq k-1$. Let $I_j$ be $1$ if $X_{(a-j)} \leq Y_{(b-j)}$, and $0$ otherwise. Then $C_A = \sum_{j=0}^{k-1} I_j$, and so $$E[C_A] = \sum_{j=0}^{k-1} E[I_j] = \sum_{j=0}^{k-1} P(X_{(a-j)} \leq Y_{(b-j)}).$$

Since $Un$'s rolls and $B$'s rolls are independent, so are their order statistics. Conditioning on the value of $Y_{(b-j)}$, then, we have $P(X_{(a-j)} \leq Y_{(b-j)}) = \sum_{i=1}^n P(Y_{(b-j)} = i) P(X_{(a-j)} \leq i).$ There are known formulas for $P(Y_{(b-j)} = i)$ and $P(X_{(a-j)} \leq i)$: $$P(Y_{(b-j)} = i) = \sum_{l=0}^j \binom{b}{l} \left( \left(1 - \frac{i}{n}\right)^l \left( \frac{i}{n}\right)^{b-l} - \left(1- \frac{i-1}{n}\right)^l \left(\frac{i-1}{n}\right)^{b-l} \right),$$ $$P(X_{(a-j)} \leq i) = \sum_{m=0}^j \binom{a}{m} \left(1 - \frac{i}{n}\right)^m \left(\frac{i}{n}\right)^{a-m}.$$

Putting this all together, we obtain

$\begin{align} E[C_A] = &\sum_{j=0}^{k-1} \sum_{i=1}^n \sum_{l=0}^j \sum_{m=0}^j \binom{b}{l} \binom{a}{m} \left( \left(1 - \frac{i}{n}\right)^l \left( \frac{i}{n}\right)^{b-l} - \left(1- \frac{i-1}{n}\right)^l \left(\frac{i-1}{n}\right)^{b-l} \right) \\ & \times \left(1 - \frac{i}{n}\right)^m \left(\frac{i}{n}\right)^{a-m}. \end{align} $

A comment on implementation:

For simplicity, the formula uses the convention that $0^0 = 1$, which occurs when $i = n$. If you try to use the formula in some computer algebra system that doesn't have that convention, like Mathematica, you will need to consider the case $i = n$ separately from the rest of the sum on $i$. This would be

$\begin{align} E[C_A] = &\sum_{j=0}^{k-1} \Bigg(\sum_{i=1}^{n-1} \sum_{l=0}^j \sum_{m=0}^j \binom{b}{l} \binom{a}{m} \left( \left(1 - \frac{i}{n}\right)^l \left( \frac{i}{n}\right)^{b-l} - \left(1- \frac{i-1}{n}\right)^l \left(\frac{i-1}{n}\right)^{b-l} \right) \\ & \times \left(1 - \frac{i}{n}\right)^m \left(\frac{i}{n}\right)^{a-m} + \left(1-\sum_{l=0}^j \binom{b}{l}\left(1-\frac{n-1}{n}\right)^l \left(\frac{n-1}{n}\right)^{b-l}\right) \Bigg). \end{align} $

Example:

In the case of standard Risk, with $n = 6, a = 3, b = 2, k = 2$ case, the formula yields $\frac{2387}{2592} = \frac{7161}{6^5}$, de acuerdo con alex.la respuesta de jordan.

In[1]:= f[n_, a_, b_, k_] := 
  Sum[Sum[Binomial[b, l]*((1 - i/n)^l*(i/n)^(b - l) - (1 - (i - 1)/n)^l*
        ((i - 1)/n)^(b - l))*Binomial[a, m]*(1 - i/n)^m*(i/n)^(a - m), 
     {i, 1, n - 1}, {l, 0, j}, {m, 0, j}] + 
    (1 - Sum[Binomial[b, l]*(1 - (n - 1)/n)^l*((n - 1)/n)^(b - l), {l, 0, j}]), 
   {j, 0, k - 1}]

In[2]:= f[6, 3, 2, 2]
Out[2]= 2387/2592

In[3]:= N[%]
Out[3]= 0.9209104938271605

In[4]:= N[7161/6^5]
Out[4]= 0.9209104938271605