0
$\begingroup$

I'm trying to simplify a win/loss simulation. The situation is as follows:

Let's say there are two players A and B where:

  • When A goes into a battle, it's probability of a win is 0.1 (10%)
  • When B goes into a battle, it's probability of a win is 0.2 (20%)

Note 1 : The win probability is invariant to the opponent.

Note 2 : There are no draws, though there could be in a future enhancement, for now trying to keep things simple.

Note 3 : There are other players in the game each with their own probabilities.

If A and B were to battle each other I need to determine who will win.

Currently what I'm doing is sampling 2 different Bernoulli distributions, one for A (with $P_a = 0.1$) and one for B (with $P_b = 0.2$)

I sample each of the distributions until only one of them returns success. That player is the winner of the battle, the other player will have lost. The following is pseudo code of the process:

while (true)
{
   bool win_a = bernoulli(pr_a);
   bool win_b = bernoulli(pr_b);

   if (win_a == win_b) // either both won or both lost
      continue;

   if (win_a)
      return "A won";
   else
      return "B won";
}

The problem with the above approach is that even though it will eventually determine a winner, it may end-up looping for a long time before it does.

I was wondering if there's a mathematically valid way of combining the above probabilities into a singular Bernoulli trial such that $Pr(A_{winning})= k$ and $Pr(B_{winning}) = 1 - k$ for some particular k.

My current thinking is that $k = \frac{P_a}{(P_a + P_b)}$ but I'm not sure if it is correct or how to reason about it correctness.

$\endgroup$

2 Answers 2

1
$\begingroup$

In sports simulations, there is a standard way to combine win probabilities for head-to-head contests in which no tie is possible, even when the contestants have not faced off previously. It should be emphasized that this is heuristic only; there is no first-principles validation for this approach, because the situation is underdetermined.

Essentially, suppose that $A$'s winning probability is $p$, and $B$'s winning probability is $q$. Then we write that

$$ P(\text{$A$ beats $B$}) = \frac{p(1-q)}{p(1-q)+q(1-p)} $$

and

$$ P(\text{$B$ beats $A$}) = \frac{q(1-p)}{p(1-q)+q(1-p)} $$

Your simulation happens to yield these same probabilities, but as I said, that's not provably correct.

$\endgroup$
8
  • $\begingroup$ thanks for the concise and informative answer, is there a name for the above formulation? something I further can research and read-up on, as I don't quite understand how those to identities were derived. $\endgroup$ Commented Dec 29, 2016 at 0:17
  • $\begingroup$ Why the simulation is not provably correct? I thought it is called acceptance-rejection method. $\endgroup$
    – Momo
    Commented Dec 29, 2016 at 0:18
  • $\begingroup$ @Momo: Given the OP's methodology, it is provably correct. What I mean is that there are plenty of situations where, on the whole, $A$'s winning percentage is $p$ and $B$'s winning percentage is $q$, but $A$ always beats $B$. This approach assumes a kind of independence that we can't necessarily insist on. $\endgroup$
    – Brian Tung
    Commented Dec 29, 2016 at 0:21
  • 1
    $\begingroup$ @Momo: For instance, in a three-person round-robin, suppose $A$ always beats $B$, who always beats $C$, who always beats $A$ (cyclic dominance). Then each player has a winning probability of $0.5$, but $A$ always beats $B$, even though the formula generates a winning probability of $0.5$ for any contestant in any contest. $\endgroup$
    – Brian Tung
    Commented Dec 29, 2016 at 0:26
  • $\begingroup$ @JacobiJohn: I'm not aware of a specific name; acceptance-rejection, cited by Momo, seems as good as any. The origin of the expression is relatively straightforward: As in your simulation, we consider only those cases where one contestant wins and the other loses. Within that restricted sample space (represented by the denominator in the expressions above), the probability of either contestant winning is the product of that contestant's winning probability and the opponent's losing probability. $\endgroup$
    – Brian Tung
    Commented Dec 29, 2016 at 0:28
0
$\begingroup$

Let $X=1$ if A wins and $0$ otherwise. Let $Y=1$ if B wins and $0$ otherwise.

$P(\text{A wins})=P(X=1,Y=0)=P(X=1)P(Y=0)=P_a(1-P_b)$

$P(\text{B wins})=P(X=0,Y=1)=P(X=0)P(Y=1)=P_b(1-P_a)$

So you need to generate a Bernoulli r.v. $Z$ with odds ratio $P_a(1-P_b):P_b(1-P_a)$

$P(\text{A wins})=P(Z=1)=\frac{P_a(1-P_b)}{P_a(1-P_b)+P_b(1-P_a)}$

$P(\text{B wins})=P(Z=0)=\frac{P_b(1-P_a)}{P_a(1-P_b)+P_b(1-P_a)}$

$\endgroup$
14
  • $\begingroup$ Ahhh now I understand! thank-you for the explanation. So the simulation I'm running is generally wrong... yet seems to give what looks like "reasonable" results. I guess it's time to throw that away. $\endgroup$ Commented Dec 29, 2016 at 0:19
  • $\begingroup$ The simulation is right. It is called acceptance-rejection method. Thowing away the ties is equivalent to conditioning on a decisive result, which gives you exactly the probabilities above. $\endgroup$
    – Momo
    Commented Dec 29, 2016 at 0:20
  • $\begingroup$ @JacobiJohn: I would not say your simulation is wrong. I would say it is a heuristic that gives reasonable results. There is not enough information to say whether a particular formula is right or wrong. $\endgroup$
    – Brian Tung
    Commented Dec 29, 2016 at 0:24
  • $\begingroup$ @Brian Tung I wouldn't exactly call it "heuristic". It just assumes independence. And it is a good model when the two Bernoulli are either independent or weakly conditioned. $\endgroup$
    – Momo
    Commented Dec 29, 2016 at 0:38
  • $\begingroup$ When two contestants go head to head, I wouldn't generally assume independence. In general, their winning probabilities aren't mutually consistent. $\endgroup$
    – Brian Tung
    Commented Dec 29, 2016 at 0:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .