The Markov Chain Monte Carlo (MCMC) method has been widely used in practice since the 1950's in areas such as biology, statistics, and physics. However, it is only in the last few decades that powerful techniques for obtaining rigorous performance guarantees with respect to the running time have been developed. Today, with only a few notable exceptions, most known algorithms for approximately uniform sampling and approximate counting rely on the MCMC method. This thesis focuses on algorithms that use MCMC combined with an algorithm from optimization called simulated annealing, for sampling and counting problems. Annealing is a heuristic for finding the global optimum of a function over a large search space. It has recently emerged as a powerful technique used in conjunction with the MCMC method for sampling problems, for example in the estimation of the permanent and in algorithms for computing the volume of a convex body. We examine other applications of annealing to sampling problems as well as scenarios when it fails to converge in polynomial time. We consider the problem of randomly generating 0-1 contingency tables. This is a well-studied problem in statistics, as well as the theory of random graphs, since it is also equivalent to generating a random bipartite graph with a prescribed degree sequence. Previously, the only algorithm known for all degree sequences was by reduction to approximating the permanent of a 0-1 matrix. We give a direct and more efficient combinatorial algorithm which relies on simulated annealing. Simulated tempering is a variant of annealing used for sampling in which a temperature parameter is randomly raised or lowered during the simulation. The idea is that by extending the state space of the Markov chain to a polynomial number of progressively smoother distributions, parameterized by temperature, the chain could cross bottlenecks in the original space which cause slow mixing. We show that simulated tempering mixes torpidly for the 3-state ferromagnetic Potts model on the complete graph. Moreover, we disprove the conventional belief that tempering can slow fixed temperature algorithms by at most a polynomial in the number of temperatures and show that it can converge at a rate that is slower by at least an exponential factor.

The promising development of wireless technologies has brought in an increasing demand of multimedia traffic. Since various types of traffic are inherently distinct in bandwidth requirements, delay sensitivities, and error tolerances, an adequate bandwidth allocation scheme is essential for the limited radio resource to fulfill different QoS (quality of service) requirements in mobile wireless networks. In this dissertation, we present a generalized channel preemption scheme (the GCPM) and a jamming-based medium access control with dynamic priority adjustment (the JMDPA) for the two different medium access models of a mobile wireless network, grant/request-based and contention-based, respectively. In the proposed GCPM, a mobile call is identified by four parameters, call type, traffic class, channel requirement, and preemption ratio. To effectively reduce dropping probability, high-priority handoff calls are allowed to fully or partially preempt low-priority ongoing calls when the mobile network becomes congested. An analytical model with multi-dimensional Markov chains is introduced to simultaneously investigate the effect of full and partial preemptions on the performance of a mobile wireless network. On the other hand, the proposed JMDPA scheme prioritizes a mobile node with two priorities, local and global; both of the local and global priorities can be dynamically changed based on the outcome in every contention round. Thus, any possible starvation of low-priority traffic or any ineffective contention of high-priority traffic can be avoided. A multi-dimensional Markov model, together with the scalability analysis, is introduced to evaluate the performance of the proposed JMDPA. The analytical results provide very useful guidelines to tune the QoS parameters for supporting prioritized multimedia traffic.

Thesis (Ph. D.)--University of Washington, 2003. / Vita. Includes bibliographical references (leaves 178-195).

No description available.

In the emerging aield of molecular machines, a molecular ratchet is a chemical system that allows the positional displacement of a submolecular component of be captured and directionally released. In information ratchets, the track over which a Brownian particle is to be transported is able to respond to the particle’s position. By raising energetic barriers to translation selectively behind the particle, it is possible to move the particle in a forward direction. This Thesis describes the development of a series of chemically-­‐driven information ratchets based on rotaxane architectures. Acylation of the rotaxane thread presents an impassible kinetic barrier to macrocycle shuttling. The incorporation of chiral centres into the thread allows the macrocycle’s position to have an effect on the kinetics of acylation in a chiral environment, with the result that the macrocycle is transported by successive acylation reactions in a direction speciaied by the handedness of a chiral. In Chapter One the physical principles of molecular motors are examined. It is shown that molecular motors are a subset of the much broader class of “triangular” reactions investigated by Onsager in 1931. Progress in the exciting aield of artiaicial chemical ratchets and motors is reviewed, and the deep connections between molecular motors and the cyclic reaction networks postulated to explain the origin of biological homochirality are explored. Chapter Two describes the synthesis and operation of a three-­‐compartment rotaxane information ratchet in which the macrocycle can be transported along a thread in either direction depending on the handedness of a chiral catalyst. Internal mechanisms of operation are elucidated by treating the system as a hidden Markov process. Chapter Three describes the synthesis and operation of a second-­‐generation three-­‐compartment information ratchet. A comparison between this system and that of the previous chapter sheds light on the complicated trade-­‐offs between kinetics and thermodynamics when these molecular ratchets are operated. In Chapter Four the ongoing efforts to construct extended information ratchets, incorporating many repeat units, are described. The synthesis of a aive-­‐ compartment information ratchet proved unexpectedly difaicult owing to problems of solubility. A four-­‐compartment rotaxane was easier to synthesise. Preliminary aindings suggest that an information ratchet mechanism is operating in this four-­‐compartment system.

This thesis provides a study of various boundary problems for one and two dimensional random walks. We first consider a one-dimensional random walk that starts at integer-valued height k > 0, with a lower boundary being the x-axis, and on each step moving downward with probability q being greater than or equal to the probability of going upward p. We derive the variance and the standard deviation of the number of steps T needed for the height to reach 0 from k, by first deriving the moment generating function of T. We then study two types of two-dimensional random walks with four boundaries. A Type I walk starts at integer-valued coordinates (h; k), where0 < h < m and 0 < k < n. On each step, the process moves one unit either up, down, left, or right with positive probabilities pu, pd, pl, pr, respectively, where pu + pd + pl + pr = 1. The process stops when it hits a boundary. A Type II walk is similar to a Type I walk except that on each step, the walk moves diagonally, either left and upward, left and downward, right and downward, or right and upward with positive probabilities plu, pld, prd, pru, respectively. We mainly answer two questions on these two types of two-dimensional random walks: (1) What is the probability of hitting one boundary before the others from an initial starting point? (2) What is the average number of steps needed to hit a boundary? To do so, we introduce a Markov Chains method and a System of Equations method. We then apply the obtained results to a boundary problem involving two independent one-dimensional random walks and answer various questions that arise. Finally, we develop a conjecture to calculate the probability of a two-sided downward-drifting Type II walk with even-valued starting coordinates hitting the x-axis before the y-axis, and we test the result with Mathematica simulations

Various models driven by a hidden Markov chain in discrete or continuous time are developed to capture the stylised features of market variables whose levels or values constitute as the underliers of financial derivative contracts or investment portfolios. Since the parameters are switching regimes, the changes and developments in the economy as soon as they arise are readily reflected in these models. The change of probability measure technique and the EM algorithm are fundamental techniques utilised in the optimal parameter estimation. Recursive adaptive filters for the state of the Markov chain and other auxiliary processes related to the Markov chain are derived which in turn yield self-tuning dynamic financial models. A hidden Markov model (HMM)-based modelling set-up for commodity prices is developed and the predictability of the gold market under this setting is examined. An Ornstein-Uhlenbeck (OU) model with HMM parameters is proposed and under this set-up, we address two statistical inference issues: the sensitivity of the model to small changes in parameter estimates and the selection of the optimal number of states. The extended OU model is implemented on a data set of 30-day Canadian T-bill yields. An exponential of a Markov-switching OU process plus a compound Poisson process is put forward as a model for the evolution of electricity spot prices. Using a data set compiled by Nord Pool, we illustrate the vast improvements gained in incorporating regimes in the model. A multivariate HMM is employed as a framework in providing the solutions of two asset allocation problems; one involves the mean-variance utility function and the other entails the CVaR constraint. Finally, the valuation of credit default swaps highlights the important considerations necessitated by pricing in a regime-switching environment. Certain numerical schemes are applied to obtain approximations for the default probabilities and swap rates.

The aim of this study is to analyze regional disparities and to test the convergence hypothesis across the provinces of Turkey. The study also attempts to analyze the spatial spillovers in the growth process of the provinces. The analyses cover the 1987-2001 period. Two alternative methodologies are used in the analyses. First, the methodology of &amp / #946 / -convergence based on cross-sectional regressions is used and effects of spatial dependence are analyzed using spatial econometric techniques. Second, Markov chain analysis is used and spatial dependence is integrated using spatial Markov chains. Results of both methodologies signal nonexistence of convergence and existence of spatial spillovers in the growth process of provinces.

<p>Cloud computing appears to be a paradigm shift in service oriented computing. Massively scalable Cloud architectures are spawned by new business and social applications as well as Internet driven economics. Besides being inherently large scale and highly distributed, Cloud systems are almost always virtualized and operate in automated shared environments. The deployed Cloud services are still in their infancy and a variety of research challenges need to be addressed to predict their long-term behavior. Performance and dependability of Cloud services are in general stochastic in nature and they are affected by a large number of factors, e.g., nature of workload and faultload, infrastructure characteristics and management policies. As a result, developing scalable and predictive analytics for Cloud becomes difficult and non-trivial. This dissertation presents the research framework needed to develop high fidelity stochastic models for large scale enterprise systems using Cloud computing as an example. Throughout the dissertation, we show how the developed models are used for: (i) performance and availability analysis, (ii) understanding of power-performance trade-offs, (ii) resiliency quantification, (iv) cost analysis and capacity planning, and (v) risk analysis of Cloud services. In general, the models and approaches presented in this thesis can be useful to a Cloud service provider for planning, forecasting, bottleneck detection, what-if analysis or overall optimization during design, development, testing and operational phases of a Cloud.</p> / Dissertation

Diss. (sammanfattning) Stockholm : Karol. inst., 2006. / Härtill 4 uppsatser.