اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدScaling limits for the threshold window: When does a monotone Boolean function flip its outcome?
38
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Consider a monotone Boolean function $f:{0,1}^nto{0,1}$ and the canonical monotone coupling ${eta_p:pin[0,1]}$ of an element in ${0,1}^n$ chosen according to product measure with intensity $pin[0,1]$. The random point $pin[0,1]$ where $f(eta_p)$ flips from $0$ to $1$ is often concentrated near a particular point, thus exhibiting a threshold phenomenon. For a sequence of such Boolean functions, we peer closely into this threshold window and consider, for large $n$, the limiting distribution (properly normalized to be nondegenerate) of this random point where the Boolean function switches from being 0 to 1. We determine this distribution for a number of the Boolean functions which are typically studied and pay particular attention to the functions corresponding to iterated majority and percolation crossings. It turns out that these limiting distributions have quite varying behavior. In fact, we show that any nondegenerate probability measure on $mathbb{R}$ arises in this way for some sequence of Boolean functions.
قيم البحث
اقرأ أيضاً
A wide array of random graph models have been postulated to understand properties of observed networks. Typically these models have a parameter $t$ and a critical time $t_c$ when a giant component emerges. It is conjectured that for a large class of
models, the nature of this emergence is similar to that of the ErdH{o}s-Renyi random graph, in the sense that (a) the sizes of the maximal components in the critical regime scale like $n^{2/3}$, and (b) the structure of the maximal components at criticality (rescaled by $n^{-1/3}$) converges to random fractals. To date, (a) has been proven for a number of models using different techniques. This paper develops a general program for proving (b) that requires three ingredients: (i) in the critical scaling window, components merge approximately like the multiplicative coalescent, (ii) scaling exponents of susceptibility functions are the same as that of the ErdH{o}s-Renyi random graph, and (iii) macroscopic averaging of distances between vertices in the barely subcritical regime. We show that these apply to two fundamental random graph models: the configuration model and inhomogeneous random graphs with a finite ground space. For these models, we also obtain new results for component sizes at criticality and structural properties in the barely subcritical regime.
Let $mathcal{H}$ denote a collection of subsets of ${1,2,ldots,n}$, and assign independent random variables uniformly distributed over $[0,1]$ to the $n$ elements. Declare an element $p$-present if its corresponding value is at most $p$. In this pape
r, we quantify how much the observation of the $r$-present ($r>p$) set of elements affects the probability that the set of $p$-present elements is contained in $mathcal{H}$. In the context of percolation, we find that this question is closely linked to the near-critical regime. As a consequence, we show that for every $r>1/2$, bond percolation on the subgraph of the square lattice given by the set of $r$-present edges is almost surely noise sensitive at criticality, thus generalizing a result due to Benjamini, Kalai and Schramm.
Scaling limits are analyzed for stochastic continuous opinion dynamics systems, also known as gossip models. In such models, agents update their vector-valued opinion to a convex combination (possibly agent- and opinion-dependent) of their current va
lue and that of another observed agent. It is shown that, in the limit of large agent population size, the empirical opinion density concentrates, at an exponential probability rate, around the solution of a probability-measure-valued ordinary differential equation describing the systems mean-field dynamics. Properties of the associated initial value problem are studied. The asymptotic behavior of the solution is analyzed for bounded-confidence opinion dynamics, and in the presence of an heterogeneous influential environment.
Fix a space dimension $dge 2$, parameters $alpha > -1$ and $beta ge 1$, and let $gamma_{d,alpha, beta}$ be the probability measure of an isotropic random vector in $mathbb{R}^d$ with density proportional to begin{align*} ||x||^alpha, expleft(-frac{|x
|^beta}{beta}right), qquad xin mathbb{R}^d. end{align*} By $K_lambda$, we denote the Generalized Gamma Polytope arising as the random convex hull of a Poisson point process in $mathbb{R}^d$ with intensity measure $lambdagamma_{d,alpha,beta}$, $lambda>0$. We establish that the scaling limit of the boundary of $K_lambda$, as $lambda rightarrow infty$, is given by a universal `festoon of piecewise parabolic surfaces, independent of $alpha$ and $beta$. Moreover, we state a list of other large scale asymptotic results, including expectation and variance asymptotics, central limit theorems, concentration inequalities, Marcinkiewicz-Zygmund-type strong laws of large numbers, as well as moderate deviation principles for the intrinsic volumes and face numbers of $K_lambda$.
The aim of this paper is to give a precise estimate on the tail probability of the visibility function in a germ-grain model: this function is defined as the length of the longest ray starting at the origin that does not intersect an obstacle in a Bo
olean model. We proceed in two or more dimensions using coverage techniques. Moreover, convergence results involving a type I extreme value distribution are shown in the two particular cases of small obstacles or a large obstacle-free region.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
