Derren Brown recently claimed he would predict the UK lottery numbers, live on television, and then explain how he did it. It’s doubtful that he did either â€” the alternative explanation that he’d actually committed a massive and improbably daring fraud is vastly more likely than the bullshit he spun out, as it’s actually possible…
I’m certain (or at the very least hopeful) that the actual “reveal” will come later on in the series… but in the mean time, he did show one very cute mathematical trick for winning a coin game.
This is the game:
- Player 1 chooses a 3-coin combination, say Tails,Tails,Heads
- Player 2 chooses another, for example Heads,Tails,Tails
- We now throw a series of coins until one of the players’ combination is thrown in order.
You might think, given that any 3-coin combination is as likely as another (will be thrown with a 1/8 probability) that there’s nothing to choose between them. But notice that I didn’t say you threw 3 coins at a time! For example, if we throw.
- Tails … at this point we’ve thrown 3 coins, and matched no combination
- Tails … and now player 2 has won: coins 2-4 read Heads,Tails,Tails
If you look at these 2 combinations, you’ll see that Player 1 will win if the sequence goes: Tails,Tails,(any number of Tails), Head. Player 2 will win in any other situation, i.e. 75% of the time.
The combination the hapless participant chose (Heads,Heads,Heads) is even worse, losing 87.5% of the time!
It’s about time for me to try modelling a problem in Haskell, so let’s try this one!
I find the docs for System.Random rather confusing, but found some inspiration from a
haskell-cafe post about random coin throws and encouragement on #haskell from Luke30, Twey, and others.
I won’t go through the code in detail this time, but here are some key things to note:
- the randoms function returns an infinite stream of random things. In this case I’m using it as a stream of Bools, like [False, True, True, False, True, ...] and then converting them into [Tail,Head, ...].
lilac pointed out that I could create an instance of Random for Coins, I’ll have a look at that soon.
- I’m using tails (nicely overloaded vocabulary ;-) to iterate the infinite sequence of coin flips, stopping when one of the players’ sequences matches.
And here’s the code:
import System.Random import Control.Monad import System.IO import Data.Maybe import Data.List data Coin = Head | Tail deriving (Eq, Ord, Show) -- Derren Brown's coin game. -- The second winner has chosen a combination that will win -- significantly more often main = do g1 <- guess let g2 = counter g1 putStrLn $ "Player 1 chooses " ++ (show g1) putStrLn $ "Player 2 chooses " ++ (show g2) coins <- coinFlips let winner = take 1 . catMaybes . map (win g1 g2) $ tails coins putStrLn $ "Player " ++ (show winner) ++ " wins!" guess = do f <- coinFlips return $ take 3 f counter [a,b,_] = [rev b, a, b] where rev Head = Tail rev Tail = Head win g1 g2 l | g1 `isPrefixOf` l = Just 1 | g2 `isPrefixOf` l = Just 2 | otherwise = Nothing -- modified from -- http://www.haskell.org/pipermail/haskell-cafe/2005-April/009687.html coinFlips :: IO [Coin] coinFlips = do g <- newStdGen let bools = randoms g let coins = map bool2coin bools return coins where bool2coin True = Head bool2coin False = Tail