Probabilistic Dynamic Programming II

I thought this was relatively harder so wanted to analyse this as well.

The task goes as follows: The inhabitants of an island are divided into three tribes: Bears, Hunters, and Ninjas. They are very hostile, and whenever two members of different tribes meet, the stronger one always eliminates the weaker one. It is known that a bear is stronger than a ninja, a ninja is stronger than a hunter, a hunter is stronger than a bear. The hostility goes on until only one tribe remains. What is the probability that each tribe is the last one standing, given initial population size?

Once again, before coding let's get into the calculation and without the loss of generality, let's consider the probability chance of bear. Let

P r [B_{i, j, k}]

be the survival probaility of bears under the assumption that

i

bears,

j

ninjas and

k

bears left. Also let us consider "meetings" as uniformaly consectivly choosen two inhabitants. Let

X_{i} / Y_{i} / Z_{i}

i \in {1, 2}

-th choice bear/ninja/hunter. The following equality consists of union of pairwise disjunkt occurances and it holds.

P r [(Y_{2} \cap X_{1}) \cup (Z_{2} \cap X_{1}) \cup (X_{2} \cap X_{1}) \cup (Y_{2} \cap Y_{1}) \cup (Z_{2} \cap Y_{1}) \cup (X_{2} \cap Y_{1}) \cup (Z_{2} \cap Z_{1}) \cup (X_{2} \cap Z_{1}) \cup (Y_{2} \cap Z_{1})] = P r [(X_{1} \cap (Y_{2} \cup Z_{2} \cup X_{2})) \cup (Y_{1} \cap (Y_{2} \cup Z_{2} \cup X_{2})) \cup (Z_{1} \cap (Y_{2} \cup Z_{2} \cup X_{2}))] = P r [(Y_{2} \cup Z_{2} \cup X_{2}) \cap (X_{1} \cup Y_{1} \cup Z_{1})] = P r [X_{1} \cup Y_{1} \cup Z_{1}] P r [(Y_{2} \cup Z_{2} \cup X_{2}) | (X_{1} \cup Y_{1} \cup Z_{1})] = 1

We can use it to construct an equation for

P r [B_{i, j, k}]

P r [B_{i, j, k}] = P r [X_{1}] P r [Y_{2} | X_{1}] P r [B_{i, j, k} | Y_{2} \cap X_{1}] + P r [X_{1}] P r [Z_{2} | X_{1}] P r [B_{i, j, k} | Z_{2} \cap X_{1}] + P r [X_{1}] P r [X_{2} | X_{1}] P r [B_{i, j, k} | X_{2} \cap X_{1}] + P r [Y_{1}] P r [Y_{2} | Y_{1}] P r [B_{i, j, k} | Y_{2} \cap Y_{1}] + P r [Y_{1}] P r [Z_{2} | Y_{1}] P r [B_{i, j, k} | Z_{2} \cap Y_{1}] + P r [Y_{1}] P r [X_{2} | Y_{1}] P r [B_{i, j, k} | X_{2} \cap Y_{1}] + P r [Z_{1}] P r [Z_{2} | Z_{1}] P r [B_{i, j, k} | Z_{2} \cap Z_{1}] + P r [Z_{1}] P r [X_{2} | Z_{1}] P r [B_{i, j, k} | X_{2} \cap Z_{1}] + P r [Z_{1}] P r [Y_{2} | Z_{1}] P r [B_{i, j, k} | Y_{2} \cap Z_{1}]

Now let's make it more readable:

P r [B_{i, j, k}] = \frac{i}{i + j + k} \cdot \frac{j}{i + j + k - 1} P r [B_{i, j - 1, k}] + \frac{i}{i + j + k} \cdot \frac{k}{i + j + k - 1} P r [B_{i - 1, j, k}] + \frac{i}{i + j + k} \cdot \frac{i - 1}{i + j + k - 1} P r [B_{i, j, k}] + \frac{j}{i + j + k} \cdot \frac{j - 1}{i + j + k - 1} P r [B_{i, j, k}] + \frac{j}{i + j + k} \cdot \frac{k}{i + j + k - 1} P r [B_{i, j, k - 1}] + \frac{j}{i + j + k} \cdot \frac{i}{i + j + k - 1} P r [B_{i, j - 1, k}] + \frac{k}{i + j + k} \cdot \frac{k - 1}{i + j + k - 1} P r [B_{i, j, k}] + \frac{k}{i + j + k} \cdot \frac{i}{i + j + k - 1} P r [B_{i - 1, j, k}] + \frac{k}{i + j + k} \cdot \frac{j}{i + j + k - 1} P r [B_{i, j, k - 1}] = \frac{2 i j \cdot P r [B_{i, j - 1, k}] + 2 i k \cdot P r [B_{i - 1, j, k}] + 2 j k \cdot P r [B_{i, j, k - 1}]}{(i + j + k) (i + j + k - 1)} + \frac{i^{2} - i + j^{2} - j + k^{2} - k}{(i + j + k) (i + j + k - 1)} P r [B_{i, j, k}] \Leftrightarrow P r [B_{i, j, k}] = \frac{2 i j \cdot P r [B_{i, j - 1, k}] + 2 i k \cdot P r [B_{i - 1, j, k}] + 2 j k \cdot P r [B_{i, j, k - 1}]}{i j + i k + j i + j k + k i + k j}

In addition to that, we have 3 base cases:

P r [B_{i > 0, j, 0}] = 1

P r [B_{i = 0, j, k}] = 0

and

P r [B_{i, j = 0, k > 0}] = 0

. Using a DP table, the code looks like this and runs in

O (b n h)

Read more

dYdX v4

GMX Data Pipeline

Probabilistic Dynamic Programming I