# Statement

A and B are playing a game of generalized Rock-Paper-Scissors, with $$n = 2k+1$$ distinct moves. Which moves beat which others is given as a $$n$$ oriented complete graph, where $$d_{in}(v_i) = d_{out}(v_i) = k$$.

The game is played best-of-3. That is, A and B play until one of them has two victories. You are given the probability vector $$V_A$$ that A plays each of his moves, and the probability vector $$V_B$$ that B plays each of his moves. You should determine the probability that A wins.

For instance, suppose $$k = 2$$, and you’re given the vectors $$V_A = \langle 0.1, 0.1, 0.2, 0.3, 0.4, 0\rangle$$, $$V_B = \langle 0.1, 0.1, 0.1, 0.1, 0.6 \rangle$$, you should answer $$\frac{2}{3}$$.

# Analysis

It should be clear that given $$V_A$$ and $$V_B$$, we can know the probability that A wins a given round. This is simple enough. Suppose that the game is as follows:

Then we know the probability $$w$$ that A wins a given round, is (denoting $$X_i$$ the probability that player X plays move $$i$$)

\begin{aligned} w = & A_{Spock} \cdot (B_{Scissors} + B_{Rock}) \\ &+ A_{Lizard} \cdot (B_{Spock} + B_{Paper}) \\ &+ A_{Rock} \cdot (B_{Scissors} + B_{Lizard}) \\ &+ A_{Paper} \cdot (B_{Spock} + B_{Rock}) \\ &+ A_{Scissors} \cdot (B_{Lizard} + B_{Paper}) \end{aligned}

Similarly, the probability $$t$$ of a tie can be written

$t = \sum_{i} A_i \cdot B_i = \langle V_A, V_B \rangle$

And obviously, we have that the probability $$l$$ of A losing can be written $l = 1 - w - t$

So we want to express the probability that A wins two games before B does. After unsuccessfully attacking the problem as a single sum of probabilities, I decided to think of it as four different subgames. In the first subgame, let’s call it $$G$$, neither player has won any rounds yet. In subgame $$G_1$$, A has won exactly one round, B hasn’t won. In subgame $$G_2$$, B has won exactly one round, and A hasn’t won. Finally, in subgame $$G_3$$, both players have won exactly one round each.

If we think of the game this way, we see that we have a sort of Markov chain of subgames, that looks like this:

Where $$0$$ is the state where A lost the game, and $$1$$ is the state where A won the game. As an example, this means that if we are playing subgame $$G_2$$, with probability $$w$$ we will start playing subgame $$G_3$$, with probability $$l$$ A will lose the game, and with probability $$l$$ we will keep playing subgame $$G_2$$.

What we want, then, is the probability that, starting at subgame $$G$$, we get to the state $$1$$. That is, we get to the state where A has won.

What we could do is reason backwards, and ask for each node, what the probability is to reach it, starting from $$G$$. If we do that, then we need only ask this question about the node $$1$$ to obtain our answer. So let’s try.

• For $$G_1$$, remember that it is the state where A won one round, B won none. The probability that we got to that subgame is the probability that A’s victory was on the first round, or that they tied the first round and A won the second round, or that they tied twice and A won the 3rd round, or so on. The probability of the first case is what we called $$w$$. The probability of the second case is $$t \cdot w$$, since each round is independent. The probability of the third case is $$t \cdot t \cdot w = t^2 w$$. Since all of these things are disjoint (we can’t both have tied until the $$k$$th round and won the $$k+1$$th round, and tied until the $$k'$$th round and won the $$k'+1$$th round, if $$k \ne k'$$), we must sum their probabilities. This means that the probability that we get to $$G_1$$ is

\begin{aligned} P(G_1) &= \sum_{i=0}^\infty t^i w\\ &= w \cdot \left(\sum_{i=0}^\infty t^i\right)\\ &= \frac{w}{1 - t} \end{aligned}

• For $$G_2$$, we can do the exact same analysis, arriving at $P(G_2) = \frac{l}{1 - t}$

• For $$G_3$$, since we either came from $$G_2$$ or came from $$G_1$$, and in each of those we could have tied an arbitrarily large (but obviously finite) number of times. This means we have \begin{aligned} P(G_3) &= P(G_1) \cdot \left(\sum_{i=0}^\infty t^i\right) \cdot l + P(G_2) \cdot \left(\sum_{i=0}^\infty t^i\right) \cdot w\\ &= \frac{P(G_1) \cdot l + P(G_2) \cdot w}{1 - t}\\ &= \frac{\frac{w}{1 - t} \cdot l + \frac{l}{1 - t} \cdot w}{1 - t}\\ &= \frac{2\cdot w \cdot l}{(1-t)^2} \end{aligned}

• Finally, for state 1, it must have happened that either they played game $$G_1$$ and A won after some number of ties, or they played game $$G_3$$, and A won after some number of ties. That is, we must have \begin{aligned} P(1) &= \frac{P(G_1) \cdot w + P(G_3) \cdot w}{1 - t}\\ &= (P(G_1) + P(G_3)) \cdot \frac{w}{1 - t}\\ &= \left(P(G_1) + \frac{2\cdot w\cdot l}{(1 - t)^2}\right) \cdot P(G_1)\\ &= P(G_1)^2 + 2 \cdot P(G_1)^2 \cdot P(G_2)\\ &= P(G_1)^2 (1 + 2 \cdot P(G_2)) \end{aligned}

# Generalization

That was the original problem I was faced with, and that solution was indeed correct. However, we can certainly generalize this. We can consider that the winning player is the one who gets to $$k$$ rounds won first. In order to consider this, we will need to expand our model to the following generalization:

Let $$n, m \in \mathbb{N}^2$$. We define the subgame $$G_{n, m}$$ to be the one where A has won exactly $$n$$ rounds, and B has won exactly $$m$$ rounds. Then, the Markov chain around $$G_{n, m}$$ looks like this:

From which we can deduce, by an analysis similar to our previous ones, that $P(G_{n, m}) = \begin{cases} 1& \text{if } n = 0 \text{ and } m = 0\\ l \cdot P(G_{n, m-1}) \cdot (1 - t)^{-1}& \text{if } n = 0 \text{ and } m > 0 \\ w \cdot P(G_{n-1, m}) \cdot (1 - t)^{-1} & \text{ if } n > 0 \text{ and } m = 0 \\ (w \cdot P(G_{n - 1, m}) + l \cdot P(G_{n, m-1})) \cdot (1 - t)^{-1} & \text{ otherwise } \end{cases}$

With the initial game being, of course, $$G_{0, 0}$$.

To find the probability that A wins (i.e. is the first to reach $$k$$ rounds won), we must find $$P(G_{k-1, i})$$ for all $$1 \le i \le k-1$$, and compute $\sum_{i=0}^{k-1} P(G_{k-1, i}) \cdot w$

This yields the obvious dynamic programming algorithm to compute the required probability, in $$O(k^2)$$ space and time.

## Alternative solution

Another way of finding the desired probability, is considering that ties do not matter. That is, if I am asking about probability of A reaching $$k$$ rounds won before B does, it doesn’t really matter what the probability of tying wins. All that matters is who is more likely to reach $$k$$ wins, and by how much. In a sense, the problem only depends on $$w$$, not on $$t$$. So we can rescale $$w$$ and $$l$$ by multiplying them by $$(1-t)^{-1}$$, and now we have the constraint $$w + l = 1$$.

Thus, we can consider every sequence of the form $$WLLWWWLLWLLLWLL\dots$$, that is, sequence of rounds being won or lost, ignoring ties. We can say that any victory for A, is exactly one sequence of $$k-1$$ wins for A and $$i$$ wins for B for some $$1 \le i \le k-1$$, followed by a win by A. So to compute this, we can sum \begin{aligned} &\left(\sum_{i=0}^{k-1} \binom{k + i - 1}{k - 1} \cdot w^{k - 1} \cdot l^i\right) \cdot w\\ = &w^k \cdot \sum_{i=0}^{k-1} \binom{k + i - 1}{k - 1} \cdot l^i \end{aligned}

Where the sum has a limit of $$k-1$$, since we do not allow for B to have won $$k$$ times, only at most $$k-1$$, before A’s final winning of the $$k$$th round.