QuickCheck’s CoArbitrary – generate random functions!

Property based testing is a great way to improve code quality since it captures logical properties of your system. Instead of writing test cases by hand, you capture logical relationships and then let the test framework generate hundreds or thousands of examples for you.

For a general introduction to property based testing (language-independent), try this YOW! Night talk Property Based Testing Finding More Bugs with Less Effort by Charles O’Farrell.

QuickCheck provides a typeclass CoArbitrary for generating random functions. In this blog post we derive CoArbitrary in a standalone setting. For the real definition, see Test.QuickCheck. Source code for this post is here.

Some imports:


> {-# LANGUAGE InstanceSigs #-}
> {-# LANGUAGE RankNTypes   #-}
> 
> module Sample where
> 
> import Control.Applicative
> import Control.Monad
> import System.Random

First, a generator of type Gen a lets us use a random number generator to get a value of type a:


> newtype Gen a = Gen
>     { unGen :: StdGen -> a }

(The real Gen in QuickCheck is parameterised over the generator, but we don’t need that here. Also, the real Gen includes a size, which you can control using resize or scale).

The Arbitrary typeclass:


> class Arbitrary a where
>     arbitrary :: Gen a

Since False < True (there is an instance of Ord for Bool) we can use randomR to define arbitrary for Bool:


> instance Arbitrary Bool where
>     arbitrary = Gen $ \stdgen ->
>       let (r, _) = randomR (False, True) stdgen in r

Here’s a first attempt at implementing Gen (Bool -> Bool), a generator for boolean functions:


> genBoolFn0 :: Gen (Bool -> Bool)
> genBoolFn0 = Gen $ \stdgen ->
>   \a -> let (r, _) = randomR (False, True) stdgen in r

The type is right but it’s going to generate pretty boring functions since it doesn’t even use the a:


> runBoolFnGen :: Gen (Bool -> Bool) -> IO ()
> runBoolFnGen g = do
>   fns  <- samples g
> 
>   forM_ fns  $ \f -> do
>     putStrLn $ "True  => " ++ show (f True)
>     putStrLn $ "False => " ++ show (f False)
>     putStrLn ""

The functions are either const True or const False. Not useful.


ghci> runBoolFnGen genBoolFn0 
True  => True
False => True

True  => False
False => False

True  => False
False => False

True  => True
False => True

True  => False
False => False

True  => True
False => True

True  => False
False => False

True  => False
False => False

True  => False
False => False

We need to split on the a somehow:


> genBoolFn1 :: Gen (Bool -> Bool)
> genBoolFn1 = Gen $ \stdgen -> \a -> case a of
>   True  -> let (r, _) = randomR (False, True) stdgen in r
>   False -> let (r, _) = randomR (False, True) stdgen in r

This isn’t any better. The other thing we can change is the generator. Fortunately, StdGen is an instance of RandomGen, so we have the split function:


> -- The split operation allows one to obtain two
> -- distinct random number generators. This is
> -- very useful in functional programs (for example,
> -- when passing a random number generator down to
> -- recursive calls), but very little work has been done
> -- on statistically robust implementations of split
> -- ([System.Random, System.Random] are the only
> -- examples we know of).
> 
> split :: StdGen -> (StdGen, StdGen)
> split = ...

Taking advantage of laziness, we can use split to write a pure function that gives us an infinite sequence of statistically distinct generators:


> splitGenerator :: RandomGen a => a -> [a]
> splitGenerator r = r0 : splitGenerator r1
>   where
>     (r0, r1) = split r

This is exactly what we need to permute the generator in genBoolFn1. Let’s map True to the generator at index 0 and False to to the generator at index 1:


> genBoolFn2 :: Gen (Bool -> Bool)
> genBoolFn2 = Gen $ \stdgen -> \a -> case a of
>   True  -> let (r, _) = randomR
>                           (False, True)
>                           (splitGenerator stdgen !! 0)
>             in r
>   False -> let (r, _) = randomR
>                           (False, True)
>                           (splitGenerator stdgen !! 1)
>             in r

Now the random functions look more random:


ghci> runBoolFnGen genBoolFn2
True  => False
False => True

True  => True
False => False

True  => False
False => True

True  => True
False => False

True  => True
False => True

True  => True
False => False

True  => True
False => True

True  => False
False => False

True  => False
False => True

So, what about random integer functions Int -> Int? We need to map any integer to one of the split generators, in other words we need a mapping $\mathbb{N} \rightarrow \mathbb Z_{\ge 0}$. Send the non-negative integers to the non-negative even integers, and the negative integers to the positive odd integers:

\[
n \rightarrow
\begin{cases}
2n & \mbox{if } n \geq 0 \\
2(-n) + 1 & \mbox{if } n < 0 \end{cases} \]

In Haskell this looks like:


> \n -> variant $ if n >= 0 then 2*n else 2*(-n) + 1

where


> variant :: Int -> Gen b -> Gen b
> variant v (Gen g) = Gen $ \r -> g $ splitGenerator r !! (v+1)

Capture this with a typeclass:


> class CoArbitrary a where
>     coarbitrary :: a -> Gen b -> Gen b
> 
> instance CoArbitrary Bool where
>   coarbitrary False = variant 0
>   coarbitrary True  = variant 1
> 
> instance CoArbitrary Int where
>     coarbitrary n = variant $ if n >= 0 then 2*n else 2*(-n) + 1

With some experimentation we can extend the CoArbitrary definitions to lists and tuples:


> instance CoArbitrary a => CoArbitrary [a] where
>   coarbitrary []     = variant 0
>   coarbitrary (x:xs) = variant 1 . coarbitrary (x, xs)
> 
> instance (CoArbitrary a, CoArbitrary b) => CoArbitrary (a, b) where
>   coarbitrary (x, y) = coarbitrary x . coarbitrary y

In general, if we have CoArbitrary a and Arbitrary b then we can derive Arbitrary (a -> b):


> instance (CoArbitrary a, Arbitrary b) => Arbitrary (a -> b) where
>     arbitrary = promote (\a -> coarbitrary a arbitrary)
> 
> promote :: (a -> Gen b) -> (Gen (a->b))
> promote f = Gen $ \r ->
>   \a -> let Gen h = f a
>          in h r

Here are more examples of random functions:


> runGenFn :: (Arbitrary a, Arbitrary b, Show a, Show b)
>          => Gen (a -> b)
>          -> [a]
>          -> IO ()
> runGenFn g as = do
>   fns  <- samples g
> 
>   forM_ fns  $ \f -> do
>     forM_ as $ \a -> putStrLn $ show a ++ " => "
>                                        ++ show (f a)
>     putStrLn ""

Running in ghci:


ghci> runGenFn (arbitrary :: Gen (Int -> Int)) [0, 1, 2]
0 => 198
1 => 940
2 => -200

0 => 734
1 => -627
2 => 6

0 => 965
1 => 581
2 => -585

0 => -306
1 => -918
2 => 678

0 => -929
1 => 336
2 => -696

0 => -66
1 => 123
2 => 875

0 => -234
1 => -673
2 => 216

0 => 355
1 => 56
2 => -615

0 => 278
1 => 116
2 => 967

ghci> runGenFn (arbitrary :: Gen (Int -> Bool)) [0, 1, 2]
0 => False
1 => True
2 => False

0 => True
1 => False
2 => True

0 => True
1 => False
2 => False

0 => True
1 => False
2 => False

0 => True
1 => True
2 => True

0 => True
1 => True
2 => False

0 => False
1 => True
2 => False

0 => True
1 => True
2 => False

0 => True
1 => True
2 => True

ghci> runGenFn (arbitrary :: Gen ([Int] -> [Int])) [[42], [0, 1, 2]]
[42] => [-93,-540,-715,-557,-249]
[0,1,2] => [433,97,665,554,-690,635]

[42] => [-785,174,-676,-662,-549]
[0,1,2] => [-735,-328,226,-524,423]

[42] => [157,976,-774]
[0,1,2] => [-197,608,-520,-37,-689]

[42] => [-684]
[0,1,2] => [902,-138,-33,689,-774,-713,474,-638]

[42] => [-782,540,649,320,-326,92,896,-76]
[0,1,2] => [156]

[42] => [524,137]
[0,1,2] => [642,-763,771,-400,825,71,895,586,252,37]

[42] => [641,-304,-890,-375,449,-608,662,546,-740,-406]
[0,1,2] => [-632,-685,-232,202,-994,666,-121]

[42] => [200,599,-844]
[0,1,2] => [-554,149,370,547,-755,-706,131]

[42] => [-898,645,-472]
[0,1,2] => [-77]

Appendix

To get the code above to work we need instances for Monad, Functor, and Applicative. These are all lifted from Test.QuickCheck.


> instance Monad Gen where
>     return :: a -> Gen a
>     return a = Gen $ \_ -> a
> 
>     (>>=) :: Gen a -> (a -> Gen b) -> Gen b
> 
>     (Gen g) >>= f = Gen $ \r ->
>        let (r1, r2) = split r
>            Gen k = f $ g r1
>         in k r2
> 
> instance Functor Gen where
>     fmap f (Gen h) = Gen $ \r -> f (h r)
> 
> instance Applicative Gen where
>     pure x = Gen $ \_ -> x
> 
>     f <*> x = do
>         f' <- f
>         x' <- x
>         return $ f' x'
> 
> generate :: Gen a -> IO a
> generate (Gen g) = do
>     stdgen <- getStdGen
>     return $ g stdgen

Use sequence to get a few samples. Note that this relies on the Applicative instance’s definition of <*> to get a new standard number generator each time it is used, which in turn uses the Monad instance’s definition which uses split.


> samples :: Gen a -> IO [a]
> samples g = generate $ sequence [g, g, g, g, g, g, g, g, g]

> instance Arbitrary Int where
>   arbitrary = Gen $ \stdgen ->
>     let (r, _) = randomR (-1000, 1000) stdgen in r
> 
> choose :: Random a => (a,a) -> Gen a
> choose range = Gen $ \stdgen ->
>   let (r, _) = randomR range stdgen in r
> 
> vectorOf :: Int -> Gen a -> Gen [a]
> vectorOf = replicateM
> 
> listOf :: Gen a -> Gen [a]
> listOf g = do
>   k <- choose (1, 10)
>   vectorOf k g
> 
> instance Arbitrary a => Arbitrary [a] where
>   arbitrary = listOf arbitrary

Pricing an option on a cumulative sum.

Consider an option with payout on an underlying which is a cumulative sum. For example, a construction company might want to mitigate the risk of rainfall causing delays in a project. The construction company could buy a call option on the cumulative sum of rainfall not exceeding 180mm on any 3-day period. Further, we restrict this so that one day can only be used in one payoff. If the cumulative rainfall $r$ a 3-day period exceeded 180mm, the entity selling the call option would have the obligation to pay the construction company based on the difference $r – 180$.

As the entity selling one of these options, we need to work out the expected loss and worst possible scenario for payouts.

Let $r_0, r_1, \ldots$ be the sequence of daily rainfall. Form the 3-sums:

\[
s_0 = r_0+r_1+r_2, s_1 = r_1+r_2+r_3, s_2 = r_2+r_3+r_4, \ldots
\]

Let $C > 0$ be the cutoff (e.g. 180mm/day). Then form the sequence $w_0, w_1, \ldots$ where

\[
w_i = f_C(s_i)
\]

where $f_C(x)$ is $0$ if $x \leq C$ and $x$ otherwise.

As the seller of the option, the worst outcome for us (i.e. largest payout) corresponds to the subsequence

\[
w_{k_1}, w_{k_2}, \ldots w_{k_n}
\]

that maximises the sum $\sum_{l=1}^n w_{k_l}$ for some $n$, where the terms $w_{k_l}$ are mutually disjoint (i.e. we don’t take the 3-sum of any days that overlap). We consider this sum over one year, but the same approach applies to monthly, quarterly, etc.

Formulation as a graph problem

Label vertices with the 3-sums $w_i$ and create an edge $(w_i, w_j)$ if the sums $w_i$ and $w_j$ refer to overlapping time periods. Then our problem is equivalent to finding a Maximum Weighted Independent Set in the graph. This is a classic NP-hard problem.

Formulation as a linear programming problem

Create binary decision variables $x_0, x_1, \ldots$ and optimise

\[ \sum{w_i x_i} \]

subject to

\[
x_i + x_j \leq 1
\]

when $w_i$ and $w_j$ refer to non-disjoint cumulative 3-sums.

Python solver

Using PuLP we can very quickly write a solver in Python.

First set up a solver:

prob = pulp.LpProblem('maxcsums', pulp.LpMaximize)

Create binary variables corresponding to each vertex:

x_vars = [ pulp.LpVariable('x' + str(i), cat='Binary')
             for (i, _) in enumerate(weights) ]

Use reduce to form the sum \( \sum w_i x_i \):

prob += reduce(lambda a,b: a+b,
                   [ weights[i]*x_vars[i] for i in range(len(weights))])

Finally, given a list of indices (3-tuples), add the constraints to avoid solutions with adjacent vertices:

for (i, x) in enumerate(indices):
  for (j, y) in enumerate(indices):
    if x < y:
      if is_adjacent(x, y):
        prob += x_vars[i] + x_vars[j] <= 1

Changi daily rainfall

For a concrete example, let’s use the daily rainfall data for Changi in Singapore.

Here are the 3-sums:



For cutoffs from 100 to 300, here are the number of extreme events per year:

     100 120 140 160 180 200 220 240 260 280 300
1980   3   3   2   1   1   1   1   1   1   0   0
1981   1   1   1   1   0   0   0   0   0   0   0
1982   2   1   1   1   1   1   1   1   0   0   0
1983   2   2   2   2   2   1   0   0   0   0   0
1984   6   4   2   1   1   1   0   0   0   0   0
1985   1   1   0   0   0   0   0   0   0   0   0
1986   4   4   4   3   1   0   0   0   0   0   0
1987   4   3   2   2   1   1   1   1   1   0   0
1988   9   4   2   1   1   0   0   0   0   0   0
1989   3   1   1   1   1   1   1   1   0   0   0
1990   2   1   1   1   0   0   0   0   0   0   0
1991   4   3   1   0   0   0   0   0   0   0   0
1992   6   3   2   2   1   1   1   0   0   0   0
1993   1   0   0   0   0   0   0   0   0   0   0
1994   4   3   2   2   2   1   0   0   0   0   0
1995   3   3   3   2   2   2   1   0   0   0   0
1996   1   0   0   0   0   0   0   0   0   0   0
1997   0   0   0   0   0   0   0   0   0   0   0
1998   3   3   1   1   0   0   0   0   0   0   0
1999   2   0   0   0   0   0   0   0   0   0   0
2000   2   2   0   0   0   0   0   0   0   0   0
2001   5   3   2   2   2   2   2   2   2   1   0
2002   4   1   1   1   1   0   0   0   0   0   0
2003   5   1   1   1   1   1   0   0   0   0   0
2004   6   4   2   2   1   1   1   0   0   0   0
2005   2   1   1   1   0   0   0   0   0   0   0
2006   5   5   5   5   3   2   2   1   1   1   1
2007   7   5   4   3   1   1   1   1   1   0   0
2008   4   3   1   0   0   0   0   0   0   0   0
2009   1   1   0   0   0   0   0   0   0   0   0
2010   4   1   0   0   0   0   0   0   0   0   0
2011   4   2   1   1   1   1   1   1   1   1   0
2012   3   0   0   0   0   0   0   0   0   0   0
2013   5   3   3   1   0   0   0   0   0   0   0
2014   0   0   0   0   0   0   0   0   0   0   0
2015   0   0   0   0   0   0   0   0   0   0   0
2016   1   0   0   0   0   0   0   0   0   0   0

We will go with 180mm as the cutoff. Ultimately, choosing the strike is a business decision.

The burn is $\texttt{max}(w_i – 180, 0)$, indicating the payout that the seller of the option would be liable for. Here is the daily burn for Changi daily rainfall (zero rows are not shown):

            c3sum   burn
DATE                    
1980-01-20  275.5   95.5
1982-12-22  245.4   65.4
1983-08-22  190.6   10.6
1983-12-26  218.8   38.8
1984-02-02  219.3   39.3
1986-12-11  186.7    6.7
1987-01-11  260.5   80.5
1988-09-21  188.9    8.9
1989-12-01  252.5   72.5
1992-11-11  223.2   43.2
1994-11-11    209   29.0
1994-12-19  180.7    0.7
1995-11-02  203.4   23.4
1995-02-06  236.9   56.9
2001-01-16  268.7   88.7
2001-12-27  281.4  101.4
2002-01-25  182.1    2.1
2003-01-31  210.5   30.5
2004-01-25  237.9   57.9
2006-12-19  356.4  176.4
2006-12-26  222.7   42.7
2006-01-09  190.7   10.7
2007-01-12  260.4   80.4
2011-01-31  298.2  118.2

The yearly burn is $\sum_i{\texttt{max}(w_i-180,0)}$ where the $w_i$ are in a particular calendar year. Plotting the yearly burn:



The histogram of burn values shows that a value around $80$ is the most frequent total yearly burn:



Cumulative histogram of the yearly burn:



From the yearly burn we can compute the expected loss over various periods:


Expected loss (all years):     71.13
Expected loss (last 10 years): 86.22
Expected loss (last 20 years): 71.13

We see that the expected loss over the last 10, 20 years differs by about 15.0.
The 99th percentile is p99 = 223.051.

Unlike pricing options on a liquid instrument such as an interest rate swap, stock, currencies, etc, the pricing of this option is set in an incomplete market. There is no way to hedge, so the Black Scholes formula cannot be used. Typically the price will be set as

\[
f(\texttt{expected loss}, \texttt{high value on the tail})
\]

where the high value on the tail is p99 or p99.9 (or similar); the function $f$ will integrate the price maker’s risk appetite, but it will be approximately

\[
\texttt{option price} \approx \texttt{expected loss} + \Delta
\]

Notes

Source code is on Github: https://github.com/carlohamalainen/maxc3sum

Most of the data manipulation is done using Python Pandas which makes lots of things one-liners, e.g. to sum the daily burn to yearly burn, given an index of datetime.date, we can group by year and then sum the result:

    yearly_burn = daily_burn.groupby(lambda x: x.year).sum()

To set the gap for GLPK, pass the command line option when setting up the initial GLPK object:

    pulp.GLPK(options=['--mipgap', 0.1]).solve(prob)

Naturally, finding a good gap is problem-specific and requires some experimentation.