Student: Kaela Newman, Undergraduate Student in Mathematics and Data Analytics, Drake University
Research Mentor: Christopher Porter
Algorithmically Random Walks in Markov Chains
In this project, we use notions of algorithmic randomness of strings to study the characteristics of Markov chains, where a Markov chain is a stochastic process consisting of a set of states such that the probability of transitioning from one state to another is determined only by the previous state visited.
We seek to determine the extent to which a string that is random with respect to the stationary distribution of a Markov chain reflects the underlying structure of the associated Markov chain, in the sense that if we use the string to define a random walk through the state space of the chain, the number of times this random walk visits a given state is approximately equal to the expected number of visits. To define these random walks, we are focusing specifically on weak notions of algorithmic randomness defined in terms of approximate entropy, but we aim to incorporate stronger notions of randomness defined in terms of various compressors.
We seek to determine the extent to which a string that is random with respect to the stationary distribution of a Markov chain reflects the underlying structure of the associated Markov chain, in the sense that if we use the string to define a random walk through the state space of the chain, the number of times this random walk visits a given state is approximately equal to the expected number of visits. To define these random walks, we are focusing specifically on weak notions of algorithmic randomness defined in terms of approximate entropy, but we aim to incorporate stronger notions of randomness defined in terms of various compressors.