People don’t sit on Park Benches at Random

As I was approaching Berkeley Square at lunchtime on Thursday, I noticed a pattern in the way that the people were sitting on the park benches.

2014-03-13 12.45.16-small

Even though it was a sunny day, the square was not very full, and there were about twice as many bench seats as there were people. Nobody wanted to sit too close to another stranger (this is London, after all), so they sat the maximum distance apart that they could. This resulted in evenly distributed people – Empty, Person, Empty, Person, and so on. The sequence cannot be called random because the people are actively deciding where to sit.

I decided to look at a simple random sequence in F#.

To start off with, I decided to define a type for my program. This might not sound like a promising starting point for a program, but in F# it’s so painless that it is a good way to begin thinking about the domain and what states make sense in your domain. For more on this, see Scott Wlaschin’s slides on Domain Driven Design in F#.

My domain is coin tossing. Therefore, I created the following discriminated union in F# interactive:

> type CoinToss = Tails | Heads;;
 
type CoinToss =
  | Tails
  | Heads

This allows a coin toss to be either heads or tails but not both or neither. Static typing allows the program to make definite statements about the world.

I also needed a random number generator:

> let r = System.Random();;
 
val r : System.Random

F# allows you to define infinite sequences that can be evaluated lazily. The following is a potentially infinite sequence of random coin tosses.

> let coins = Seq.initInfinite (fun _ -> if r.Next(2) = 0 then Heads else Tails);;
 
val coins : seq<CoinToss>

r.Next(2) means the next random integer less than 2 but greater than or equal to 0, that is a random 0 or 1.

If the idea of an infinite sequence of coin tosses sounds weird and unruly, here’s how we can make use of them. The take function allows us to tame infinity. Or at least take a little bit of it.

The following says “Take 10 of the randomly generated coins and pass them along (|>) to a function that iterates through them one at a time and prints them out”

> Seq.take 10 coins |> Seq.iter (printfn "%A");;
Heads
Heads
Tails
Heads
Heads
Tails
Tails
Heads
Tails
Tails
val it : unit = ()

That sequence is not very dissimilar from the lunchers on the park benches in the photo above. There are no long clusters of one thing (person, heads, etc.) or another (empty seat, tails, etc.).

However, this isn’t always the case:

> Seq.take 10 coins |> Seq.iter (printfn "%A");;
Tails
Tails
Heads
Heads
Heads
Tails
Heads
Tails
Heads
Heads
val it : unit = ()

or even:

> Seq.take 10 coins |> Seq.iter (printfn "%A");;
Tails
Tails
Tails
Tails
Tails
Heads
Heads
Heads
Heads
Heads
val it : unit = ()

Five tails followed by five heads looks completely fixed. In a casino, you might start to get worried. But it happened. Trust me.

One way to check if the coin is being tossed fairly, is to count how many times each face lands. This function does that:

> let rec countCoins coins (heads, tails) = 
    match coins with 
    | [] -> heads, tails
    | hd :: tl ->
        let newCounts =
            match hd with
            | Heads -> heads + 1, tails
            | Tails -> heads, tails + 1
        countCoins tl newCounts;;
 
val countCoins : coins:CoinToss list -> heads:int * tails:int -> int * int

The way to read this function is as follows.

If the argument coins matches an empty list, return the counts for heads and tails as they are.

Otherwise, coins must be a list with a first element (hd) and the remaining part of the part of the list (tl), which might be an empty list. We need to find the new counts of heads or tails by adding 1 to either count. Finally, we call the countCoins function again with the remainder of the list (tl). This will continue until we have stripped all the first elements from the list and tl is an empty list. The function then terminates as we have satisfied the first condition above.

For convenience, I defined a function that gets a number of coin tosses and puts them into a list to be counted:

> let getCoins numberOfCoins = Seq.take numberOfCoins coins |> Seq.toList;;
 
val getCoins : numberOfCoins:int -> CoinToss list

For a short list, the counts for each face might not be equal:

> countCoins (getCoins 10) (0, 0);;
val it : int * int = (6, 4)

Note that the counts for heads and tails start off as zeroes.

However, with a larger number of coins (in this case, pown 10 7 or 10 to the power of 7 or 10 million), the counts should both approach half the number of tosses:

> countCoins (getCoins (pown 10 7)) (0, 0);;
val it : int * int = (4997646, 5002354)

Leave a Reply