In this paper, we identify sufficient conditions for Lyapunov Mean Square Stability (LMSS) of a contention-based network of first-order systems, with state-based schedulers. The stability analysis helps us to choose policies for adapting the scheduler threshold to the delay from the network and scheduler. We show that three scheduling laws can result in LMSS: constant-probability laws and additively increasing or decreasing probability laws. Our results counter the notions that increasing probability scheduling laws alone can guarantee stability of the closed-loop system, or that decreasing probability scheduling laws are required to mitigate congestion in the network. / <p>QC 20130116</p>

This thesis considered the connections between parabolic partial differential equations of the diffusion type and Gaussian-Markov stochastic processes, in particular the Wiener process. A method has been developed by which certain Wiener integrals of the type∫C0[0,1] exp{t/a ∫1/0 e[t(1-s), 2 √(t/a) x(s) =ξ] ds} o [2√(t/a) x(1) – ξ] dwxHave been obtained as solutions of non-homogeneous heat equations. In the appendix the method has been extended to the evaluation of Wiener integrals of the type,∫C0 [0,t] exp {∫t/0 e [t-s, x(s) + ξ] ds} o [x(s) + ξ] dwx.In addition an inequality which gives bounds for Wiener integrals of the type∫C0 [s,t] exp {-∫t/s F[x( r )] dr} dwx has been deduced.Further, certain parabolic partial differential equations have been solved by building suitable Green’s functions through Gaussian-Markov stochastic processes. Two stochastic processes which exhibit certain interesting features have been obtained and briefly discussed.Ball State UniversityMuncie, IN 47306

Spin systems are powerful mathematical models widely used and studied in Statistical Physics and Computer Science. This thesis focuses the study of spin systems on colorings and weighted independent sets (the hard-core model). In many spin systems, there exist phase transition phenomena: there is a threshold value of a parameter such that when the parameter is on one side of the threshold, the system exhibits the so-called spatial decay of correlation, i.e., the influence from a set of vertices to another set of vertices diminishes as the distance between the two sets grows; when the parameter is on the other side, long range correlations persist. The uniqueness problem and the reconstruction problem are two major threshold problems that are concerned with the decay of correlations in the Gibbs measure from different perspectives. In Computer Science, the study of spin systems mainly focused on finding an efficient algorithm that samples the configurations from a distribution that is very close to the Gibbs measure. Glauber dynamics is a typical Markov chain algorithm for performing sampling. In many systems, the convergence time of the Glauber dynamics also exhibits a threshold behavior: the speed of convergence experiences a dramatic change around the threshold of the parameter. The first two parts of this thesis focus on making connections between the phase transition of the convergence time of the dynamics and the phase transition of the reconstruction phenomenon in both colorings and the hard-core model on regular trees. A relatively sharp threshold is established for the change of the convergence time, which coincides with the reconstruction threshold. A general technique of upper bounding the conductance of the dynamics via analyzing the sensitivity of the reconstruction algorithm is proposed and proven to be very effective for lower bounding the convergence time of the dynamics. The third part of the thesis provides an innovative analytical method for establishing a strong version of the decay of correlation of the Gibbs distributions for many two spin systems on various classes of graphs. In particular, the method is applied to the hard-core model on the square lattice, a very important graph that is of great interest in both Statistical Physics and Computer Science. As a result, we significantly improve the lower bound of the uniqueness threshold on the square lattice and extend the range of parameter where the Glauber dynamics is rapidly mixing.

No description available.

We give an upper bound for the norm distance of (0,1) -valued Markov-exchangeable random variables to mixtures of distributions of Markov processes. A Markov-exchangeable random variable has a distribution that depends only on the starting value and the number of transitions 0-0, 0-1, 1-0 and 1-1. We show that if, for increasing length of variables, the norm distance to mixtures of Markov processes goes to 0, the rate of this convergence may be arbitrarily slow. (author's abstract) / Series: Forschungsberichte / Institut für Statistik

No description available.

This thesis proposes a computationally effective analytical approach to automated material handling system (AMHS) performance modeling for a simple closed loop AMHS, such as is typical in supporting a 300mm wafer fab bay. Discrete-event simulation can produce accurate assessments of the production performance, including the contribution by the AMHS. However, the corresponding simulation models are both expensive and time-consuming to construct, and require long execution times to produce statistically valid estimates. These attributes render simulation ineffective as a decision support tool in the early phase of system design, where requirements and configurations are likely to change often. We propose an alternative model that estimates the AMHS performance considering the possibility of vehicle-blocking. A probabilistic model is developed, based on a detailed description of AMHS operations, and the system is analyzed as an extended Markov chain. The model tracks the operations of all the vehicles on the closed-loop considering the possibility of vehicle-blocking. The resulting large-scale model provided reasonably accurate performance estimates; however, it presented some computational challenges. These computational challenges motivated the development of a second model that also analyzes the system as an extended Markov chain but with a much reduced state space because the model tracks the movement of a single vehicle in the system with additional assumptions on vehicle-blocking. Neither model is a conventional Markov Chain because they combine the conventional Markov Chain analysis of the AMHS operations with additional constraints on AMHS stability and vehicle-blocking that are necessary to provide a unique solution to the steady-state behavior of the AMHS. Based on the throughput capacity model, an approach is developed to approximate the expected response time of the AMHS to move requests. The expected response times are important to measure the performance of the AMHS and for estimating the required queue capacity at each pick-up station. The derivation is not straightforward and especially complicated for multi-vehicle systems. The approximation relies on the assumption that the response time is a function of the distribution of the vehicles along the tracks and the expected length of the path from every possible location to the move request location.

A metagenome originated from a shotgun sequencing of a microbial community is a heterogeneous mixture of rather short sequences. A vast majority of microbial species in a given community (99%) are likely to be non-cultivable. Many protein-coding regions in a new metagenome are likely to code for barely detectable homologs of already known proteins. Therefore, an ab initio method that would accurately identify the new genes is a vitally important tool of metagenomic sequence analysis. However, a heuristic model method for finding genes in short prokaryotic sequences with anonymous origin was proposed in 1999 prior to the advent of metagenomics. With hundreds of new prokaryotic genomes available it is now possible to enhance the original approach and to utilize direct polynomial and logistic approximations of oligonucleotide frequencies. The idea was to bypass traditional ways of parameter estimation such as supervised training on a set of validated genes or unsupervised training on an anonymous sequence supposed to contain a large enough number of genes. The codon frequencies, critical for the model parameterization, could be derived from frequencies of nucleotides observed in the short sequence. This method could be further applied for initializing the algorithms for iterative parameters estimation for prokaryotic as well as eukaryotic gene finders.

The term resource is used to refer to a machine, tool-group, piece of equipment or personnel. Optimization models for resource maintenance are obtained in conjunction with other production related decisions like production planning, production scheduling, resource allocation and job inspection. Emphasis is laid on integrating the above inter-dependent decisions into a unified optimization framework. This is accomplished for large stationary resources, small non-stationary resources with high breaking rate and for resources that form a part of a network. Owing to large problem size and high uncertainty, the optimal decisions are determined by formulating and solving the above problems as Markov decision processes (MDPs). Approximate dynamic programming based algorithms are used for solving the large optimization problems at hand. The performance of resulting near optimal policies is compared with that of traditional formulations in all cases. The latter treat the resource maintenance decisions independent of other manufacturing related decisions. In certain formulations, the resource state is not completely observable. This results in a partially observable MDP (POMDP). An alternative algorithm for the solution of POMDP is developed, where several mixed integer linear programs (MILPs) are solved during each ADP iteration. This helps obtain better quality solutions for the POMDPs with very large or continuous action spaces in an efficient manner.

Multi-hop wireless transmission, where radios forward the message of other radios, is becoming popular both in cellular as well as sensor networks. This research is concerned with the statistical modeling of multi-hop wireless networks that do cooperative transmission (CT). CT is a physical layer wireless communication scheme in which spatially separated wireless nodes collaborate to form a virtual array antenna for the purpose of increased reliability. The dissertation has two major parts. The first part addresses a special form of CT known as the Opportunistic Large Array (OLA). The second part addresses the signal-to-noise ratio (SNR) estimation for the purpose of recruiting nodes for CT. In an OLA transmission, the nodes from one level transmit the message signal concurrently without any coordination with each other, thereby producing transmit diversity. The receiving layer of nodes receives the message signal and repeats the process using the decode-and-forward cooperative protocol. The key contribution of this research is to model the transmissions that hop from one layer of nodes to another under the effects of channel variations, carrier frequency offsets, and path loss. It has been shown for a one-dimensional network that the successive transmission process can be modeled as a quasi-stationary Markov chain in discrete time. By studying various properties of the Markov chain, the system parameters, for instance, the transmit power of relays and distance between them can be optimized. This optimization is used to improve the performance of the system in terms of maximum throughput, range extensions, and minimum delays while delivering the data to the destination node using the multi-hop wireless communication system. A major problem for network sustainability, especially in battery-assisted networks, is that the batteries are drained pretty quickly during the operation of the network. However, in dense sensor networks, this problem can be alleviated by using a subset of nodes which take part in CT, thereby saving the network energy. SNR is an important parameter in determining which nodes to participate in CT. The more distant nodes from the source having least SNR are most suitable to transmit the message to next level. However, practical real-time SNR estimators are required to do this job. Therefore, another key contribution of this research is the design of optimal SNR estimators for synchronized as well as non-synchronized receivers, which can work with both the symbol-by-symbol Rayleigh fading channels as well as slow flat fading channels in a wireless medium.