Randomized Algorithms

Random Numbers

Up until now, every date structure and algorithm has been deterministic. Randomized algorithms are exactly the same.

1mkStdGen :: Int -> StdGen
2random :: Random a => StdGen -> (a, StdGen)
3randomR :: Random a => StdGen -> (a, a) -> (a, StdGen)

These two random functions, given a seed, will produce a "random" value and a new seed. We can use these functions as:

1-- A list of random numbers
2rs :: [Int]
3rs = unfoldr (Just . random) $ mkStdGen 42

There are two kinds of randomised alogrithms:

• Monte Carlo produces, given a fixed time, a random answer. Given more time, it would get closer to the exact answer.
• Las Vegas produces an answer within a certain probability of being correct, but may take a random amount of time to get there.

A classic monte-carlo algorithm is calculating :

1inside :: (Double, Double) -> Boolean
2inside (x, y) = x^2 + y^2 <= 1
3
4montePi :: Int -> Double
5montePi !darts = go (mkStdGen 4) darts 0
6  where go :: StdGen -> Int -> Int -> Double
7        go _ 0 hits = 4 * fromIntegral inside / fromIntegral darts
8        go gen n hits
9          | inside p  = go seed' (n-1) (hits+1)
10          | otherwise = go seed' (n-1) hits
11          where (p, seed') = randomR ((0, 0), (1, 1)) gen

Treaps

A heap is a structure where smaller values float to the top and larger values sink to the bottom.

A treap is a structure with both properties (i.e. there are two kinds of value: a priority and a value).

A randomized treap uses random values for the priority and normal values otherwise. When every node has a random priority, we might expect the tree to be balanced.

1data Treap a = Tip | Node Int (Treap a) a (Treap a)
2data RTreap a = RTreap STdGen (Treap a)
3
4nodeL :: Int -> Treap a -> a -> Treap a -> Treap a
5nodeL p lt@(Node lp llt u lrt) v rt
6  | p <= lp = Node p lt v rt
7  | otherwise = Node lp llt u (Node p lrt v rt)
8
9nodeR :: Int -> Treap a -> a -> Treap a -> Treap a
10nodeR p lt u rt@(Node rp rlt v rrt)
11  | p <= rp = Node p lt u rt
12  | otherwise = Node rp (Node p lt u rlt) v rrt
13
14height :: RTreap a -> Int
15height (RTreap _ t) = height' t
16  where height' Tip = 0
17        height' (Node _ lt _ rt) = 1 + max (height' lt) (height' rt)
18
19instance Poset RTreap where
20  empty = RTreap (mkStdGen 42) Tip
21
22  insert :: forall a. Ord a => a -> RTreap a -> RTreap a
23  insert x (RTreap seed t) = RTreap seed' (pinsert p x t)
24    where (p, seed') = random seed
25
26          pinsert :: Int -> a -> Treap a -> Treap a
27          pinsert p x Tip = Node p Tip x Tip
28          pinsert p x (Node q lt y rt) = case compare x y of
29            EQ -> t
30            LT -> nodeL q (pinsert p x lt) y rt
31            GT -> nodeR q lt y (pinsert p x rt)

The fromList function on a randomized treap is structurally similar to the quicksort algorithm.