Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userIntuitive Analyses via Drift Theory
58
0
0.0
(
0
)
Added by
Martin Krejca
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Humans are bad with probabilities, and the analysis of randomized algorithms offers many pitfalls for the human mind. Drift theory is an intuitive tool for reasoning about random processes. It allows turning expected stepwise changes into expected first-hitting times. While drift theory is used extensively by the community studying randomized search heuristics, it has seen hardly any applications outside of this field, in spite of many research questions which can be formulated as first-hitting times. We state the most useful drift theorems and demonstrate their use for various randomized processes, including approximating vertex cover, the coupon collector process, a random sorting algorithm, and the Moran process. Finally, we consider processes without expected stepwise change and give a lemma based on drift theory applicable in such scenarios without drift. We use this tool for the analysis of the gamblers ruin process, for a coloring algorithm, for an algorithm for 2-SAT, and for a version of the Moran process without bias.
rate research
Read More
Abstract polymer models are systems of weighted objects, called polymers, equipped with an incompatibility relation. An important quantity associated with such models is the partition function, which is the weighted sum over all sets of compatible polymers. Various approximation problems reduce to approximating the partition function of a polymer model. Central to the existence of such approximation algorithms are weight conditions of the respective polymer model. Such conditions are derived either via complex analysis or via probabilistic arguments. We follow the latter path and establish a new condition---the clique dynamics condition---, which is less restrictive than the ones in the literature. We introduce a new Markov chain where the clique dynamics condition implies rapid mixing by utilizing cliques of incompatible polymers that naturally arise from the translation of algorithmic problems into polymer models. This leads to improved parameter ranges for several approximation algorithms, such as a factor of at least $2^{1/alpha}$ for the hard-core model on bipartite $alpha$-expanders.
The aim of this paper is to study the asymptotic properties of the maximum likelihood estimator (MLE) of the drift coefficient for fractional stochastic heat equation driven by an additive space-time noise. We consider the traditional for stochastic partial differential equations statistical experiment when the measurements are performed in the spectral domain, and in contrast to the existing literature, we study the asymptotic properties of the maximum likelihood (type) estimators (MLE) when both, the number of Fourier modes and the time go to infinity. In the first part of the paper we consider the usual setup of continuous time observations of the Fourier coefficients of the solutions, and show that the MLE is consistent, asymptotically normal and optimal in the mean-square sense. In the second part of the paper we investigate the natural time discretization of the MLE, by assuming that the first N Fourier modes are measured at M time grid points, uniformly spaced over the time interval [0,T]. We provide a rigorous asymptotic analysis of the proposed estimators when N goes to infinity and/or T, M go to infinity. We establish sufficient conditions on the growth rates of N, M and T, that guarantee consistency and asymptotic normality of these estimators.
For the last ten years, almost every theoretical result concerning the expected run time of a randomized search heuristic used drift theory, making it the arguably most important tool in this domain. Its success is due to its ease of use and its powerful result: drift theory allows the user to derive bounds on the expected first-hitting time of a random process by bounding expected local changes of the process -- the drift. This is usually far easier than bounding the expected first-hitting time directly. Due to the widespread use of drift theory, it is of utmost importance to have the best drift theorems possible. We improve the fundamental additive, multiplicative, and variable drift theorems by stating them in a form as general as possible and providing examples of why the restrictions we keep are still necessary. Our additive drift theorem for upper bounds only requires the process to be nonnegative, that is, we remove unnecessary restrictions like a finite, discrete, or bounded search space. As corollaries, the same is true for our upper bounds in the case of variable and multiplicative drift.
For a spatial characteristic, there exist commonly fat-tail frequency distributions of fragment-size and -mass of glass, areas enclosed by city roads, and pore size/volume in random packings. In order to give a new analytical approach for the distributions, we consider a simple model which constructs a fractal-like hierarchical network based on random divisions of rectangles. The stochastic process makes a Markov chain and corresponds to directional random walks with splitting into four particles. We derive a combinatorial analytical form and its continuous approximation for the distribution of rectangle areas, and numerically show a good fitting with the actual distribution in the averaging behavior of the divisions.
Consider a reflecting diffusion in a domain in $R^d$ that acquires drift in proportion to the amount of local time spent on the boundary of the domain. We show that the stationary distribution for the joint law of the position of the reflecting process and the value of the drift vector has a product form. Moreover, the first component is the symmetrizing measure on the domain for the reflecting diffusion without inert drift, and the second component has a Gaussian distribution. We also consider processes where the drift is given in terms of the gradient of a potential.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
