Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Ottawa

$26,000.00

Inference and Scaling in Stochastic Dynamical Systems

EF 2015-16

Résumé
Dynamical systems are a ubiquitous feature of our world: from the small (the motions of single atoms) to the large (galactic dynamics), from the concrete (foraging patterns of ants) to the abstract (flow of information on the internet), from the quick (neural impulses) to the slow (evolutionary trajectories of different species' genomes). Being able to understand such systems is crucial to fields as diverse as biology, chemistry, physics, economics, engineering, and, not least, computer science. My research focuses on computational methods for the analysis and estimation of dynamical systems, particularly stochastic dynamical systems. The current proposal focuses on two recent problems on which my lab has made important breakthroughs: characterizing path distributions for discrete-state discrete-time stochastic systems (Markov chains), and inference of maximum-probability paths for discrete-state continuous-time stochastic systems (continuous-time Markov chains). On the path distribution problem, we recently clarified and improved upon a 50-year old conjecture by Mandelbrot by proving necessary and sufficient conditions for the distribution of paths generated by a Markov chain to be powerlaw. We also showed that finite and stretched-exponential distributions are possible, with the distribution type depending only on the structure of possible state transitions, and not on the exact transition probabilities. We developed graph-theoretic computations to discriminate between the cases, and efficient eigenvalue / dynamic programming computations to determine distribution parameters. In this proposal, we will investigate the uses of our theory for model selection. In the case that empirical scaling of the path distribution is observed and a Markov model needs to be estimated from the data, how can we incorporate scaling information into the model estimation process? We will also work to extend our results to more sophisticated models of sequential data--in particular, stochastic context-free grammars, which are relevant to the analysis of natural language, music, genome structure, and many other complex real-world systems. For the path inference problem, we have recently developed an approach called State Sequence Analysis for identifying the most probable sequences of states visited by a continuous-time Markov chain over some period of time. Using this approach, we obtained novel insights into a number of domains, including stochastic protein folding, the evolution of drug-resistance mutations in HIV, and ion channel dynamics. In the present proposal, we will seek to extend our results to noisy / partial observation models, as well as more general forms of waiting-time distributions in the states of the system. This will allow State Sequence Analysis to be applied to a much wider range of target domains.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
RGPIN-2014-05716
Name nom
Perkins, Theodore
Department département
Biochemistry, Microbiology and Immunology
Organization id
28
Institution établissement
University of Ottawa
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2015
Competition year année de concours
2014
Award amount
26000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
Research subject code
2713
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Algorithms
Research subject fr
Algorithmes
Partie
2
Nb partie
5
Application title
Inference and Scaling in Stochastic Dynamical Systems
Keyword
NSERC
Application summary
Dynamical systems are a ubiquitous feature of our world: from the small (the motions of single atoms) to the large (galactic dynamics), from the concrete (foraging patterns of ants) to the abstract (flow of information on the internet), from the quick (neural impulses) to the slow (evolutionary trajectories of different species' genomes). Being able to understand such systems is crucial to fields as diverse as biology, chemistry, physics, economics, engineering, and, not least, computer science. My research focuses on computational methods for the analysis and estimation of dynamical systems, particularly stochastic dynamical systems. The current proposal focuses on two recent problems on which my lab has made important breakthroughs: characterizing path distributions for discrete-state discrete-time stochastic systems (Markov chains), and inference of maximum-probability paths for discrete-state continuous-time stochastic systems (continuous-time Markov chains). On the path distribution problem, we recently clarified and improved upon a 50-year old conjecture by Mandelbrot by proving necessary and sufficient conditions for the distribution of paths generated by a Markov chain to be powerlaw. We also showed that finite and stretched-exponential distributions are possible, with the distribution type depending only on the structure of possible state transitions, and not on the exact transition probabilities. We developed graph-theoretic computations to discriminate between the cases, and efficient eigenvalue / dynamic programming computations to determine distribution parameters. In this proposal, we will investigate the uses of our theory for model selection. In the case that empirical scaling of the path distribution is observed and a Markov model needs to be estimated from the data, how can we incorporate scaling information into the model estimation process? We will also work to extend our results to more sophisticated models of sequential data--in particular, stochastic context-free grammars, which are relevant to the analysis of natural language, music, genome structure, and many other complex real-world systems. For the path inference problem, we have recently developed an approach called State Sequence Analysis for identifying the most probable sequences of states visited by a continuous-time Markov chain over some period of time. Using this approach, we obtained novel insights into a number of domains, including stochastic protein folding, the evolution of drug-resistance mutations in HIV, and ion channel dynamics. In the present proposal, we will seek to extend our results to noisy / partial observation models, as well as more general forms of waiting-time distributions in the states of the system. This will allow State Sequence Analysis to be applied to a much wider range of target domains.