Probability computation via decision tree

Introduction

In SingleOrDouble problem from TCO 2022 Round 1A, we want to compute the probability for Alice to win a game.

The game is played via following rules

• we generate a sequence of stages. For each stage, the result is the sum of N dice thrown at random. They all have D faces.
• In this experiment, there are 2 events in the sample space
• Alice wins as soon as the number is A
• Bob wins as soon as the number is B twice in a row

Let WA be a binary random variable which value is the outcome of the experiment

• WA=1 if Alice wons
• WA=0 if Alice looses

As a note, we are interested in the expected value ...

E[WA] = p[WA=0] * 0 + p[WA=1] * 1
E[WA] = p[WA=1]

Probability 101

Notice the terms in bold in the introduction. I have reused the terms outlined in the 1st video lecture in Probabilistic Systems Analysis and Applied Probability MIT course. It is available for free.

Probability distribution for an individual event

The generated numbers M_i in each round i are independent random variables. They follow the same discrete probability distribution of a random variable M. Valid values range from 1*N (all dice land on 1) to D*N (all dice land on D).

We define array S as the count array for the possibilities for N dice to sum up to any values n, n = N ... D*N.

We get the statistics associated to outcome n using N dice, based on the last die value d and the statistics associated to n-d using N-1 dice.

S[N][n] = Sum(S[N-1][n-d], d = 1 ... D)

Dynamic programming

We can compute the statistics array via DP, with a single array in O(D*N^2). 

int[] S = new int[D*N+1];
S[0] = 1;
for (int i = 1; i <= N; i++) {
   for (int s = i*D; s >= 0; s--) {
      S[s] = 0;
      for (int d = 1; d <= D; d++) {
         if (s-d < 0 || (i > 1 && s-d == 0)) {
            continue;
         }
         S[s] += S[s-d];
      }
   }
}

int sum = 0;
for (int s = N; s <= N*D; s++) {
   sum += S[s];
}

double pA = 1D * S[A] / sum;
double pB = 1D * S[B] / sum;

Below is the sum count for D=6, N = {1, 2, 3}

We divide by the total number of outcomes to calculate the probability:

p[M=n] = S[n] / Sum(S[s], s = N ... D*N)

See editorial for an alternative DP computation of the probability.

Decision tree

We look at the first 2 numbers N1 and N2 in the sequence. This makes sense because Bob wins after 2 consecutive numbers equal to B.

We break down the set of all individual outcomes into 3 disjoint subsets or events:

• A
• B
• A∪B

Notice they are

• Mutually exclusive
• Collectively exhaustive

Decision tree for the 1st 2 stages in the sequence based on the 3 possible events is

There are 5 leaves in the above tree. We can write Ω as a disjoint union of 5 events.

• N1=A
• N1=B,N2=A
• N1=B,N2=B
• N1=B,N2=A∪B
• N1=A∪B

as

Ω = N1=A ∪ N1=B,N2=A ∪ N1=B,N2=B ∪ N1=B,N2=A∪B ∪ N1=A∪B

The winning event can then be partitioned into

WA=1 = WA=1 ∩ Ω

     = WA=1 ∩ (N1=A ∪ N1=B,N2=A ∪ N1=B,N2=B ∪ N1=B,N2=A∪B ∪ N1=A∪B)

     = (WA=1 ∩ N1=A) ∪

       (WA=1 ∩ N1=B,N2=A) ∪

       (WA=1 ∩ N1=B,N2=B) ∪

       (WA=1 ∩ N1=B,N2=A∪B) ∪

       (WA=1 ∩ N1=A∪B)

The winning event probability is now the sum of each associated event probabilities

p[WA=1] = p[WA=1 ∩ N1=A] +

          p[WA=1 ∩ N1=B,N2=A] +

          p[WA=1 ∩ N1=B,N2=B] +

          p[WA=1 ∩ N1=B,N2=A∪B] +

          p[WA=1 ∩ N1=A∪B]

We can rewrite the conditional probability formula

P[E1 | E2] = P[E1 ∩ E2] / P[E2]

to express the probability of the intersection

P[E1 ∩ E2] = P[E1 | E2] * P[E2]

p[WA=1] = p[WA=1 | N1=A] * p[N1=A] +

          p[WA=1 | N1=B,N2=A] * p[N1=B,N2=A] +

          p[WA=1 | N1=B,N2=B] * p[N1=B,N2=B] +

          p[WA=1 | N1=B,N2=A∪B] * p[N1=B,N2=A∪B] +

          p[WA=1 | N1=A∪B] * p[N1=A∪B]

Assumptions

Now we apply the rules from the problem description:

Alice winning rule

Alice wins on the first occurence of A

p[WA=1 | N1=A] = p[WA=1 | N1=B,N2=A] = 1

Bob winning rule

Alice looses on the first 2 consecutive occurrences of B

p[WA=1 | N1=B,N2=B] = 0

Independent variables

With individual event probabilities

• pA = p[N=A]
• pB = p[N=B]

we have

p[N1=B,N2=A] = p[N1=B] * p[N2=A] = pB * pA

p[N1=B,N2=B] = p[N1=B] * p[N2=B] = pB * pB

p[N1=B,N2=A∪B] = p[N1=B] * p[N2=A∪B] = pB * (1-pA-pB)

The probability of Alice winning the game if N1 was not A or B is the overall probability of winning, same for N2 not equal to A or B.

p[WA=1 | N1=A∪B] = p[WA=1 | N1=B,N2=A∪B] = p[WA=1]

Probability equation

Let pWA be the probability that Alice wins,

pWA = p[WA=1]

We can finally derive the expression for pWA :

pWA = 1 * pA +

      1 * pB * pA +

      0 * pB * pB +

      pWA * pB * (1-pA-pB) +

      pWA * (1-pA-pB)

which leads to

pWA = (pA + pB * pA) / (pA + pB * pA + pB*pB)

Conclusion

We write down the winning probability as a sum over a disjoint partition of outcome subsets, called events. Using conditional probability, we express each event probability as a product of the conditional probability of winning given this event and the probability of the event.

To help us break down the sample space, we use a decision tree based on the rules of the game. They usually give us winning / losing outcomes assuming some conditions on previous events.

This lets us come up with a linear equation of which pWA is a solution.

Annex

Matplotlib input

import matplotlib.pyplot as plt

S1 = [1, 1, 1, 1, 1, 1]

S2 = [1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1]

S3 = [1, 3, 6, 10, 15, 21, 25, 27, 27, 25, 21, 15, 10, 6, 3, 1]

plt.plot(range(1, len(S1)+1), S1, label='N=1', marker='.')

plt.plot(range(2, len(S2)+2), S2, label='N=2', marker='+')

plt.plot(range(3, len(S3)+3), S3, label='N=3', marker='*')

plt.xticks(range(1, len(S3)+3))

plt.title('Count for the sum of N D-face dice values, D=6')

plt.legend()

plt.show()

Graphviz input

digraph G {

  N1 -> N2;

  O -> A1;

  O -> B1;

  O -> C1;

  B1 -> A2;

  B1 -> B2;

  B1 -> C2;

  O [label="Ω"];

  A1, A2 [label="A"];

  B1, B2 [label="B"];

  C1, C2 [label=<<O>A &cup; B</O>>];

  { rank = same;

    N1; A1; B1; C1; };

}