Intuitive Approach to Solve Probability-DP Tasks

Disclaimer: This blogpost walks through Island Tribes as an exemplary CE Task which we had during our semester, so beware of spoilers in case you haven't solved it yet.

The type of problems that typically require a DP Approach are the problems which contain probabilistic decisions happening in a period of time, until some condition is reached.

Let's look at the example of the Island Tribes task and draw a tree with possible outcomes by hand, in order to derive our Recurrence. This is in general a safe bet - to work it out by hand for a small example first.

Island Tribes

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, à la survival of the fittest. It is known that

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?

Say we start with 2 bears, 1 hunter, 2 ninjas. We denote one time step as an occurrence of two members of distinct tribes meeting (if two of the same tribes meet, nothing happens). At time step 0 we have 2-1-2 (b-h-n). At time step 1, we have 2 possible ways for a bear to be eliminated. Hunters kill bears, and since we have 1 Hunter and 2 Bears, there are 2*1 possible ways a Bear can get removed, either the first hunter kills the first bear or the first hunter kills the second bear. Similarly, we have 2 possible ways for a Hunter to get removed, since ninjas are stronger than hunters and there are 2 ninjas and 1 hunter. Lastly, we have 4 possible ways that a Ninja can get removed, since there are 2 ninjas and 2 bears, while bears are stronger than ninjas, which results in 2*2=4 distinct pairs of one ninja and one bear each.

First time step

Now what is the probability of reaching for instance the state 1 1 2 (B-H-N)? We have 2+2+4 total hostile meetings that are possible, 2 of which result in a bear being eliminated (reaching 1 1 2 from 2 1 2). Hence, the probability to get 1 1 2 is . We can generalize this.

Full tree What is the probability of reaching 0 1 2? Well, we have a 0.25 probability of getting to 1 1 2 and a probability of reaching 0 1 2 from there. So from the initial state 2 1 2 we have a 0.25*0.2 probability to reach 0 1 2. Now what is the probability to get to any endings that end up with the Bears being the tribe remaining?

Let us denote as the probability of Bears remaining at the end, given B bears, H hunters, and N ninjas. Following the Law of Total Probability, we get

We notice that

and analogously:

Filling this into the recurrence above gives us

We have the base case

Top-Down Way

To do it Top-Down, we define a function to recursively calculate these Probabilities. Before returning, we save the values and before every recursion we check if we already previously calculated the entry. This way we save a lot of computation, the ones ticked in orange in the above image.

Bottom-Up Way

We loop over the 3 dimensions of the DP-Table i.e. an array of dimensions (b+1)x(h+1)x(n+1), calculating the new value from the entries we calculated in the respective previous iterations. This is quite elegant.

Base case

Now that we know the probability that the bears are the last remaining tribe, we can retrieve the probability of the hunter winning and the probability of the ninja winning as well.

For that, we notice that the to calculate the probabilities for the hunters winning, we only change the base case to be

and for the ninjas:

Hence, since the recurrence is the same otherwise, we observe that:

Therefore we can calculate the probability of any one of the tribes winning as the respective cyclic rotation of the original DP-Array . We initialize our base-case (for ) and then simply do 3 loops (nested) to loop over values of B, H, and N bottom-up, and calculate the new DP-Entries of using the recurrence we derived from the initial drawing by hand, effectively re-using the previously calculated values.

Slay the Dragon

We have to calculate the expected value (Erwartungswert) of needed spells to kill the dragon. This is also a probability DP exercise, the difference being that we have to determine the Erwartungswert from the Probability-DP-Array in the end. For this, it is essential to know the Law of total Expectation, in addition to the Law of total Probability (used in pretty much all of these types of tasks).

Winter Season

This is a quite straightforward and stereotypical DP-Probability, comparatively easier than the other ones. Drawing the tree again gives us the recurrence needed.

Recipe

1) Draw a small example by hand 2) What variables make up the states? In the case of Island Tribes, this was the amount of bears, hunters, and ninjas. It is easiest if you attribute one DP-Dimension to each of these variables. Most of the time, you can save memory by overwriting old DP values when it's not necessary to save all of them, however that is not needed and the intuitive way is sufficient (hopefully). 3) Derive the recurrence from this using the Law of Total Probability and some pondering about how you get from one state to another in the example you drew 4) Figure out the base case, depends on what the tasks asks from you to deliver the probability of 5) Read out the correct value(s) to determine the result (or what you need to get to the result)

 

Hope you enjoyed :) ~Tobi