Speaker:Andrei Migunov

Algorithmic Randomness in Continuous-time Markov Chains

In this talk, based on joint work with Xiang Huang and Jack H. Lutz, I will discuss the notion of randomness in continuous-time Markov chains. A continuous-time Markov chain (CTMC) is a stochastic (random) process in which transitions between states of this process are governed by probability and times between such transitions are continuous (real-valued) and are also governed probabilistically by an exponential distribution at each state. This distribution, as well the next system state, depends only on the current state (this is called memorylessness, or the Markov property). Each individual trajectory of a CTMC can be thought of as a particular execution of the chain itself -- (a concrete sequence of transitions which happens when we 'press Play' on the CTMC). That said -- what does it mean for a particular trajectory itself to be random or non-random, as opposed to being randomly determined? To answer this question we need a theory of randomness for CTMCs, and I will discuss a theory based on the classical theory of randomness for infinite binary sequences, as well as some applications to the primary motivation of this research: computation using chemical reaction networks (CRNs). Stochastic CRNs are a model of analog computation in which chemical reactions transition a system between states (here, states are vectors of positive integers representing quantities of various types of molecules in solution). It is desirable to be able to reason about the executions of such reaction networks because we want to harness them for computation. A theory of randomness is helpful in this regard.

Bio: Andrei is a Ph.D. student in the ISU Department of Computer Science advised by Jack H. Lutz. He has a bachelor's degree in Philosophy and in Computer Science also from ISU. His interests are randomness, analog computation, and philosophy of science.

This exam will be held on WebEx. 

Meeting number: 120 677 9741

Password: gradwebinar