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

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

CodePudding user response：

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