اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدThe accessibility of convex bodies and derandomization of the hit and run algorithm
39
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We introduce the concept of accessibility and prove that any convex body $X$ in $mathbb R^d$ is accessible with relevant constants depending on $d$ only. This property leads to a new algorithm which may be considered as a natural derandomization of the hit and run algorithm applied to generate a sequence of random points covering $X$ uniformly. We prove stability of the Markov chain generated by the proposed algorithm and provide its rate of convergence.
قيم البحث
اقرأ أيضاً
Estimating the volume of a convex body is a central problem in convex geometry and can be viewed as a continuous version of counting. We present a quantum algorithm that estimates the volume of an $n$-dimensional convex body within multiplicative err
or $epsilon$ using $tilde{O}(n^{3}+n^{2.5}/epsilon)$ queries to a membership oracle and $tilde{O}(n^{5}+n^{4.5}/epsilon)$ additional arithmetic operations. For comparison, the best known classical algorithm uses $tilde{O}(n^{4}+n^{3}/epsilon^{2})$ queries and $tilde{O}(n^{6}+n^{5}/epsilon^{2})$ additional arithmetic operations. To the best of our knowledge, this is the first quantum speedup for volume estimation. Our algorithm is based on a refined framework for speeding up simulated annealing algorithms that might be of independent interest. This framework applies in the setting of Chebyshev cooling, where the solution is expressed as a telescoping product of ratios, each having bounded variance. We develop several novel techniques when implementing our framework, including a theory of continuous-space quantum walks with rigorous bounds on discretization error.
We present a general method to derive continuity estimates for conditional probabilities of general (possibly continuous) spin models sub jected to local transformations. Such systems arise in the study of a stochastic time-evolution of Gibbs measure
s or as noisy observations. We exhibit the minimal necessary structure for such double-layer systems. Assuming no a priori metric on the local state spaces, we define the posterior metric on the local image space. We show that it allows in a natural way to divide the local part of the continuity estimates from the spatial part (which is treated by Dobrushin uniqueness here). We show in the concrete example of the time evolution of rotators on the q-1 dimensional sphere how this method can be used to obtain estimates in terms of the familiar Euclidean metric.
We introduce a Gibbs measure on nearest-neighbour paths of length $t$ in the Euclidean $d$-dimensional lattice, where each path is penalised by a factor proportional to the size of its boundary and an inverse temperature $beta$. We prove that, for al
l $beta>0$, the random walk condensates to a set of diameter $(t/beta)^{1/3}$ in dimension $d=2$, up to a multiplicative constant. In all dimensions $dge 3$, we also prove that the volume is bounded above by $(t/beta)^{d/(d+1)}$ and the diameter is bounded below by $(t/beta)^{1/(d+1)}$. Similar results hold for a random walk conditioned to have local time greater than $beta$ everywhere in its range when $beta$ is larger than some explicit constant, which in dimension two is the logarithm of the connective constant.
We prove that there exists an absolute constant $alpha >1$ with the following property: if $K$ is a convex body in ${mathbb R}^n$ whose center of mass is at the origin, then a random subset $Xsubset K$ of cardinality ${rm card}(X)=lceilalpha nrceil $
satisfies with probability greater than $1-e^{-n}$ {Ksubseteq c_1n,{mathrm conv}(X),} where $c_1>0$ is an absolute constant. As an application we show that the vertex index of any convex body $K$ in ${mathbb R}^n$ is bounded by $c_2n^2$, where $c_2>0$ is an absolute constant, thus extending an estimate of Bezdek and Litvak for the symmetric case.
The Brownian web (BW), which developed from the work of Arratia and then T{o}th and Werner, is a random collection of paths (with specified starting points) in one plus one dimensional space-time that arises as the scaling limit of the discrete web (
DW) of coalescing simple random walks. Two recently introduced extensions of the BW, the Brownian net (BN) constructed by Sun and Swart, and the dynamical Brownian web (DyBW) proposed by Howitt and Warren, are (or should be) scaling limits of corresponding discrete extensions of the DW -- the discrete net (DN) and the dynamical discrete web (DyDW). These discrete extensions have a natural geometric structure in which the underlying Bernoulli left or right arrow structure of the DW is extended by means of branching (i.e., allowing left and right simultaneously) to construct the DN or by means of switching (i.e., from left to right and vice-versa) to construct the DyDW. In this paper we show that there is a similar structure in the continuum where arrow direction is replaced by the left or right parity of the (1,2) space-time points of the BW (points with one incoming path from the past and two outgoing paths to the future, only one of which is a continuation of the incoming path). We then provide a complete construction of the DyBW and an alternate construction of the BN to that of Sun and Swart by proving that the switching or branching can be implemented by a Poissonian marking of the (1,2) points.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
