Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Imperative programming / 8

For Uniform, require a nonempty integer interval. Compute its size in Long before converting to Double, avoiding integer overflow in u-l+1. For Flip, require

0 \leq p \leq 1

, and omit zero-probability outcomes from the reported support.

class Uniform(l: Int, u: Int) extends FiniteDist[Int] {
  require(l <= u)
  private val size = u.toLong - l.toLong + 1L
  def getDom: List[Int] = {
    val result = List.newBuilder[Int]
    var x = l.toLong
    while (x <= u.toLong) { result += x.toInt; x += 1L }
    result.result()
  }
  def getProb(x: Int): Double =
    if (l <= x && x <= u) 1.0 / size.toDouble else 0.0
}

class Flip(p: Double) extends FiniteDist[Boolean] {
  require(0.0 <= p && p <= 1.0)
  def getDom: List[Boolean] =
    if (p == 0.0) List(false)
    else if (p == 1.0) List(true)
    else List(true, false)
  def getProb(x: Boolean): Double = if (x) p else 1.0-p
}

The first is a discrete uniform distribution; the second is a Bernoulli distribution on Boolean values. Their exact mathematical probability mass functions are

p_{U} (x) = ⎩ ⎨ ⎧ \frac{1}{u - l + 1} 0 l \leq x \leq u, otherwise, p_{F} (true) = p, p_{F} (false) = 1 - p .

(1)

Each support contains exactly the positive-probability outcomes once, and the probabilities sum to one. Double approximates these exact values by floating-point arithmetic. Materializing a huge support is limited by available memory; the Long calculation keeps its cardinality and endpoints arithmetically correct.

b

 0  0

Solution

 0  0

Reject the empty string, because the given formula would divide by zero and no normalized probability distribution exists on its empty observed support. Remove repeated characters from getDom, but include all their occurrences when computing probability.

class DistFromString(s: String) extends FiniteDist[Char] {
  require(s.nonEmpty)
  private val chars = s.toList
  private val dom = chars.distinct
  def getDom: List[Char] = dom
  def getProb(x: Char): Double =
    chars.count(c => c == x).toDouble / chars.length.toDouble
}

The probability mass function is an empirical probability distribution:

p (c) = \frac{# { i : s _{i} = c }}{∣ s ∣} .

(1)

Every character occurrence contributes exactly once to the total count, so the probabilities sum to one. Absent characters have count zero. For "Scala", the support is List('S','c','a','l'), with probabilities

1/5, 1/5, 2/5, 1/5

respectively. Here Char means the language's UTF-16 code unit, matching the supplied interface rather than assuming one Unicode code point per element.

c

 0  0

Solution

 0  0

Define an implicit conversion in the scope where client code uses the added methods:

import scala.language.implicitConversions

implicit def stringToDist(s: String): DistFromString =
  new DistFromString(s)

Then, for example,

val support = "Scala".getDom
val p = "Scala".getProb('a')

The Scala compiler can convert the receiver to DistFromString when the requested member is absent from String. The conversion must be imported or otherwise visible, and constructing the finite probability distribution retains the nonempty-string precondition of part (b).

implicit def stringToDist(s: String): DistFromString .

(1)

d

 0  0

Solution

 0  0

For the product of finite probability distributions, enumerate the Cartesian product of the two supports and multiply the two probability masses.

def product[T,U](d: FiniteDist[T], d2: FiniteDist[U]): FiniteDist[(T,U)] =
  new FiniteDist[(T,U)] {
    private val dom = for (x <- d.getDom; y <- d2.getDom) yield (x,y)
    def getDom: List[(T,U)] = dom
    def getProb(p: (T,U)): Double = d.getProb(p._1) * d2.getProb(p._2)
  }

Each pair appears once because both original supports have no duplicates. Exact probabilities are positive on that support, and normalization follows by finite distributivity:

\sum_{x, y} p_{1} (x) p_{2} (y) = (\sum_{x} p_{1} (x)) (\sum_{y} p_{2} (y)) = 1.

(1)

For the pushforward of a finite probability distribution, sum all masses in each fiber of a function; simply overwriting repeated image values would lose probability.

def image[T,U](d: FiniteDist[T], f: T => U): FiniteDist[U] =
  new FiniteDist[U] {
    private val weighted = d.getDom.map(x => (f(x), d.getProb(x)))
    private val dom = weighted.map(_._1).distinct
    def getDom: List[U] = dom
    def getProb(y: U): Double =
      weighted.foldLeft(0.0) { case (total, (z,p)) =>
        if (z == y) total+p else total
      }
  }

Assume the given finite probability distributions are fixed and f is a pure total function on the source support. Distinct image values form exactly the positive-mass support. The fibers partition the original support, proving