<p>I denna avhandling studerar vi nödvändiga och tillräckliga villkor för svag konvergens av första-sällan-händelsetider för semi-Markovska processer.</p><p>I introduktionen ger vi nödvändiga grundläggande definitioner och beskrivningar av modeller som betraktas i avhandlingen, samt ger några exempel på situationer i vilka metoder av första-sällan-händelsetider kan vara lämpliga att använda. Dessutom analyserar vi publicerade resultat om asymptotiska problem för stokastiska funktionaler som definieras på semi-Markovska processer.</p><p>I artikel A betraktar vi första-sällan-händelsetider för semi-Markovska processer med en ändlig mängd av lägen. Vi ger också en sammanfattning av våra resultat om nödvändiga och tillräckliga villkor för svag konvergens, samt diskuterar möjliga tillämpningar inom aktuarie-området.</p><p>I artikel B redovisar vi i detalj de resultat som annonseras i artikel A och bevisen för dem. Vi ger också nödvändiga och tillräckliga villkor för svag konvergens av första-sällan-händelsetider för semi-Markovska processer med en ändlig mängd av lägen i ett icke-triangulärt tillstånd. Dessutom beskriver vi med hjälp av Laplacetransformationen klassen av alla möjliga gränsfördelningar.</p><p>I artikel C studerar vi villkor av svag konvergens av flöden av sällan-händelser i ett icke-triangulärt tillstånd. Vi formulerar nödvändiga och tillräckliga villkor för konvergens, och beskriver klassen av alla möjliga gränsflöden. Vi tillämpar också våra resultat i asymptotisk analys av icke-ruin-sannolikheten för störda riskprocesser.</p><p>I artikel D ger vi nödvändiga och tillräckliga villkor för svag konvergens av första-sällan-händelsetider för semi-Markovska rocesser med en ändlig mängd av lägen i ett triangulärt tillstånd, samt beskriver klassen av alla möjliga gränsfördelningar. Resultaten utvidgar slutsatser från artikel B till att gälla för ett allmänt triangulärt tillstånd.</p><p>I artikel E ger vi nödvändiga och tillräckliga villkor för svag konvergens av flöden av sällan-händelser för semi-Markovska processer i ett triangulärt tillstånd. Detta generaliserar resultaten från artikel C till att beskriva ett allmänt triangulärt tillstånd. Vidare ger vi tillämpningar av våra resultat på asymptotiska problem av störda riskprocesser och till kösystemen med snabb service.</p> / <p>In this thesis we study necessary and sufficient conditions for weak convergence of first-rare-event times for semi-Markov processes, we describe the class of all possible limit distributions, and give the applications of the results to risk theory and queueing systems.</p><p>In paper <b>A</b>, we consider first-rare-event times for semi-Markov processes with a finite set of states, and give a summary of our results concerning necessary and sufficient conditions for weak convergence of first-rare-event times and their actuarial applications.</p><p>In paper <b>B</b>, we present in detail results announced in paper <b>A</b> as well as their proofs. We give necessary and sufficient conditions for weak convergence of first-rare-event times for semi-Markov processes with a finite set of states in non-triangular-array mode and describe the class of all possible limit distributions in terms of their Laplace transforms.</p><p>In paper <b>C</b>, we study the conditions for weak convergence for flows of rare events for semi-Markov processes with a finite set of states in non-triangular array mode. We formulate necessary and sufficient conditions of convergence and describe the class of all possible limit stochastic flows. In the second part of the paper, we apply our results to the asymptotical analysis of non-ruin probabilities for perturbed risk processes.</p><p>In paper <b>D</b>, we give necessary and sufficient conditions for the weak convergence of first-rare-event times for semi-Markov processes with a finite set of states in triangular array mode as well as describing the class of all possible limit distributions. The results of paper <b>D</b> extend results obtained in paper <b>B</b> to a general triangular array mode.</p><p>In paper <b>E</b>, we give the necessary and sufficient conditions for weak convergence for the flows of rare events for semi-Markov processes with a finite set of states in triangular array case. This paper generalizes results obtained in paper <b>C</b> to a general triangular array mode. In the second part of the paper, we present applications of our results to asymptotical problems of perturbed risk processes and to queueing systems with quick service</p>

One of the newer and rapidly developing approaches in quantum computing is based on "quantum walks," which are quantum processes on discrete space that evolve in either discrete or continuous time and are characterized by mixing of components at each step. The idea emerged in analogy with the classical random walks and stochastic techniques, but these unitary processes are very different even as they have intriguing similarities. This thesis is concerned with study of discrete-time quantum walks. The original motivation from classical Markov chains required for discrete-time quantum walks that one adds an auxiliary Hilbert space, unrelated to the one in which the system evolves, in order to be able to mix components in that space and then take the evolution steps accordingly (based on the state in that space). This additional, "coin," space is very often an internal degree of freedom like spin. We have introduced a general framework for construction of discrete-time quantum walks in a close analogy with the classical random walks with memory that is rather different from the standard "coin" approach. In this method there is no need to bring in a different degree of freedom, while the full state of the system is still described in the direct product of spaces (of states). The state can be thought of as an arrow pointing from the previous to the current site in the evolution, representing the one-step memory. The next step is then controlled by a single local operator assigned to each site in the space, acting quite like a scattering operator. This allows us to probe and solve some problems of interest that have not had successful approaches with "coined" walks. We construct and solve a walk on the binary tree, a structure of great interest but until our result without an explicit discrete time quantum walk, due to difficulties in managing coin spaces necessary in the standard approach. Beyond algorithmic interests, the model based on memory allows one to explore effects of history on the quantum evolution and the subtle emergence of classical features as "memory" is explicitly kept for additional steps. We construct and solve a walk with an additional correlation step, finding interesting new features. On the other hand, the fact that the evolution is driven entirely by a local operator, not involving additional spaces, enables us to choose the Fourier transform as an operator completely controlling the evolution. This in turn allows us to combine the quantum walk approach with Fourier transform based techniques, something decidedly not possible in classical computational physics. We are developing a formalism for building networks manageable by walks constructed with this framework, based on the surprising efficiency of our framework in discovering internals of a simple network that we so far solved. Finally, in line with our expectation that the field of quantum walks can take cues from the rich history of development of the classical stochastic techniques, we establish starting points for the work on non-Abelian quantum walks, with a particular quantum walk analog of the classical "card shuffling," the walk on the permutation group. In summary, this thesis presents a new framework for construction of discrete time quantum walks, employing and exploring memoried nature of unitary evolution. It is applied to fully solving the problems of: A walk on the binary tree and exploration of the quantum-to-classical transition with increased correlation length (history). It is then used for simple network discovery, and to lay the groundwork for analysis of complex networks, based on combined power of efficient exploration of the Hilbert space (as a walk mixing components) and Fourier transformation (since we can choose this for the evolution operator). We hope to establish this as a general technique as its power would be unmatched by any approaches available in the classical computing. We also looked at the promising and challenging prospect of walks on non-Abelian structures by setting up the problem of "quantum card shuffling," a quantum walk on the permutation group. Relation to other work is thoroughly discussed throughout, along with examination of the context of our work and overviews of our current and future work. / Graduation date: 2012

This thesis is on the existence and uniqueness of weak solutions to the Navier-Stokes equations in R3 which govern the velocity of incompressible fluid with viscosity ν. The solution is obtained in the space of tempered distributions on R3 given an initial condition and forcing data which are dominated by majorizing kernels. The solution takes the form of an expectation of functionals on a Markov process indexed by a binary branching tree. / Graduation date: 2012

Recently the independent multinomial selections model (IMS) with the multinomial logit link has been suggested as an analysis tool for radio-telemetry habitat selection data. This model assumes independence between animals, independence between sightings within an animal, and identical multinomial habitat selection probabilities for all animals. We propose two generalizations to the IMS model. The first generalization is to allow a Markov chain dependence between consecutive sightings of the same animal. This generalization allows for both positive correlation (individuals persisting in the same habitat class in which they were previously sighted) and negative correlation (individual vacating the habitat class in which they were previously sighted). The second generalization is to allow for heterogeneity. Here, a hierarchical Dirichlet-multinomial distribution is used to allow for variability in selection probabilities between animals. This generalization accounts for over-dispersion of selection probabilities and allows for inference to the population of animals, assuming that the animals studied constitute a random sample from that population.. Both generalizations are one parameter extensions to the multinomial logit model and allow for testing the assumptions of identical multinomial selection probabilities and independence. These tests are performed using the score, Wald, and asymptotic likelihood ratio statistics. Estimates of model parameters are obtained using maximum likelihood techniques, and habitat characteristics are tested using drop-in-deviance statistics. Using example data, we show that persistence and heterogeneity exist in habitat selection data and illustrate the difference in analysis results between the IMS model and the persistence and heterogeneity models. Through simulation, we show that analyzing persistence data assuming independence between sightings within an animal gives liberal tests of significance for habitat characteristics when the data are generated with positive correlation and conservative tests of significance when the data are generated with negative correlation. Similarly, we show that analyzing heterogeneous data, assuming identical multinomial selection probabilities, gives liberal tests of significance for habitat characteristics. / Graduation date: 2001

We formalize and analyze the notions of monotonicity and complete monotonicity for Markov Chains in continuous-time, taking values in a finite partially ordered set. Similarly to what happens in discrete-time, the two notions are not equivalent. However, we show that there are partially ordered sets for which monotonicity and complete monotonicity coincide in continuoustime but not in discrete-time.

In the living cell, the organization of the complex internal structure relies to a large extent on molecular motors. Molecular motors are proteins that are able to convert chemical energy from the hydrolysis of adenosine triphosphate (ATP) into mechanical work. Being about 10 to 100 nanometers in size, the molecules act on a length scale, for which thermal collisions have a considerable impact onto their motion. In this way, they constitute paradigmatic examples of thermodynamic machines out of equilibrium. This study develops a theoretical description for the energy conversion by the molecular motor myosin V, using many different aspects of theoretical physics. Myosin V has been studied extensively in both bulk and single molecule experiments. Its stepping velocity has been characterized as a function of external control parameters such as nucleotide concentration and applied forces. In addition, numerous kinetic rates involved in the enzymatic reaction of the molecule have been determined. For forces that exceed the stall force of the motor, myosin V exhibits a 'ratcheting' behaviour: For loads in the direction of forward stepping, the velocity depends on the concentration of ATP, while for backward loads there is no such influence. Based on the chemical states of the motor, we construct a general network theory that incorporates experimental observations about the stepping behaviour of myosin V. The motor's motion is captured through the network description supplemented by a Markov process to describe the motor dynamics. This approach has the advantage of directly addressing the chemical kinetics of the molecule, and treating the mechanical and chemical processes on equal grounds. We utilize constraints arising from nonequilibrium thermodynamics to determine motor parameters and demonstrate that the motor behaviour is governed by several chemomechanical motor cycles. In addition, we investigate the functional dependence of stepping rates on force by deducing the motor's response to external loads via an appropriate Fokker-Planck equation. For substall forces, the dominant pathway of the motor network is profoundly different from the one for superstall forces, which leads to a stepping behaviour that is in agreement with the experimental observations. The extension of our analysis to Markov processes with absorbing boundaries allows for the calculation of the motor's dwell time distributions. These reveal aspects of the coordination of the motor's heads and contain direct information about the backsteps of the motor. Our theory provides a unified description for the myosin V motor as studied in single motor experiments. / Die hier vorgelegte Arbeit entwickelt unter Verwendung vieler verschiedener Aspekte der statistischen Physik eine Theorie der chemomechanischen Kopplung für den Energieumsatz des molekularen Motors Myosin V. Das Myosin V ist sowohl in chemokinetischen wie in Einzelmolekülexperimenten grundlegend untersucht worden. Seine Schrittgeschwindigkeit ist in Abhängigkeit verschiedener externer Parameter, wie der Nukleotidkonzentration und einer äußeren Kraft, experimentell bestimmt. Darüber hinaus ist eine große Anzahl verschiedener chemokinetischer Raten, die an der enzymatischen Reaktion des Moleküls beteiligt sind, quantitativ erfasst. Unter der Wirkung externer Kräfte, die seine Anhaltekraft überschreiten, verhält sich der Motor wie eine Ratsche: Für Kräfte, die entlang der Schrittbewegung des Motors wirken, hängt seine Geschwindigkeit von der ATP-Konzentration ab, für rückwärts angreifende Kräfte jedoch ist die Bewegung des Motors unabhängig von ATP. Auf der Grundlage der chemischen Zustände des Motors wird eine Netzwerktheorie aufgebaut, die die experimentellen Beobachtungen des Schrittverhaltens für Myosin V einschließt. Diese Netzwerkbeschreibung dient als Grundlage für einen Markovprozess, der die Dynamik des Motors beschreibt. Die Verwendung diskreter Zustände bietet den Vorteil der direkten Erfassung der chemischen Kinetik des Moleküls. Darüber hinaus werden chemische und mechanische Eigenschaften des Motors in gleichem Maße im Modell berücksichtigt. Durch die Erfassung der Enzymkinetik mittels eines stochastischen Prozesses lässt sich die Motordynamik mit Hilfe des stationären Zustands der Netzwerkdarstellung beschreiben. Um diesen zu bestimmen, verwenden wir eine graphentheoretische Methode, die auf Kirchhoff zurückgreift. Wir zeigen in Einklang mit den Gesetzen der Thermodynamik für Nichtgleichgewichtssysteme, dass das Schrittverhalten des Motors von mehreren chemomechanischen Zyklen beeinflusst wird. Weiterhin untersuchen wir das funktionale Verhalten mechanischer Schrittraten in Abhängigkeit der äußeren Kraft unter Verwendung einer geeigneten Fokker-Planck-Gleichung. Hierfür wird auf die Theorie einer kontinuierlichen Beschreibung von molekularen Methoden zurückgegriffen. Wir berechnen Größen wie die mittlere Schrittgeschwindigkeit, das Verhältnis von Vorwärts- und Rückwärtsschritten, und die Lauflänge des Motors in Abhängigkeit einer äußeren angreifenden Kraft sowie der Nukleotidkonzentration, und vergleichen diese mit experimentellen Daten. Für Kräfte, die kleiner als die Anhaltekraft des Motors sind, unterscheidet sich der chemomechanische Zyklus grundlegend von demjenigen, der für große Kräfte dominiert. Diese Eigenschaft resultiert in einem Schrittverhalten, das mit den experimentellen Beobachtungen übereinstimmt. Es ermöglicht weiterhin die Zerlegung des Netzwerks in einzelne Zyklen, die die Bewegung des Motors für verschiedene Bereiche externer Kräfte erfassen. Durch die Erweiterung unseres Modells auf Markovprozesse mit absorbierenden Zuständen können so die Wartezeitenverteilungen für einzelne Zyklen des Motors analytisch berechnet werden. Sie erteilen Aufschluss über die Koordination des Motors und enthalten zudem direkte Informationen über seine Rückwärtsschritte, die experimentell nicht erfasst sind. Für das gesamte Netzwerk werden die Wartezeitenverteilungen mit Hilfe eines Gillespie-Algorithmus bestimmt. Unsere Theorie liefert eine einheitliche Beschreibung der Eigenschaften von Myosin V, die in Einzelmolekülexperimenten erfasst werden können.

<p>This thesis presents a system for performing whole gesture recognition for South African Sign Language. The system uses feature vectors combined with Hidden Markov models. In order to constuct a feature vector, dynamic segmentation must occur to extract the signer&rsquo / s hand movements. Techniques and methods for normalising variations that occur when recording a signer performing a gesture, are investigated. The system has a classification rate of 69%</p>

<p>Recognising and estimating gestures is a fundamental aspect towards translating from a sign language to a spoken language. It is a challenging problem and at the same time, a growing phenomenon in Computer Vision. This thesis presents two approaches, an example-based and a learning-based approach, for performing integrated detection, segmentation and 3D estimation of the human upper body from a single camera view. It investigates whether an upper body pose can be estimated from a database of exemplars with labelled poses. It also investigates whether an upper body pose can be estimated using skin feature extraction, Support Vector Machines (SVM) and a 3D human body model. The example-based and learning-based approaches obtained success rates of 64% and 88%, respectively. An analysis of the two approaches have shown that, although the learning-based system generally performs better than the example-based system, both approaches are suitable to recognise and estimate upper body poses in a South African sign language recognition and translation system.</p>

I denna avhandling studerar vi nödvändiga och tillräckliga villkor för svag konvergens av första-sällan-händelsetider för semi-Markovska processer. I introduktionen ger vi nödvändiga grundläggande definitioner och beskrivningar av modeller som betraktas i avhandlingen, samt ger några exempel på situationer i vilka metoder av första-sällan-händelsetider kan vara lämpliga att använda. Dessutom analyserar vi publicerade resultat om asymptotiska problem för stokastiska funktionaler som definieras på semi-Markovska processer. I artikel A betraktar vi första-sällan-händelsetider för semi-Markovska processer med en ändlig mängd av lägen. Vi ger också en sammanfattning av våra resultat om nödvändiga och tillräckliga villkor för svag konvergens, samt diskuterar möjliga tillämpningar inom aktuarie-området. I artikel B redovisar vi i detalj de resultat som annonseras i artikel A och bevisen för dem. Vi ger också nödvändiga och tillräckliga villkor för svag konvergens av första-sällan-händelsetider för semi-Markovska processer med en ändlig mängd av lägen i ett icke-triangulärt tillstånd. Dessutom beskriver vi med hjälp av Laplacetransformationen klassen av alla möjliga gränsfördelningar. I artikel C studerar vi villkor av svag konvergens av flöden av sällan-händelser i ett icke-triangulärt tillstånd. Vi formulerar nödvändiga och tillräckliga villkor för konvergens, och beskriver klassen av alla möjliga gränsflöden. Vi tillämpar också våra resultat i asymptotisk analys av icke-ruin-sannolikheten för störda riskprocesser. I artikel D ger vi nödvändiga och tillräckliga villkor för svag konvergens av första-sällan-händelsetider för semi-Markovska rocesser med en ändlig mängd av lägen i ett triangulärt tillstånd, samt beskriver klassen av alla möjliga gränsfördelningar. Resultaten utvidgar slutsatser från artikel B till att gälla för ett allmänt triangulärt tillstånd. I artikel E ger vi nödvändiga och tillräckliga villkor för svag konvergens av flöden av sällan-händelser för semi-Markovska processer i ett triangulärt tillstånd. Detta generaliserar resultaten från artikel C till att beskriva ett allmänt triangulärt tillstånd. Vidare ger vi tillämpningar av våra resultat på asymptotiska problem av störda riskprocesser och till kösystemen med snabb service. / In this thesis we study necessary and sufficient conditions for weak convergence of first-rare-event times for semi-Markov processes, we describe the class of all possible limit distributions, and give the applications of the results to risk theory and queueing systems. In paper <b>A</b>, we consider first-rare-event times for semi-Markov processes with a finite set of states, and give a summary of our results concerning necessary and sufficient conditions for weak convergence of first-rare-event times and their actuarial applications. In paper <b>B</b>, we present in detail results announced in paper <b>A</b> as well as their proofs. We give necessary and sufficient conditions for weak convergence of first-rare-event times for semi-Markov processes with a finite set of states in non-triangular-array mode and describe the class of all possible limit distributions in terms of their Laplace transforms. In paper <b>C</b>, we study the conditions for weak convergence for flows of rare events for semi-Markov processes with a finite set of states in non-triangular array mode. We formulate necessary and sufficient conditions of convergence and describe the class of all possible limit stochastic flows. In the second part of the paper, we apply our results to the asymptotical analysis of non-ruin probabilities for perturbed risk processes. In paper <b>D</b>, we give necessary and sufficient conditions for the weak convergence of first-rare-event times for semi-Markov processes with a finite set of states in triangular array mode as well as describing the class of all possible limit distributions. The results of paper <b>D</b> extend results obtained in paper <b>B</b> to a general triangular array mode. In paper <b>E</b>, we give the necessary and sufficient conditions for weak convergence for the flows of rare events for semi-Markov processes with a finite set of states in triangular array case. This paper generalizes results obtained in paper <b>C</b> to a general triangular array mode. In the second part of the paper, we present applications of our results to asymptotical problems of perturbed risk processes and to queueing systems with quick service

We developed a new program called GeneTack for ab initio frameshift detection in intronless protein-coding nucleotide sequences. The GeneTack program uses a hidden Markov model (HMM) of a genomic sequence with possibly frameshifted protein-coding regions. The Viterbi algorithm nds the maximum likelihood path that discriminates between true adjacent genes and a single gene with a frameshift. We tested GeneTack as well as two other earlier developed programs FrameD and FSFind on 17 prokaryotic genomes with frameshifts introduced randomly into known genes. We observed that the average frameshift prediction accuracy of GeneTack, in terms of (Sn+Sp)/2 values, was higher by a signicant margin than the accuracy of the other two programs. GeneTack was used to screen 1,106 complete prokaryotic genomes and 206,991 genes with frameshifts (fs-genes) were identifed. Our goal was to determine if a frameshift transition was due to (i) a sequencing error, (ii) an indel mutation or (iii) a recoding event. We grouped 102,731 genes with frameshifts (fs-genes) into 19,430 clusters based on sequence similarity between their protein products (fs-proteins), conservation of predicted frameshift position, and its direction. While fs-genes in 2,810 clusters were classied as conserved pseudogenes and fs-genes in 1,200 clusters were classied as hypothetical pseudogenes, 5,632 fs-genes from 239 clusters pos- sessing conserved motifs near frameshifts were predicted to be recoding candidates. Experiments were performed for sequences derived from 20 out of the 239 clusters; programmed ribosomal frameshifting with eciency higher than 10% was observed for four clusters. GeneTack was also applied to 1,165,799 mRNAs from 100 eukaryotic species and 45,295 frameshifts were identied. A clustering approach similar to the one used for prokaryotic fs-genes allowed us to group 12,103 fs-genes into 4,087 clusters. Known programmed frameshift genes were among the obtained clusters. Several clusters may correspond to new examples of dual coding genes. We developed a web interface to browse a database containing all the fs-genes predicted by GeneTack in prokaryotic genomes and eukaryotic mRNA sequences. The fs-genes can be retrieved by similarity search to a given query sequence, by fs- gene cluster browsing, etc. Clusters of fs-genes are characterized with respect to their likely origin, such as pseudogenization, phase variation, programmed frameshifts etc. All the tools and the database of fs-genes are available at the GeneTack web site http://topaz.gatech.edu/GeneTack/