Safe Haskell	Safe
Language	Haskell98

Numeric.Probability.Example.Kruskal

Description

Given a row of n (~50) dice, two players start with a random dice within the first m (~5) dice. Every player moves along the row, according to the pips on the dice. They stop if a move would exceed the row. What is the probability that they stop at the same die? (It is close to one.)

Kruskal's trick: http://faculty.uml.edu/rmontenegro/research/kruskal_count/kruskal.html

Wuerfelschlange (german): http://www.math.de/exponate/wuerfelschlange.html/

Synopsis

type Die = Int
type Probability = Rational
type Dist = T Probability
die :: (C prob experiment, Fractional prob) => Score -> experiment Die
type Score = Int
game :: (C prob experiment, Fractional prob) => Score -> Score -> (Score, Score) -> experiment (Maybe Score)
gameRound :: Score -> Score -> Dist (Either (Maybe Score) (Score, Score)) -> Dist (Either (Maybe Score) (Score, Score))
gameFast :: Score -> Score -> Dist (Score, Score) -> Dist (Maybe Score)
gameFastEither :: Score -> Score -> Dist (Score, Score) -> Dist (Maybe Score)
gameFastFix :: Score -> Score -> Dist (Score, Score) -> Dist (Maybe Score)
gameLeastScore :: Score -> Score -> Dist (Score, Score) -> Dist (Maybe Score)
flattenedMatrix :: Score -> [Int]
startVector :: Score -> [Int]
compareMaybe :: Ord a => Maybe a -> Maybe a -> Ordering
cumulate :: Ord a => Dist (Maybe a) -> [(Maybe a, Probability)]
runExact :: Score -> IO ()
trace :: Score -> [Score] -> [Score]
chop :: [Score] -> [[Score]]
meeting :: [Score] -> [Score] -> Maybe Score
bruteforce :: Score -> Score -> (Score, Score) -> T (Maybe Score)
runSimulation :: Score -> IO ()
latexDie :: Score -> String
latexMarkedDie :: Score -> String
latexFromChain :: [Score] -> String
latexChoppedFromChain :: [Score] -> String
makeChains :: IO ()

Documentation

type Die = Int Source #

type Probability = Rational Source #

type Dist = T Probability Source #

die :: (C prob experiment, Fractional prob) => Score -> experiment Die Source #

type Score = Int Source #

game :: (C prob experiment, Fractional prob) => Score -> Score -> (Score, Score) -> experiment (Maybe Score) Source #

We reformulate the problem to the following game: There are two players, both of them collect a number of points. In every round the player with the smaller score throws a die and adds the pips to his score. If the two players somewhen get the same score, then the game ends and the score is the result of the game (Just score). If one of the players exceeds the maximum score n, then the game stops and players lose (Nothing).

gameRound :: Score -> Score -> Dist (Either (Maybe Score) (Score, Score)) -> Dist (Either (Maybe Score) (Score, Score)) Source #

gameFast :: Score -> Score -> Dist (Score, Score) -> Dist (Maybe Score) Source #

gameFastEither :: Score -> Score -> Dist (Score, Score) -> Dist (Maybe Score) Source #

gameFastFix :: Score -> Score -> Dist (Score, Score) -> Dist (Maybe Score) Source #

This version could be generalized to both Random and Distribution monad while remaining efficient.

gameLeastScore :: Score -> Score -> Dist (Score, Score) -> Dist (Maybe Score) Source #

In gameFastFix we group the scores by rounds. This leads to a growing probability distribution, but we do not need the round number. We could process the game in a different way: We only consider the game states where the lower score matches the round number.

flattenedMatrix :: Score -> [Int] Source #

gameLeastScore can be written in terms of a matrix power. For n pips we need a n² × n² matrix. Using symmetries, we reduce it to a square matrix with size n·(n+1)/2.

M[(n+1,(x,y)),(n,(x,y))] = 6

M[(n+1,(min y (n+d), max y (n+d))), (n,(n,y))] = 1

M[(n+1,(x1,y1)),(n,(x0,y0))] = 0

startVector :: Score -> [Int] Source #

compareMaybe :: Ord a => Maybe a -> Maybe a -> Ordering Source #

cumulate :: Ord a => Dist (Maybe a) -> [(Maybe a, Probability)] Source #

runExact :: Score -> IO () Source #

trace :: Score -> [Score] -> [Score] Source #

chop :: [Score] -> [[Score]] Source #

meeting :: [Score] -> [Score] -> Maybe Score Source #

bruteforce :: Score -> Score -> (Score, Score) -> T (Maybe Score) Source #

This is a bruteforce implementation of the original game: We just roll the die maxScore times and then jump from die to die according to the number of pips.

runSimulation :: Score -> IO () Source #

latexDie :: Score -> String Source #

latexMarkedDie :: Score -> String Source #

latexFromChain :: [Score] -> String Source #

latexChoppedFromChain :: [Score] -> String Source #

makeChains :: IO () Source #