Intereting Posts

How to reverse digits of an integer mathematically?
Prove that in a Noetherian ring, no invertible maximal ideal properly contains a nonzero prime ideal
The boundary of an $n$-manifold is an $n-1$-manifold
Minimality in the case of partial derivatives and Sobolev spaces?
proof of the chain rule for calculus
Evaluating a triple integral
Proving the Möbius formula for cyclotomic polynomials
Cardinality of the union of infinite and countable sets
The inegral $\int_1^2 2x \sqrt{x^2 + 1}\; dx$ using differential forms
What is the number of automorphisms (including identity) for permutation group $S_3$ on 3 letters?
Show that for any odd $n$ it follows that $n^2 \equiv 1 \mod 8$ and for uneven primes $p\neq 3$ we have $p^2 \equiv 1\mod 24$.
Proving that two systems of linear equations are equivalent if they have the same solutions
What is a Primitive Atomic Formula?
Determining the Smith Normal Form
If $f \circ g$ is onto then $f$ is onto and if $f \circ g$ is one-to-one then $g$ is one-to-one

So, I played a game of Risk the other day for the first time since I was very little. I was frustrated to discover that I couldn’t compute (at least not in my head) whether the attacker or the defender has the upper-hand in large battles. Based on how the game unfolded, I guessed that the attacker has the advantage, and later I verified this by calculating the expected number of casualties in a round of “combat”. But, my approach was just to brute-force the computation in a spreadsheet. I’m curious whether there is a more elegant approach and also I thought it might be nice to ask a more general question.

Let $A$ and $B$ be two players. Let $a,b,n,k$ be positive integers with $k \leq a,b$. The game is as follows. Person $A$ has $a$ dice. Person $B$ has $b$ dice. All dice have $n$ sides labelled $1,2,\ldots,n$. Both players roll all of their dice, extract their $k$ highest rolls (with repetition) and sort them in (weakly) decreasing order. Say $a_1,\ldots,a_k$ are $A$’s $k$ best rolls and $b_1,\ldots,b_k$ are $B$’s $k$ best rolls. $A$ suffers one “casualty” for each index $i \in \{1,2,\ldots,k\}$ with $a_i \leq b_i$. $B$ suffers one “casualty” for each index $i \in \{1,2,\ldots,k\}$ with $a_i > b_i$. Note that player $B$ wins when the rolls are tied.

What are the expected number casulties that $A$ suffers in terms of $a,b,n,k$? Note by linearity of expectation, the expected number of casualties that $A$ suffers plus the expected number of casualties that $B$ suffers sum to $k$.

- How to solve $\int_0^\infty J_0(x)\ \text{sinc}(\pi\,x)\ e^{-x}\,\mathrm dx$?
- Challenging identity regarding Bell polynomials
- Show that $e^{-\beta} = \frac{1}{\sqrt{\pi}} \int_{0}^{\infty} \frac{e^{-u}}{\sqrt{u}} e^{-\beta^2 / 4u} du$.
- Integral ${\large\int}_0^1\left(-\frac{\operatorname{li} x}x\right)^adx$
- Finite Sum $\sum\limits_{k=1}^{m-1}\frac{1}{\sin^2\frac{k\pi}{m}}$
- About the closed form for $\lim_{y\to +\infty}\left(-\frac{2}{\pi}\log(1+y)+\int_{0}^{y}\frac{|\cos x\,|}{1+x}\,dx\right)$

- Find values for probability density function
- Is statistical dependence transitive?
- Conditional expectation on Gaussian random variables
- Prove $\int_0^1 \frac{4\cos^{-1}x}{\sqrt{2x-x^2}}\,dx=\frac{8}{9\sqrt{\pi}}\left(9\Gamma(3/4)^2{}_4F_3(\cdots)+\Gamma(5/4)^2{}_4F_3(\cdots)\right)$
- The probability of an ace from a 5-card hand?
- Uncorrelated, Non Independent Random variables
- Probability of spherical particles touching one another in a cylindrical column
- Infinite Series $\sum\limits_{n=0}^\infty\frac{(-1)^n}{(2n+1)^{2m+1}}$
- iid and correlated order statistics a comparison
- The average time for a spider to reach the top of a cliff

For an actual game of Risk, where the attacker has 3 armies and the defender has 2, I worked it out this way. I think you can generalize easily for other values of $a$ and $n$. Other values of $b$ will make the counting slightly more difficult, but still within reach (I think). Other values of $k$ however will make my counting method a lot more difficult (I think).

If we view the three attacker’s dice as distinguished, then the space of possible rolls for the attacker has size $6^3$. It’s like a giant $6\times6\times6$ cube itself – one dimension for each die. For example, the attacker’s roll might be a $(2,5,4)$ or a $(4,6,6)$. Each such roll has the same probability: $\frac{1}{6^3}$.

We can break this cube into shells that I will try to define. The smallest shell contains the singleton $(1,1,1)$. The next shell contains all possible rolls where the high die is a 2. (This shell therefore has $7$ elements – surrounding $(1,1,1)$.) Continue in this way up to the outermost shell, which will contain all possible rolls where the highest die is a 6. Geometrically, this last shell is three faces of the cube. Each previous shell can also be viewed as having three faces (with the possible exception of $S_1$.) To be more precise,

$$S_i = \{(a,b,c)|\max\{a,b,c\}=i\}$$

for $i =1\ldots6$.

The probability of tossing into shell $i$ is $$P(S_i)=\frac{i^3-(i-1)^3}{6^3}$$

Each shell $S_i$ has subsets $S_{i,j}$ where $j$ is the second highest roll (possibly equal to $i$). Geometrically, $S_{i,j}$ is composed of line segments running along the three faces of $S_i$. $S_{i,i}$ is composed of the three edges converging to the main corner in $S_i$. For $j$ less than $i$, $S_{i,j}$ is composed of three “arrows”, one along each face of $S_i$, each pointing to the main corner of $S_i$. The image below illustrates the cube of possilbe attacker rolls, $S_6$, $S_{6,6}$, and $S_{6,3}$.

We find that for the attacker’s roll, with $j$ less than $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*}

Now we begin to consider the defender’s tosses, conditional upon what $S_{i,j}$ the attacker has rolled into. Similar to the cube that we envisioned for the attacker, the defender has a $6\times 6$ square of possible rolls.

Let’s start counting the number of armies that the attacker loses. Let $X$ be this random variable, which can take values $0$, $1$, or $2$.

Suppose the attacker has rolled into $S_{i,i}$. If both the defender’s dice are less than $i$ (which will happen with $P=\frac{(i-1)^2}{6^2}$), the attacker will lose zero armies. If both of the defender’s dice are $\geq i$ (which will happen with $P=\frac{(7-i)^2}{6^2}$) the attacker will lose two armies. In all other situations ($P=\frac{2(i-1)(7-i)}{6^2}$), each player loses one army.

Now suppose that the attacker has rolled into $S_{i,j}$ with $j<i$. The attacker loses no armies if the defender’s highest die is less than $i$ and the other die is less than $j$. This defines an “L” shaped region of the defender’s square of possibilities. This region has $P=\frac{(i-1)^2-(i-j)^2}{6^2}$. Similarly, the attacker will lose two armies exactly when the defender has his high die at least $i$ and other die at least $j$. This defines an “L” shaped region on the other side of the square. ($P=\frac{(7-j)^2-(i-j)^2}{6^2}$). This leaves three rectangular regions on the square where each player loses one army ($P=\frac{2(j-1)(7-i)+(i-j)^2}{6^2}$).

Altogether now, the probabilities for each value of $X$ can be compute via summation:

\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*}

Each of these can be reduced using the sum formulas

\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*}

After applying these, we find:

\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*}

These agree with the decimal probabilities reported here. Thus the expected number of casualties is $$0\frac{2890}{6^5}+1\frac{2611}{6^5}+2\frac{2275}{6^5}=\frac{7161}{6^5}$$

Here’s an answer. It’s not very pretty, but it is exact. Let the random variable $C_A$ denote the number of Player $A$ (the attacker)’s casualties. Then

$\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 $A$’s dice from largest to smallest and $B$’s dice from largest to smallest. This is equivalent to taking two random samples – of size $a$ in $A$’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 $A$’s dice rolls and from $B$’s dice rolls, respectively, then $A$ 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 $A$’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}$, in agreement with alex.jordan’s answer.

```
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
```

- Does Nakayama Lemma imply Cayley-Hamilton Theorem?
- Machin's formula and cousins
- Solution of Wave Equation using Reflection Principle
- How to show that $1,\alpha,\alpha^2/2$ is an integral basis of $R=\mathcal{O}\cap \mathbb{Q}$
- Existence of real roots of a quartic polynomial
- If every ideal is principal show the same is true for the image of a homomorphism.
- Showing that $X_{1:n}$ is sufficient for $\eta$, by factorization
- If $n$ vectors are linearly independent, is there only one way to write a vector as a linear combination of those vectors?
- How many valid paths are there?(counting problem)
- Fitting of Closed Curve in the Polar Coordinate.
- Find a formula in terms of k for the entries of Ak, where A is the diagonalizable matrix:
- Prove Cardinality of Power set of $\mathbb{N}$, i.e $P(\mathbb{N})$ and set of infinite sequences of $0$s & $1$s is equal.
- When does a polynomial in $GF$ have a multiplicative inverse?
- If $\omega$-chains corresponds to maximality, then $\kappa$-chains corresponds to ???
- Graph of morphism , reduced scheme.