For an odds calculator for a board game, I need to calculate how many rounds a battle will last on average. Because there is a possibility that both sides in the battle will miss, a battle can theoretically last forever. Therefore I cannot traverse all branches, but need to calculate a mathematical limit. By verifying with a simulator, I have found that the following function correctly approximates the average number of rounds left:
// LIMIT could be any number, the larger it is, the more accurate the result.
const LIMIT = 100;
// r is the number of rounds left if at least 1 of the sides hit
// x is the chance that both sides miss and the round count gets increased,
// but the battle state stays the same.
function approximateLimitForNumberOfRounds(r: number, x: number) {
let approx = r / (1 - x);
// n -> infinity
for (let n = 1; n < LIMIT; n++) {
approx += x ** n;
}
return approx;
}
How can I modify this function to exactly calculate the number of rounds left, instead of approximating it? (noting that since x is a chance, it is contained in (0, 1) or 0 < x < 1).
We can note that approx takes on the following values:
r / (1 - x) # I refer to this as 'a' below
a + x
a + x + x^2
a + x + x^2 + x^3
a + x + x^2 + ... + x^n
Thus, we can simplify the mathematical expression to be:
a + (the sum of x^k from k = 1 to k = n)
Next, we must note that the sequence x + x^2 + x^3 ... forms a geometric sequence with first term x and common ratio x. Since x is bounded by 0 < x < 1, this will have a limiting sum, namely:
x + x^2 + x^3 + ... x^inf = x/(1-x)
(this obviously fails when x = 1, as well as in the original function where r / (1 - x) is taken, but in that case, you will simply have the sum as infinity and approx would escape to infinity if it were not undefined; so I am assuming that x != 1 in the following calculations and x = 1 can be / has been dealt with separately).
Now, since we have both a single expression for x + x^2 + ... to infinity, and a single expression for approx that includes x + x^2 + ... then we can write approx using both of these two facts:
approx = r / (1 - x) + x / (1 - x)
approx = (r + x) / (1 - x)
And there you go! That is the mathematical equivalent of the logic you've outlined in your question, compressed to a single statement (which I believe is correct :)).