Tossing coins

Simulate a biased coin with a fair coin

The following algorithm simulates a biased coin with head probability 0<p<1, using a random number generator toss_coin that returns 0 and 1 with equal probability.

// Pre-condition: p is a rational number and 0 < p < 1
while (true) {
    var p = p * 2,
    var p2 = p - floor(p);
    var msb = p - p2;
    var random_bit = toss_coin(); // 0 or 1
    if (random_bit < msb) {
        print "head";
        break;
    }
    if (random_bit > msb) {
        print "tail";
        break;
    }
    p = p2;
}
// Post-condition: "head" is outputted with probability p
//                 "tail" is outputted with probability 1-p

To see why it works, consider a random number 0 < r < 1 generated by enumerating its binary representation with a fair coin. Observe that given 0 < p < 1, the probability that 0 < r < p is exactly p. The algorithm then enumerates p and r, digit by digit, and determines the return value according to the following fact: r < p if and only if r_i < p_i for some i and r_j = p_j for all j < i, where x_k denotes the kth digit in the binary representation of x.

The following code fragment is adapted from the book Abstraction, Refinement and Proof for Probabilistic Systems, A McIver, C Morgan, 2005. Succinct as it is, its behavior is not as straightforward to understand as the above one and we skip the analysis of its correctness.

// Pre-condition: p is a rational number and 0 < p < 1
var x = p;
while (toss_coin() == 1) {
    x = 2 * x;
    if(x > 1){
      x = x - 1;
    }
}
// Post-condition: x > 0.5 with probability p
print x > 0.5 ? "head" : "tail";

Simulate a fair coin with a biased coin

while (true) {
    var a = toss_biased_coin();
    var b = toss_biased_coin();
    if(a == b){
      print a == 1 ? "head" : "tail";
      break;
    }
}

The expected running time is $\frac{2}{1-2p(1-p)}$.

Checking whether a coin is fair

First, note that it is impossible to rule out arbitrarily small deviations from fairness such as might be expected to affect only one flip in a lifetime of flipping. Also, it is always possible for a biased coin to happen to turn up exactly 10 heads in 20 flips. As such, any fairness test must only establish a certain degree of confidence in a certain degree of fairness (a certain maximum bias). In more rigorous terminology, this problem can be viewed as a special case of determining the parameters of a Bernoulli process, given only a limited sample of Bernoulli trials.
Suppose that there are $h$ heads and $t$ tails in an experiment of $n=h+t$ tosses. The best estimator for the actual head probability $p$ is $$q=\frac{h}{h+t}.$$ One can associate this estimator with a margin of error $\epsilon$ at a particular confidence level, which is given by the Z-value of a standard normal distribution in the following sense: $$P\{|p-q|\le z\sigma\}=P\{|Z|\le z\},$$ where $\sigma$ is the standard deviation of error of the estimate and $Z$ is a standard-normal distributed random variable. For $n$ Bernoulli trials, the standard deviation is $$\sigma=\sqrt{\frac{p(1-p)}{n}}\le\frac{1}{2\sqrt n}.$$ Hence, suppose that $P\{|Z|\le z\}=c$ then we have $$P\{|p-q|\le \frac{z}{2\sqrt n}\}\ge c.$$ For example, by looking up the table we see that $z=2.5759$ for $c=99\%$. Suppose now $h=54$ and $t=46$, then the actual head probability $p$ falls into $0.54\pm 0.12879$ at 99% level of confidence.

Scala: Applications of implicit constructs

Prefix-to-Infix conversion. Suppose we have $F: Int \rightarrow Double \rightarrow Boolean$ and we would like to define an infix operator $\otimes$ such that $a \otimes b = F(a, b)$. The infix call is technically interpreted as a.⊗(b), so we have to add a $\otimes$ method to class Int. However, we cannot do this easily because Int is defined in the core Scala library. This situation is where Scala's implicit conversion can come to play: an implicit class defined as follows would perfectly serve our purpose:

implicit class Converter(b: Double) {
  def ⊗(a: Int): Boolean = F(a, b)
}

Note that the class name doesn't matter. The point is to use the keyword implicit and provide the function $\otimes$ with the correct signature. Now, when the compiler encounters something like a⊗b and tries to resolve the method call, it does not find a method named "$\otimes$" in class Int. It will then look for any implicit conversions it could use to transform a into something that has a method named "$\otimes$" with an applicable signature. Assuming our Converter class is in the right scope, the compiler will implicitly construct a Converter object from a and call $\otimes$ on that object instead.
PS. Scala defines a default converter from type Any to type String, which simply invokes the toString method of Any.

Type classes. Suppose we have a function $F: A \rightarrow B$ and we would like it to work only for a restricted subset $A'$ of $A$. There is no way to express such type constraint through inheritance. In Scala, however, we can use the type class pattern to set the constraint. Here is the idea: 1) create an abstract class that will represent a type class, 2) create elements representing the classes belonging to that type class, and 3) use an implicit parameter to restrict the type parameter of $F$ to that type class.
More concretely, suppose $A$ is the Numeric type and we would like $F$ to work only for Int and Long, but not any other subtype of Numeric. We first define an abstract type class:

abstract class Acceptable[T]

Next, we create the members of the type class, one for Int and another for Long. To make them available without need for import statements, we put them inside the companion class to Acceptable.

object Acceptable {
  implicit object AllowInt extends Acceptable[Int]
  implicit object AllowLong extends Acceptable[Long]
}

Finally, we allow $F$ to accept only type Int and Long by letting it take an implicit parameter:

def F[T](t: T)(implicit constraint: Acceptable[T]) = ...

Now, if you try to call $F(x)$ on an argument $x$ of type other than Int and Long, you will get an error at compile time, because the compiler cannot find the implicit object for that type. You can increase the number of allowed types by defining new implicit objects in the right scope.