CS2030 Practical Assessment #2

Back to homepage

Probability Monad

Many problems found in textbooks on probability and statistics can be solved by applying probabilistic functions. For example,

• what is the probability of getting a head (or a tail) when tossing a coin?
• what is the probability of getting two heads and one tail when tossing a coin three times?
• what is the probability of getting at least two 6s when rolling a six-sided die (no pun intended) four times?
• etc..

Since the techniques used to solve these problems are very similar, we can abstract out the computation into a computation context! This frees up the client to focus on defining the problem and applying these abstractions via the context.

Task

In this task, you are to define a probability context Dist<T> that takes in a distribution table of probability values as a List<T>, so that it can be used to solve probability problems such as those mentioned above. Here is an example to find the probability of landing heads when tossing a coin.

jshell> Dist.<String>of(List.of("H","T"))
$.. ==> [H, T]

jshell> Dist.<String>of(List.of("H","T")).query(x -> x.equals("H"))
$.. ==> 0.5

Take Note!

This task comprises a number of levels. You are required to complete ALL levels.

The following are the constraints imposed on this task. In general, you should keep to the constructs and programming discipline instilled throughout the module.

• Write each class or interface in its own file. Do not use single letter names for classes or interfaces.
• Ensure that ALL object properties and class constants are declared private final
• Ensure that ALL classes/interfaces are NOT cyclic dependent.
• ONLY the following java libraries ARE allowed:
  • java.util.List
  • java.util.stream.Stream
  • functional interfaces from java.util.function
• The following are NOT allowed:
  • var, null, default, enum
  • instanceof (except checking for an instance of its own class)
  • methods of the String class
• You are NOT allowed to define anonymous inner classes; if necessary, define lambdas instead.
• Other usual restrictions:
  • Use only &&, || and ! in logical expressions. DO NOT use bitwise operators.
  • You are NOT allowed to use * wildcard imports.
  • You are NOT allowed to use method references ::
  • You are NOT allowed to define array constructs, e.g. String[] or using ellipsis, e.g.String...
  • You are NOT allowed to use exception handling
  • You are NOT allowed to use Java reflection, i.e. Object::getClasses and other methods from java.lang.Class

In the following level specifications, you will be guided on the non-private methods to define. Any other method you create yourself must be declared private.

An Event class has been provided for you. It is similar to the usual Pair but the second value has a fixed type of double. DO NOT replace this with your own version.

DO NOT use any other Java records. If necessary, write a class.

To keep things simple, all levels DO NOT require the use of bounded wildcards.

Level 1

Write a generic class Dist<T> to represent a uniform probability distribution by taking in a List<T> of outcomes of an experiment, e.g. tossing a coin.

• Write a factory method static <T> Dist<T> of(List<T> list) that encapsulates the list of outcomes;
• Write a toString() method that returns a string representation of the outcomes, or events.

The sample run below depicts the probability distribution of tossing a fair coin, and rolling a fair die.

jshell> Dist<String> toss = Dist.<String>of(List.of("H","T"))
toss ==> [H, T]

jshell> Dist<Integer> roll = Dist.of(List.of(1,2,3,4,5,6))
roll ==> [1, 2, 3, 4, 5, 6]

Now include a forEach() method that output each event together with its probability of occurrence within that experiment as follows:

jshell> toss.forEach()
Event[H, 0.500]
Event[T, 0.500]

jshell> roll.forEach()
Event[1, 0.167]
Event[2, 0.167]
Event[3, 0.167]
Event[4, 0.167]
Event[5, 0.167]
Event[6, 0.167]

Notice that the probability values always sum to 1.0, altough the output probability values are rounded.

Level 2

Write a query method that takes in a Predicate<T> and returns a value of type double that represents the probability that an event occurs in the experiment.

jshell> Dist.<Integer>of(List.of(1,2,3,4,5,6)).
   ...> query(x -> x == 6)
$.. ==> 0.16666666666666666

jshell> Dist.<Integer>of(List.of(1,2,3,4,5,6)).
   ...> query(x -> x % 2 == 0)
$.. ==> 0.5

Thus far, we have been assuming fairness in the experiment. For the case of, say an unfair coin, we can also make use of Dist by passing in a list of occurrences of the events when performing the experiment over a period of time, e.g. [H,T,H,H,T,T,T].

jshell> Dist.<String>of(List.of("H","T","H","H","T","T","T"))
$.. ==> [H, T]

jshell> Dist.<String>of(List.of("H","T","H","H","T","T","T")).
   ...> forEach()
Event[H, 0.429]
Event[T, 0.571]

Notice from the above that the outcomes are normalized so that it represents the probability distribution of the unfair coin. In the above, since there are four occurrences of T out of seven, T has a higher probability of 4/7. Moreover, normalization of events is performed in order of presentation of the outcomes of the experiment. In the above, since H is the first outcome, normalization for H is performed first.

Level 3

Given a probability distribution of an experiment involving rolling a six-sided die, what is the probability that the number is even? We can do this via map!

Write the method map that takes in an an appropriate Function and returns the resulting Dist object.

jshell> Dist.<Integer>of(List.of(1,2,3,4,5,6)).
   ...> map(x -> x % 2).
   ...> forEach()
Event[1, 0.500]
Event[0, 0.500]

Now write a method filter that takes in a predicate and removes all occurrences in the distribution that violates the predicate.

jshell> Dist.<Integer>of(List.of(1,2,3,4,5,6)).
   ...> filter(x -> x % 3 != 0)
$.. ==> [1, 2, 4, 5]

jshell> Dist.<Integer>of(List.of(1,2,3,4,5,6)).
   ...> filter(x -> x % 3 != 0).
   ...> forEach()
Event[1, 0.250]
Event[2, 0.250]
Event[4, 0.250]
Event[5, 0.250]

jshell> Dist.<Integer>of(List.of(1,2,3,4,5,6)).
   ...> map(x -> x % 2).
   ...> filter(x -> x == 0).
   ...> forEach()
Event[0, 1.000]

Level 4

Thus far, the experiment involves a simple action, i.e. a flip or a roll. We are now ready to combine distributions.

Write the method flatMap that takes in an an appropriate Function that allows us to combine the probability distributions, and returns the resulting Dist object.

jshell> Dist<String> toss = Dist.<String>of(List.of("H","T"))
toss ==> [H, T]

jshell> toss.flatMap(x -> toss.map(y -> x + y))
$.. ==> [HH, HT, TH, TT]

jshell> toss.flatMap(x -> toss.map(y -> x + y)).
   ...> forEach()
Event[HH, 0.250]
Event[HT, 0.250]
Event[TH, 0.250]
Event[TT, 0.250]

jshell> Dist<Integer> roll = Dist.of(List.of(1,2,3,4,5,6))
roll ==> [1, 2, 3, 4, 5, 6]

jshell> roll.flatMap(x -> roll.map(y -> x + y)).
   ...> forEach()
Event[2, 0.028]
Event[3, 0.056]
Event[4, 0.083]
Event[5, 0.111]
Event[6, 0.139]
Event[7, 0.167]
Event[8, 0.139]
Event[9, 0.111]
Event[10, 0.083]
Event[11, 0.056]
Event[12, 0.028]

One can also perform an experiment of tossing a coin followed by rolling a die, or vice-versa.

jshell> toss.flatMap(x -> roll.map(y -> x + y))
$.. ==> [H1, H2, H3, H4, H5, H6, T1, T2, T3, T4, T5, T6]

jshell> roll.flatMap(x -> toss.map(y -> x + y))
$.. ==> [1H, 1T, 2H, 2T, 3H, 3T, 4H, 4T, 5H, 5T, 6H, 6T]

Now write a roll method that takes in a positive integer n and performs the experiment n times. The method should also take in a BinaryOperator to represent the resulting event.

jshell> Dist<String> toss = Dist.<String>of(List.of("H","T"))
toss ==> [H, T]

jshell> toss.roll(1, (x,y) -> x + y)
$.. ==> [H, T]

jshell> toss.roll(2, (x,y) -> x + y)
$.. ==> [HH, HT, TH, TT]

jshell> toss.roll(3, (x,y) -> x + y)
$.. ==> [HHH, HHT, HTH, HTT, THH, THT, TTH, TTT]

jshell> toss.roll(3, (x,y) -> x + y).
   ...> forEach()
Event[HHH, 0.125]
Event[HHT, 0.125]
Event[HTH, 0.125]
Event[HTT, 0.125]
Event[THH, 0.125]
Event[THT, 0.125]
Event[TTH, 0.125]
Event[TTT, 0.125]

Here is an example for an unfair coin.

jshell> toss = Dist.<String>of(List.of("H","H","T"))
toss ==> [H, T]

jshell> toss.forEach()
Event[H, 0.667]
Event[T, 0.333]

jshell> toss.roll(1, (x,y) -> x + y).
   ...> forEach()
Event[H, 0.667]
Event[T, 0.333]

jshell> toss.roll(2, (x,y) -> x + y).
   ...> forEach()
Event[HH, 0.444]
Event[HT, 0.222]
Event[TH, 0.222]
Event[TT, 0.111]

jshell> toss.roll(3, (x,y) -> x + y).
   ...> forEach()
Event[HHH, 0.296]
Event[HHT, 0.148]
Event[HTH, 0.148]
Event[HTT, 0.074]
Event[THH, 0.148]
Event[THT, 0.074]
Event[TTH, 0.074]
Event[TTT, 0.037]

Level 5

Now we solve some probability problems. Write your answers in level5.jsh.

• Write a toss method that takes in a distribution comprising string outcomes "H" and "T" that represents the toss of a coin, and tosses the coin n times. The method returns the probability distribution of different outcomes of the number of heads and tails, irrespective of it's order.

  jshell> toss(Dist.<String>of(List.of("H","T")), 3)
  $.. ==> [HHH, HHT, HTT, TTT]
  
  jshell> toss(Dist.<String>of(List.of("H","T")), 3).
     ...> forEach()
  Event[HHH, 0.125]
  Event[HHT, 0.375]
  Event[HTT, 0.375]
  Event[TTT, 0.125]
  

  Hint: Use string concatenation. You are NOT ALLOWED to make use of methods from any Java library, including String methods to construct another string.

• Write the method atLeastTwoSixes that takes in a distribution of integer outcomes when rolling a die, and returns the probability of getting at least two sixes after rolling n times. For example, when n is 4,

  jshell> atLeastTwoSixes(Dist.<Integer>of(List.of(1,2,3,4,5,6)), 4)
  $.. ==> 0.1319444444444444
  

  Hint: Use only arithmetic operations. You are NOT ALLOWED to make use of methods from any Java library.