Closed form equation for win percentage of two battling armies

I was pondering a battle mechanic for a board game that is similar to, but simpler than battling armies in Risk. Consider one army of size X and a second army of size Y. The battle occurs by creating pairs of one-on-one fights where the two combatants each have 50% probability of winning. The pairs of fights continue until one army is defeated.

For Example, a 2 vs 3 battle could have the following outcomes for the first army, when the first army wins:

1. W W W
2. L W W W
3. W L W W
4. W W L W

Note that the final fight must be a win, all outcomes must have 3 wins total (the size of the second army, Y), and there cannot be more than 1 loss (the size of the first army, X, minus 1).

I'm having trouble finding a closed form equation that gives the probability of the first army winning the battle where the sizes of the armies are X and Y.

If that's easy, how about if the probability of winning the battle if an individual fight is not 50% but rather probability P?

Edit: just wanted to add a 3 vs 2 example as well:

1. W W
2. L W W
3. W L W
4. L L W W
5. L W L W
6. W L L W

Here's the 2 vs 2 case, which produces a 50% probability:

1. W W
2. L W W
3. W L W
-
Say person one on army X (denoted X1) fights person one on army Y (denoted Y1). If X1 wins, can Y1 compete anymore? – BeaumontTaz Jul 8 '14 at 6:55
@BeaumontTaz, no, if Y1 loses, that person is defeated and can no longer fight. – Ben McIntosh Jul 8 '14 at 6:57
In the 3 vs 2 case, it can have strings with a single L also, isn't it? – gar Jul 8 '14 at 7:13
@gar, yes I will make that edit, thanks. – Ben McIntosh Jul 8 '14 at 7:16
Michael was the first to actually post the answer, but thank you @BeaumontTaz for the thorough explanation. – Ben McIntosh Jul 8 '14 at 19:54

Suppose you have $n$ men and the enemy has $m$. Let $W(n,m)$ be the probability that you win. There are three rules:

$$W(n,m)=(W(n-1,m)+W(n,m-1))/2\\ W(n,0)=1\\ W(0,m)=0$$

The solution seems to be

$$W(n,m) = \frac{1}{2^{n+m-1}}\sum_{k=0}^{n-1}{n+m-1\choose k}$$

-
Well done... how did you arrive at the solution? – Ben McIntosh Jul 8 '14 at 7:30
I had a Pascal-like triangle with all $n+m=5$, for example, on the same row. The probabilities were $1,15/16,11/16,5/16,1/16,0$. I noticed that the differences between the numerators were $1,4,6,4,1$. – Michael Jul 8 '14 at 7:37

We can also derive a summation in the following manner:

When army X does not lose, there is only one way for the sequence of winning: a string of only W's, and the probability can be written as: \begin{align*} \binom{y-1}{0} p^{y} \end{align*}

where $p$ is the probability of a player of army X winning in one battle.

When army X loses once, fix the last character as W. It has one L anywhere before that and number of sequences of winning is $\binom{y-1+1}{1}$ and the corresponding probability is: \begin{align*} \binom{y-1+1}{1} p^{y} q \end{align*} where $q=1-p$ and we go on till there are $x-1$ L's. Therefore, the total probability of army X winning when there are $x$ players and army Y has $y$ players is:

\begin{align*} P(x,y) &= \sum_{i=0}^{x-1}\binom{y-1+i}{i}\, p^{y}\, q^i \end{align*}

-

Let $n$ be the size of army $X$ and $m$ be the size of army $Y$. Denote $f(n,m)$ the probability that army $X$ will win.

It's easy to see that $f(n,0)=1$ and $f(0,m)=0$.

Let's go through some examples. For the $n=m=1$ combination, we know that two outcomes could happen:

1) X wins

2) Y wins

Which is 50/50. So $f(1,1)=0.5$.

However, think of it this way:

$$f(1,1) = 0.5f(1,0) + 0.5f(0,1) = 0.5(1) + 0.5(0) = 0.5$$

This is why we think of it this way. The next case to look at is $f(2,1)$. There are at most 2 battles and a minimum of 1. (Note here that the maximum number of battles is $n+m-1$ and the minimum number of battles is $\min{(n,m)}$. See why?) The first battle has a 50% chance of x winning which would leave a remaining battle of $f(2,0)$ and a 50% chance of y winning with would leave a remaining battle of $f(1,1)$.

So,

$$f(2,1) = 0.5f(1,1) + 0.5f(2,0) = 0.5(0.5f(1,0)+0.5f(0,1))+0.5(1) = 0.5(0.5(1)+0.5(0))+0.5 = 0.5(0.5)+0.5 = 0.75$$

I'll keep updating as I come up with more. But I think this is the recurrence relationship we want to work with to come up with the closed form.

Just to explicitly state it: the relationship is:

$$f(n,m) = 0.5f(n,m-1) + 0.5f(n-1,m)$$

Expanding a few things we can show that: $$f(n,m) = \frac{1}{16}\left(f(n-4,m)+4f(n-3,m-1)+6f(n-2,m-2)+4f(n-1,m-3)+f(n,m-4)\right)$$ and in general:

$$f(n,m) = \frac{1}{2^i}\sum_{j=0}^i\dbinom{i}{j}f(n-i+j,m-j)$$

where $i$ represents the number of games played so far. We know the maximum number of games is $n+m-1$. So we can write

\begin{align}{r l}f(n,m)& = \frac{1}{2^{n+m-1}}\sum_{j=0}^{n+m-1}\dbinom{n+m-1}{j}f(n-(n+m-1)+j,m-j)\\&=\frac{1}{2^{n+m-1}}\sum_{j=0}^{n+m-1}\dbinom{n+m-1}{j}f(1+j-m,m-j)\end{align}

And for all $j\leq m-1$ we have $f(0,m-j)$ which is just 0. So we can ignore all $j$ except for those starting at $m$.

$$f(n,m)=\frac{1}{2^{n+m-1}}\sum_{j=m}^{n+m-1}\dbinom{n+m-1}{j}f(1+j-m,m-j)$$

However, it's clear that for all $j\geq m$ (what we are concerned with in the summation), we have $f(1+j-m,0)$ which is just 1. So we can drop that term.

$$f(n,m)=\frac{1}{2^{n+m-1}}\sum_{j=m}^{n+m-1}\dbinom{n+m-1}{j}$$

Lastly, so that we work with smaller numbers, we know that the combinations are symmetric, and that $\binom{n}{k} = \binom{n}{n-k}$ Which for us means we can play with the bounds on our summation to not be the latter part of the combinations, but the first part. We just have to get the right number of terms. And we are looking at the last $n+m-1-m=n-1$ terms, so we just take the first $n-1$ terms and to make notation nicer, I change back to the standard $i$ for the index.

$$f(n,m)=\frac{1}{2^{n+m-1}}\sum_{i=0}^{n-1}\dbinom{n+m-1}{i}$$

-
Well done, thank you for the clear thought process! – Ben McIntosh Jul 8 '14 at 7:31
@BenMcIntosh, I have a final answer now (and it matches with what Michael got!) Logic and methods are explained best I can. – BeaumontTaz Jul 8 '14 at 8:15

You succeed if and only if you win at least $Y$ battles out of $N = X + Y - 1$ attempts.

Indeed, if you win less than $Y$, then you lose at least $X$, and you are dead before your enemy. Conversely, if you win at least $Y$, then your enemy will be dead before you.

The number of battles won is given by the binomial distribution, so the probability of succeeding is

$$\sum_{k=Y}^{N}{N\choose k}P^k(1-P)^{N-k}$$

For large $N$, we can approximate the binomial distribution with a normal one, and thus approximate the above formula to

$$\Phi\left(\frac{PN - Y}{\sqrt{NP(1-P)}}\right)$$

-