Grant: Discovery Grants Program - Individual
University of Manitoba
$12,000.00
Runs and patterns, coupon collecting and permutations
FY 2012-13
Summary
The distribution theory of runs and patterns in sequences of multi-state trials has a long and rich history and has applications in genetics (particularly biological sequences), reliability theory, game theory, health sciences and general statistical inference. The exact distribution for a large class of these runs and patterns may be found by a finite Markov imbedding technique. In general, we consider the exact distribution of the number of occurrences of patterns in a large number of trials. In many cases, however, the resulting state spaces for these Markov chains are prohibitively large and exact probability calculations become difficult from both a time and space perspective. In this research we propose to study new approximation methods for these probabilities. We have developed approximations for extreme left-tail probabilities which outperform the usual Gaussian and Poisson approximations for these types of problems. Here, we intend to develop similar results for extreme right-tail probabilities. These are important for many reasons. In biological sequences (DNA, RNA and protein sequences, for example), patterns which occur much more often than expected (or much less often than suspected) may have some biological function and hence identifying these are important. I will also investigate the distribution of runs and patterns in permutations and permutations of multi-sets. The additional difficulty here lies with dependence structure among elements of the permutations. Here, I intend to not only study specific cases, but also to study more general methods that will be applicable for a wide variety of runs and patterns in permutations. Runs and patterns in permutations have many of the same applications as those listed above. Some secondary structures in RNA, for example, can be linked to permutations. The final area of research in this proposal involves some generalizations of the classic coupon collector's problem and these have applications such as network security, capture/mark/recapture experiments, and reliability theory. Many of the techniques used for runs and patterns in multi-state trials and permutations also have applications to these types of extensions.
Program
Discovery Grants Program - Individual
Recipient
Location
Manitoba, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
327123-2010
Name nom
Johnson, Brad
Department département
Statistics
Organization id
19
Institution établissement
University of Manitoba
Province en
Manitoba
Province fr
Manitoba
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2012
Competition year année de concours
2010
Award amount
12000
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
1508
Committee name en
Mathematics and Statistics
Committee name fr
Mathématiques et statistique
Area of application code
1205
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Mathematical sciences
Area of application fr
Sciences mathématiques
Research subject code
3000
Research subject group en
Statistics and probability
Research subject group fr
Statistique et probabilité
Research subject en
Statistics and probability
Research subject fr
Statistique et probabilité
Partie
3
Nb partie
5
Application title
Runs and patterns, coupon collecting and permutations
Keyword
NSERC
Application summary
The distribution theory of runs and patterns in sequences of multi-state trials has a long and rich history and has applications in genetics (particularly biological sequences), reliability theory, game theory, health sciences and general statistical inference. The exact distribution for a large class of these runs and patterns may be found by a finite Markov imbedding technique. In general, we consider the exact distribution of the number of occurrences of patterns in a large number of trials. In many cases, however, the resulting state spaces for these Markov chains are prohibitively large and exact probability calculations become difficult from both a time and space perspective. In this research we propose to study new approximation methods for these probabilities. We have developed approximations for extreme left-tail probabilities which outperform the usual Gaussian and Poisson approximations for these types of problems. Here, we intend to develop similar results for extreme right-tail probabilities. These are important for many reasons. In biological sequences (DNA, RNA and protein sequences, for example), patterns which occur much more often than expected (or much less often than suspected) may have some biological function and hence identifying these are important. I will also investigate the distribution of runs and patterns in permutations and permutations of multi-sets. The additional difficulty here lies with dependence structure among elements of the permutations. Here, I intend to not only study specific cases, but also to study more general methods that will be applicable for a wide variety of runs and patterns in permutations. Runs and patterns in permutations have many of the same applications as those listed above. Some secondary structures in RNA, for example, can be linked to permutations. The final area of research in this proposal involves some generalizations of the classic coupon collector's problem and these have applications such as network security, capture/mark/recapture experiments, and reliability theory. Many of the techniques used for runs and patterns in multi-state trials and permutations also have applications to these types of extensions.