Game probability problem

[BGM]

From the previous calculations you know how to calculate the probability mass function of the number of attackers survived after a battle. Then you just need to exhaust all the possible paths (remember the reduction of 1 army through the next battle).

Say you want to calculate the probability of winning all 3 battles. So first you calculate the probability mass function of the number of attackers entering the final battle. To do this you also need to consider the number of armies entering the second battle - essentially you are listing all the paths. By independence each path probability is just the product.

E.g. Initially the number of attackers is \( 5 \).

You can calculate the probability of winning with \( 3 \) armies entering the final. Such scenario occur when you win first two battles without any losses, i.e. \( 5 \to 5, 4 \to 4 \). Next you calculate with \( 2 \) only. The possible paths are \( 5 \to 4, 3 \to 3 \) and \( 5 \to 5, 4 \to 3 \) . Similarly you can calculate all these and sum them up to obtain the desired probability.

 

[GameGod]

So from that I've tried to come up with a function which represents what we're doing. Can you confirm if it is correct? (it is in the attached PDF)

\(R_A\) is the number of attackers remaining after the battle, given that it started with \((A,D)\) attackers and defenders respectively. This is thus the expectation, to be calculated with the method shown from our previous posts.

 

[GameGod]

Hi, can you tell me whether the above solution is correct or not?

And I have a further question - how can we work out the expected number of attackers remaining, \(R_{A overall}\), after the whole campaign? (Or the probability that there will be a certain number, \(R_{A overall}\), of attackers remaining after my last battle which will thus be the number to occupy the final territory \(T_n\).)

 

[BGM]

I am just too lazy to check the formula lol, but I think the general framework is correct - in the iterative summation, the upper bound of the inner summation (representing the maximum number of attacker survived in the next battle) is reduced by the losses in the previous battle, so the bound will be dependent to the dummy variable of the outer summation.

For the expectation I think is very easy - actually you have all the probabilities of losing/terminated at certain battle, and winning the final battle with attackers left. With the probability of all these scenario ready, you can calculate any expectation related.

 

[GameGod]

OK, so let me explain what the formula shows.

Let's consider the possible routes by which the attacker can go from the first territory to the second. He has to leave behind 1 piece, so there will be A[T_A]-1 attacking pieces against the D[T_1] defending pieces on the first territory he attacks. Given that we are calculating the probability that the attacker wins in his overall conquest, then the different outcomes by which victory might be possible are that: he has all A[T_A]-1 pieces left at the end, after the battle; he has A[T_A]-2 pieces left at the end; etc., all the way down to having only 1 piece left at the end (he cannot have 0 because then he hasn't won). Then the probability that he has a certain number, k, of pieces remaining, given the initial battle was A[T_A]-1 vs D[T_1], is simply the expectation from a single (A,D) battle that is calculated as before.

Now given that he had k pieces remaining, in the next battle, he will be able to fight using only k-1 pieces, against D[T_2] pieces. In this battle, again, any outcome from his ending up with k-1 pieces to his ending up with just 1 piece is possible. The probability of each of these is just the probability of his having a certain number of pieces remaining after a battle of (A,D), as before.

So now there is a pattern. My plan is simply to multiply the probability of the attacker having a pieces remaining after the first battle, b after the second, c after the third, together; and then sum over all values of the number of pieces remaining from each battle that are possible.

Maybe the best thing to request from you is that you could write out the function for a 2-series battle? i.e. A[T_A] on territory A, attacks territory 1 with D[T_1] defenders, and then territory 2 with D[T_2] defenders. What is the function for the probability the attacker will win both, in terms of A[T_A], D[T_1], D[T_2] and the single battle-probabilities we worked out before?

 

[BGM]

Let \( a_k \) be the number of attackers survived just before the \( k \)-th battle (if exist), so it is including those singleton attacker stayed in the territory. And \( a_1 \) is the initial number of the attackers. Note that the actual number of attackers entering the the \( k \)-th battle is \( a_k - k \).

Let \( d_k \) be the number of defenders entering the \( k \)-th battle.

Let \( p(\cdot|(a, d)) \) be the probability mass function of the number of attackers left after a battle given that the number of attackers and defenders entering the battle are \( (a, d) \)

Therefore the probability of winning is

\( \sum_{a_2 -1 = 2}^{a_1-1} \sum_{a_3 -2= 1}^{a_2 - 2} p(a_2-1|(a_1-1, d_1))
p(a_3-2|(a_2-2, d_2))\)

Sorry if I count it wrong

 

[GameGod]

Can I ask what's going on in the lower summation bounds and why? It seems a bit strange to me ...

 

[BGM]

Ok let me try to explain a little bit more.

In this two-battle campaign, as said before, there are \( a_1 - 1 \) attackers entering the 1st battle. So to win all two battles, you need at least \( 2 \) out of \( a_1 - 1 \) attackers survive after the 1st battle so that one can stayed in the victory land while the other can continue to enter the 2nd battle. Thats why the summation bound is from \( 2 \) to \( a_1 - 1 \). Basically the lower bound \( 2 \) is the number of battles remaining (including the current one), and the upper bound of course is the number of attackers entering the battle.

The reason why I chose \( a_2 - 1 \) as the dummy variable is due to the consistency of the notation. Remember there are \( 1 \) attacker stayed in the homeland before the first battle, in order to have a total of \( a_2 \) attackers survived right before the 2nd battle, it is equivalent to say that there are \( a_2 - 1 \) out of \( a_1 - 1 \) survived in the 1st battle. Hope this make sense.

 

[GameGod]

Thanks, so let me attempt a 3-battle sum:

\( \sum_{a_2 -1 = 3}^{a_1-1} \sum_{a_3 -2= 2}^{a_2 - 2} \sum_{a_4 -3 = 1}^{a_3 - 3} p(a_2-1|(a_1-1, d_1))
\cdot p(a_3-2|(a_2-2, d_2)) \cdot p(a_4-3|(a_3-3, d_3))\)

Maybe there is a problem with the bounds?

And can't we just rewrite e.g. \(a_2 -1 = 2\) as \(a_2 = 2 + 1\)?

 

[BGM]

This is for interpretation issue only - I just kept the argument of the pmf the same as the dummy variable of the summation. Of course you can always rewrite, e.g.

\( \sum_{a_2 - 1 = 3}^{a_1 - 1} = \sum_{a_2 = 4}^{a_1} \)

 

[GameGod]

OK thanks. And is it otherwise correct?

 

[GameGod]

Let \( a_k \) be the number of attackers survived just before the \( k \)-th battle (if exist), so it is including those singleton attacker stayed in the territory. And \( a_1 \) is the initial number of the attackers. Note that the actual number of attackers entering the the \( k \)-th battle is \( a_k - k \).

Let \( d_k \) be the number of defenders entering the \( k \)-th battle.

Let \( p(\cdot|(a, d)) \) be the probability mass function of the number of attackers left after a battle given that the number of attackers and defenders entering the battle are \( (a, d) \)

Therefore the probability of winning is

\( \sum_{a_2 -1 = 2}^{a_1-1} \sum_{a_3 -2= 1}^{a_2 - 2} p(a_2-1|(a_1-1, d_1))
p(a_3-2|(a_2-2, d_2))\)

Sorry if I count it wrong

Please help, I need to know if my 3-battle solution is correct so I can generalize. (See post #29)

Furthermore, could you show how to find the probability for the 2-battle scenario of there being \(m\) attackers surviving and placed on the last conquered territory at the end (in terms of the pm functions we already know how to calculate), for \(1 \leq m \leq a_0-2\) where \(a_0\) is the number of attackers that originally started (maximum \(m\) is \(a_0-2\) because the first battle involves \(a_0-1\) attackers, the second involves maximum \(a_0-2\) attackers and if these attackers all win there will be \(a_0-2\) surviving attackers on the last conquered territory).

 

[BGM]

I think #29 is alright (at least the same as my idea but maybe I am wrong). You may try to verify it by simulation.

For the latter problem you want to ask if there is exactly \( m \) attackers survive and placed on the last territory.

Note that in the formula \( \sum_{a_3 - 2 = 1}^{a_2 - 2} \) means we consider all the scenario with the attackers from \( 1 \) to \( a_2 - 2 \) so that you are winning the last battle. (Actually \( a_3 - 2 \) is the \( m \) you considered here).

Therefore you just need to modify it as

\( \sum_{a_2 - 1 = m+1}^{a_1 - 1} p(a_2 - 1|(a_1 - 1, d_1))p(m|(a_2 - 2, d_2) \)

Note that you require \( m + 1 \) survived after the second last battle.

 

[GameGod]

Thanks. So what are the two summation bounds for the 3-battle case?

\(\sum \sum p(a_2-1|(a_1-1, d_1))
\cdot p(a_3-2|(a_2-2, d_2)) \cdot p(m|(a_3-3, d_3))\)

But what are the summation bounds ...

 

[BGM]

Actually there is nothing special/mysterious. Just need to include all the cases, and ensure that it is possible to led to \( m \) survivors at last.

\( \sum_{a_2 -1 = m+2}^{a_1-1} \sum_{a_3 -2= m+1}^{a_2 - 2}
p(a_2-1|(a_1-1, d_1))p(a_3-2|(a_2-2, d_2))p(m|(a_3-3, d_3)) \)