Discrete Stochastic Processes: Tools for Machine Learning and Data Science

Preface
Contents
List of Figures
1 A Summary of Markov Chains
	1.1 Markov Property
		Transition Matrices
		Higher-Order Transition Probabilities
	1.2 Hitting Probabilities
		Hitting Probabilities
	1.3 Mean Hitting and Absorption Times
		First Return Times
		Hitting Times vs. Return Times
		Markov Chains with Rewards
		Mean Number of Returns
	1.4 Classification of States
		Communicating States
		Examples: Reducibility and Irreducibility
		Recurrent States
		Transient States
		Examples: Recurrent and Transient States
		Positive vs. Null Recurrence
		Periodicity and Aperiodicity
		Examples: Periodicity and Aperiodicity
	1.5 Hitting Times of Random Walks
		Mean Hitting Times
	Notes
	Exercises
2 Phase-Type Distributions
	2.1 Negative Binomial Distribution
	2.2 Markovian Construction
	2.3 Hitting Time Distribution
	2.4 Mean Hitting Times
	Notes
	Exercises
3 Synchronizing Automata
	3.1 Pattern Recognition
		Markovian Text Generation
		First-Order Word Analysis
		Second-Order Word Analysis
		Independent Samples
		Average Recognition Times
		Probability Generating Functions
	3.2 Winning Streaks
		Probability Distribution of T(m)
	3.3 Synchronizing Automata
		Example
		Markovian Text Generator
	3.4 Synchronization Times
		Mean Synchronization Times
		Synchronization Probabilities
	Notes
	Exercises
4 Random Walks and Recurrence
	4.1 Distribution and Hitting Times
		One-Dimensional Random Walk
		Two-Dimensional Random Walk
		Multidimensional Random Walk
		Return Times
	4.2 Recurrence of Symmetric Random Walks
		Recurrence of the One-Dimensional Random Walk
		Recurrence of the Two-Dimensional Random Walk
		Recurrence of d-Dimensional Random Walks, d3
		Recurrence Revisited
	4.3 Reflected Random Walk
	4.4 Conditioned Random Walk
		Conditional Hitting Probabilities
		Conditional Mean Hitting Times
	Notes
	Exercises
5 Cookie-Excited Random Walks
	5.1 Hitting Times and Probabilities
		Hitting Probabilities
	5.2 Recurrence
	5.3 Mean Hitting Times
	5.4 Count of Cookies Eaten
	5.5 Conditional Results
	Notes
	Exercises
6 Convergence to Equilibrium
	6.1 Limiting and Stationary Distributions
		Limiting Distributions
		Example
		Stationary Distributions
		Example
	6.2 Markov Chain Monte Carlo: MCMC
		Generating Random Samples from a Target Distribution
		Interpretation
		Generating Posterior Samples Using MCMC
		Implementation Example
	6.3 Transition Bounds and Contractivity
	6.4 Distance to Stationarity
	6.5 Mixing Times
		Coupling
	Notes
	Exercises
7 The Ising Model
	7.1 Construction
		Example
	7.2 Irreducibility, Aperiodicity and Recurrence
		Aperiodicity
		Irreducibility
		Recurrence
	7.3 Limiting and Stationary Distributions
	7.4 Simulation Examples
	Notes
	Exercises
8 Search Engines
	8.1 Markovian Modeling of Ranking
	8.2 Limiting and Stationary Distributions
	8.3 Matrix Perturbation
	8.4 State Ranking
		Convergence Analysis
		Mean Return Times Analysis
	8.5 Meta Search Engines
		Limiting and Stationary Distributions
		Matrix Perturbation
		State Ranking
		Convergence Analysis
		Mean Return Times Analysis
	Notes
	Exercises
9 Hidden Markov Model
	9.1 Graphical Markov Model
		Hidden Chain
		Observed Process
		Example
	9.2 Forward–Backward Formulas
	9.3 Hidden State Estimation
		Maximum Likelihood Estimation
	9.4 Forward–Backward Algorithm
		Forward Algorithm
		Backward Algorithm
		Forward–Backward Algorithm
	9.5 Baum-Welch Algorithm
		Simulation Example
		Frequency Analysis
	Notes
	Exercises
10 Markov Decision Processes
	10.1 Construction
		Example: Deterministic MDP
	10.2 Reinforcement Learning
		Policy Optimization
		Q-Learning
	10.3 Example: Deterministic MDP
		Optimal Value Function
		Optimal Policy
	10.4 Example: Stochastic MDP
	Notes
	Exercises
A Probability Generating Functions
	A.1 Probability Generating Functions
		Some Properties of Probability Generating Functions
B Some Useful Identities
References
Index
Author Index