1 of 64

Deciphering using MCMC

Ales Franek

ales.franek-e@maf.ae

2 of 64

GARAGE TRIP CIPHER

3 of 64

GARAGE TRIP CIPHER

4 of 64

GARAGE TRIP CIPHER

5 of 64

GARAGE TRIP CIPHER

6 of 64

Outline

Basics of Markov chains

Monte Carlo methods

Accept-Reject Sampling

Markov Chain Monte Carlo (MCMC) methods

Metropolis-Hastings algorithm

Practical demonstration

Deciphering using MCMC

7 of 64

Markov Chains

8 of 64

Markov Chain

9 of 64

Markov Chain

Definition: A Markov chain is a stochastic process that undergoes transitions from one state to another in a state space. It possesses the Markov property, which states that the future state depends only on the current state, not on the sequence of events that preceded it.

Key terms:

State Space: The set of all possible states in which a system can exist.

Transition Probability: The probability of moving from one state to another.

State Transition Diagram: A graphical representation of a Markov chain, showing states as nodes and transitions as directed edges with associated probabilities.

Transition Matrices

Definition: A transition matrix (or stochastic matrix) represents the probabilities of moving from one state to another in a single time step. Each element PijP_{ij}Pij of the matrix indicates the probability of transitioning from state i to state j.

Properties:

Each row of the transition matrix sums to 1.

Transition matrices are often used to compute the distribution of states over time.

Stationary Distribution (steady state): A probability distribution that remains unchanged as the system evolves over time. It represents the long-term behavior of the Markov chain.

Ergodic Chains: Chains where it is possible to reach any state from any other state. Ergodic chains have a unique stationary distribution.

10 of 64

Markov Chain

Definition: A Markov chain is a stochastic process that undergoes transitions from one state to another in a state space. It possesses the Markov property, which states that the future state depends only on the current state, not on the sequence of events that preceded it.

Key terms:

State Space: The set of all possible states in which a system can exist.

Transition Probability: The probability of moving from one state to another.

State Transition Diagram: A graphical representation of a Markov chain, showing states as nodes and transitions as directed edges with associated probabilities.

Transition Matrices

Definition: A transition matrix (or stochastic matrix) represents the probabilities of moving from one state to another in a single time step. Each element PijP_{ij}Pij of the matrix indicates the probability of transitioning from state i to state j.

Properties:

Each row of the transition matrix sums to 1.

Transition matrices are often used to compute the distribution of states over time.

Stationary Distribution (steady state): A probability distribution that remains unchanged as the system evolves over time. It represents the long-term behavior of the Markov chain.

Ergodic Chains: Chains where it is possible to reach any state from any other state. Ergodic chains have a unique stationary distribution.

11 of 64

Markov Chain

Definition: A Markov chain is a stochastic process that undergoes transitions from one state to another in a state space. It possesses the Markov property, which states that the future state depends only on the current state, not on the sequence of events that preceded it.

Key terms:

State Space: The set of all possible states in which a system can exist.

Transition Probability: The probability of moving from one state to another.

State Transition Diagram: A graphical representation of a Markov chain, showing states as nodes and transitions as directed edges with associated probabilities.

Transition Matrices

Definition: A transition matrix (or stochastic matrix) represents the probabilities of moving from one state to another in a single time step. Each element PijP_{ij}Pij of the matrix indicates the probability of transitioning from state i to state j.

Properties:

Each row of the transition matrix sums to 1.

Transition matrices are often used to compute the distribution of states over time.

Stationary Distribution (steady state): A probability distribution that remains unchanged as the system evolves over time. It represents the long-term behavior of the Markov chain.

Ergodic Chains: Chains where it is possible to reach any state from any other state. Ergodic chains have a unique stationary distribution.

12 of 64

Markov Chain

Definition: A Markov chain is a stochastic process that undergoes transitions from one state to another in a state space. It possesses the Markov property, which states that the future state depends only on the current state, not on the sequence of events that preceded it.

Key terms:

State Space: The set of all possible states in which a system can exist.

Transition Probability: The probability of moving from one state to another.

State Transition Diagram: A graphical representation of a Markov chain, showing states as nodes and transitions as directed edges with associated probabilities.

Transition Matrices

Definition: A transition matrix (or stochastic matrix) represents the probabilities of moving from one state to another in a single time step. Each element PijP_{ij}Pij of the matrix indicates the probability of transitioning from state i to state j.

Properties:

Each row of the transition matrix sums to 1.

Transition matrices are often used to compute the distribution of states over time.

Stationary Distribution (steady state): A probability distribution that remains unchanged as the system evolves over time. It represents the long-term behavior of the Markov chain.

Ergodic Chains: Chains where it is possible to reach any state from any other state. Ergodic chains have a unique stationary distribution.

13 of 64

Markov Chain - Stationary Distribution

Definition: A Markov chain is a stochastic process that undergoes transitions from one state to another in a state space. It possesses the Markov property, which states that the future state depends only on the current state, not on the sequence of events that preceded it.

Key terms:

State Space: The set of all possible states in which a system can exist.

Transition Probability: The probability of moving from one state to another.

State Transition Diagram: A graphical representation of a Markov chain, showing states as nodes and transitions as directed edges with associated probabilities.

Transition Matrices

Definition: A transition matrix (or stochastic matrix) represents the probabilities of moving from one state to another in a single time step. Each element PijP_{ij}Pij of the matrix indicates the probability of transitioning from state i to state j.

Properties:

Each row of the transition matrix sums to 1.

Transition matrices are often used to compute the distribution of states over time.

Stationary Distribution (steady state): A probability distribution that remains unchanged as the system evolves over time. It represents the long-term behavior of the Markov chain.

Ergodic Chains: Chains where it is possible to reach any state from any other state. Ergodic chains have a unique stationary distribution.

14 of 64

Markov Chain - Stationary Distribution

Definition: A Markov chain is a stochastic process that undergoes transitions from one state to another in a state space. It possesses the Markov property, which states that the future state depends only on the current state, not on the sequence of events that preceded it.

Key terms:

State Space: The set of all possible states in which a system can exist.

Transition Probability: The probability of moving from one state to another.

State Transition Diagram: A graphical representation of a Markov chain, showing states as nodes and transitions as directed edges with associated probabilities.

Transition Matrices

Definition: A transition matrix (or stochastic matrix) represents the probabilities of moving from one state to another in a single time step. Each element PijP_{ij}Pij of the matrix indicates the probability of transitioning from state i to state j.

Properties:

Each row of the transition matrix sums to 1.

Transition matrices are often used to compute the distribution of states over time.

Stationary Distribution (steady state): A probability distribution that remains unchanged as the system evolves over time. It represents the long-term behavior of the Markov chain.

Ergodic Chains: Chains where it is possible to reach any state from any other state. Ergodic chains have a unique stationary distribution.

15 of 64

Markov Chain - Stationary Distribution

Definition: A Markov chain is a stochastic process that undergoes transitions from one state to another in a state space. It possesses the Markov property, which states that the future state depends only on the current state, not on the sequence of events that preceded it.

Key terms:

State Space: The set of all possible states in which a system can exist.

Transition Probability: The probability of moving from one state to another.

State Transition Diagram: A graphical representation of a Markov chain, showing states as nodes and transitions as directed edges with associated probabilities.

Transition Matrices

Definition: A transition matrix (or stochastic matrix) represents the probabilities of moving from one state to another in a single time step. Each element PijP_{ij}Pij of the matrix indicates the probability of transitioning from state i to state j.

Properties:

Each row of the transition matrix sums to 1.

Transition matrices are often used to compute the distribution of states over time.

Stationary Distribution (steady state): A probability distribution that remains unchanged as the system evolves over time. It represents the long-term behavior of the Markov chain.

Ergodic Chains: Chains where it is possible to reach any state from any other state. Ergodic chains have a unique stationary distribution.

16 of 64

Markov Chain - Stationary Distribution

Definition: A Markov chain is a stochastic process that undergoes transitions from one state to another in a state space. It possesses the Markov property, which states that the future state depends only on the current state, not on the sequence of events that preceded it.

Key terms:

State Space: The set of all possible states in which a system can exist.

Transition Probability: The probability of moving from one state to another.

State Transition Diagram: A graphical representation of a Markov chain, showing states as nodes and transitions as directed edges with associated probabilities.

Transition Matrices

Definition: A transition matrix (or stochastic matrix) represents the probabilities of moving from one state to another in a single time step. Each element PijP_{ij}Pij of the matrix indicates the probability of transitioning from state i to state j.

Properties:

Each row of the transition matrix sums to 1.

Transition matrices are often used to compute the distribution of states over time.

Stationary Distribution (steady state): A probability distribution that remains unchanged as the system evolves over time. It represents the long-term behavior of the Markov chain.

Ergodic Chains: Chains where it is possible to reach any state from any other state. Ergodic chains have a unique stationary distribution.

17 of 64

Markov Chain - Stationary Distribution

Definition: A Markov chain is a stochastic process that undergoes transitions from one state to another in a state space. It possesses the Markov property, which states that the future state depends only on the current state, not on the sequence of events that preceded it.

Key terms:

State Space: The set of all possible states in which a system can exist.

Transition Probability: The probability of moving from one state to another.

State Transition Diagram: A graphical representation of a Markov chain, showing states as nodes and transitions as directed edges with associated probabilities.

Transition Matrices

Definition: A transition matrix (or stochastic matrix) represents the probabilities of moving from one state to another in a single time step. Each element PijP_{ij}Pij of the matrix indicates the probability of transitioning from state i to state j.

Properties:

Each row of the transition matrix sums to 1.

Transition matrices are often used to compute the distribution of states over time.

Stationary Distribution (steady state): A probability distribution that remains unchanged as the system evolves over time. It represents the long-term behavior of the Markov chain.

Ergodic Chains: Chains where it is possible to reach any state from any other state. Ergodic chains have a unique stationary distribution.

18 of 64

Markov Chain - Stationary Distribution

Definition: A Markov chain is a stochastic process that undergoes transitions from one state to another in a state space. It possesses the Markov property, which states that the future state depends only on the current state, not on the sequence of events that preceded it.

Key terms:

State Space: The set of all possible states in which a system can exist.

Transition Probability: The probability of moving from one state to another.

State Transition Diagram: A graphical representation of a Markov chain, showing states as nodes and transitions as directed edges with associated probabilities.

Transition Matrices

Definition: A transition matrix (or stochastic matrix) represents the probabilities of moving from one state to another in a single time step. Each element PijP_{ij}Pij of the matrix indicates the probability of transitioning from state i to state j.

Properties:

Each row of the transition matrix sums to 1.

Transition matrices are often used to compute the distribution of states over time.

Stationary Distribution (steady state): A probability distribution that remains unchanged as the system evolves over time. It represents the long-term behavior of the Markov chain.

Ergodic Chains: Chains where it is possible to reach any state from any other state. Ergodic chains have a unique stationary distribution.

19 of 64

Markov Chain - Stationary Distribution

Definition: A Markov chain is a stochastic process that undergoes transitions from one state to another in a state space. It possesses the Markov property, which states that the future state depends only on the current state, not on the sequence of events that preceded it.

Key terms:

State Space: The set of all possible states in which a system can exist.

Transition Probability: The probability of moving from one state to another.

State Transition Diagram: A graphical representation of a Markov chain, showing states as nodes and transitions as directed edges with associated probabilities.

Transition Matrices

Definition: A transition matrix (or stochastic matrix) represents the probabilities of moving from one state to another in a single time step. Each element PijP_{ij}Pij of the matrix indicates the probability of transitioning from state i to state j.

Properties:

Each row of the transition matrix sums to 1.

Transition matrices are often used to compute the distribution of states over time.

Stationary Distribution (steady state): A probability distribution that remains unchanged as the system evolves over time. It represents the long-term behavior of the Markov chain.

Ergodic Chains: Chains where it is possible to reach any state from any other state. Ergodic chains have a unique stationary distribution.

20 of 64

Monte Carlo Methods

21 of 64

Monte Carlo

22 of 64

Monte Carlo

23 of 64

Accept-Reject Sampling

24 of 64

Accept-Reject Sampling

25 of 64

Accept-Reject Sampling

26 of 64

Accept-Reject Sampling

27 of 64

Accept-Reject Sampling

28 of 64

Accept-Reject Sampling

29 of 64

Accept-Reject Sampling

30 of 64

Accept-Reject Sampling

31 of 64

Accept-Reject Sampling

32 of 64

Accept-Reject Sampling

33 of 64

Markov Chain Monte Carlo (MCMC) Methods

34 of 64

Accept-Reject Sampling

35 of 64

MCMC Markov Chain

36 of 64

Probability Distribution Modelling

37 of 64

Probability Distribution Modelling

38 of 64

Probability Distribution Modelling

39 of 64

Probability Distribution Modelling

40 of 64

Probability Distribution Modelling

41 of 64

Probability Distribution Modelling

42 of 64

Probability Distribution Modelling

43 of 64

Probability Distribution Modelling

44 of 64

MCMC Markov Chain

45 of 64

Metropolis-Hastings Algorithm

46 of 64

Metropolis–Hastings Algorithm

47 of 64

Metropolis–Hastings Algorithm

48 of 64

Demo

49 of 64

Deciphering using MCMC

50 of 64

GARAGE TRIP CIPHER

51 of 64

Text Probability

yQd SdEEZK OCrrDFfJA mm gricxgDDUP wlS Hiwat kR uYoZl diWFhqU NOXd p SqCR mKgyHu fR WbjA fFWGXy mJxMjYeq aDMPp MhWwIUN KPCuXHQZG zvlsP KhUOjKjT

Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Et sollicitudin ac orci phasellus egestas tellus rutrum tellus pellentesque.

When Mr. Bilbo Baggins of Bag End announced that he would shortly be celebrating his eleventy-first birthday with a party of special magnificence, there was much talk and excitement in Hobbiton.

52 of 64

Text Probability

53 of 64

Text Probability

54 of 64

Text Probability

55 of 64

Text Probability

56 of 64

Text Probability

57 of 64

Text Probability

58 of 64

Laplace Smoothing

59 of 64

Laplace Smoothing

60 of 64

Laplace Smoothing

61 of 64

Laplace Smoothing

62 of 64

Laplace Smoothing

63 of 64

Laplace Smoothing

64 of 64

Lower Bound of Wilson Score Confidence Interval for a Bernoulli Parameter

Given the ratings I have, there is a 95% chance that the “real” fraction of positive ratings is at least what?