How can I efficiently calculate the mathematical limit for average number of rounds in a game?

user_2947592 0
Viewed 38

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).

math javascript
1 Answers

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 :)).

user_102217650
Related