共查询到20条相似文献，搜索用时 0 毫秒
1.
The following question is due to Chatterjee and Varadhan (2011). Fix and take , the Erd?s‐Rényi random graph with edge density p, conditioned to have at least as many triangles as the typical . Is G close in cut‐distance to a typical ? Via a beautiful new framework for large deviation principles in , Chatterjee and Varadhan gave bounds on the replica symmetric phase, the region of where the answer is positive. They further showed that for any small enough p there are at least two phase transitions as r varies. We settle this question by identifying the replica symmetric phase for triangles and more generally for any fixed d‐regular graph. By analyzing the variational problem arising from the framework of Chatterjee and Varadhan we show that the replica symmetry phase consists of all such that lies on the convex minorant of where is the rate function of a binomial with parameter p. In particular, the answer for triangles involves rather than the natural guess of where symmetry was previously known. Analogous results are obtained for linear hypergraphs as well as the setting where the largest eigenvalue of is conditioned to exceed the typical value of the largest eigenvalue of . Building on the work of Chatterjee and Diaconis (2012) we obtain additional results on a class of exponential random graphs including a new range of parameters where symmetry breaking occurs. En route we give a short alternative proof of a graph homomorphism inequality due to Kahn (2001) and Galvin and Tetali (2004). © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 109–146, 2015 相似文献
2.
3.
With ξ the number of triangles in the usual (Erd?s‐Rényi) random graph G(m,p), p > 1/m and η > 0, we show (for some Cη > 0) This is tight up to the value of Cη. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 40, 452–459, 2012 相似文献
4.
What is the probability that the number of triangles in , the Erd?s‐Rényi random graph with edge density p , is at least twice its mean? Writing it as , already the order of the rate function r (n, p ) was a longstanding open problem when p = o (1), finally settled in 2012 by Chatterjee and by DeMarco and Kahn, who independently showed that for ; the exact asymptotics of r (n, p ) remained unknown. The following variational problem can be related to this large deviation question at : for δ > 0 fixed, what is the minimum asymptotic p‐relative entropy of a weighted graph on n vertices with triangle density at least (1 + δ )p 3? A beautiful large deviation framework of Chatterjee and Varadhan (2011) reduces upper tails for triangles to a limiting version of this problem for fixed p . A very recent breakthrough of Chatterjee and Dembo extended its validity to for an explicit α > 0, and plausibly it holds in all of the above sparse regime. In this note we show that the solution to the variational problem is when vs. when (the transition between these regimes is expressed in the count of triangles minus an edge in the minimizer). From the results of Chatterjee and Dembo, this shows for instance that the probability that for has twice as many triangles as its expectation is where . Our results further extend to k‐cliques for any fixed k , as well as give the order of the upper tail rate function for an arbitrary fixed subgraph when . © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 420–436, 2017 相似文献
5.
Given a fixed graph H, what is the (exponentially small) probability that the number XH of copies of H in the binomial random graph Gn,p is at least twice its mean? Studied intensively since the mid 1990s, this so‐called infamous upper tail problem remains a challenging testbed for concentration inequalities. In 2011 DeMarco and Kahn formulated an intriguing conjecture about the exponential rate of decay of for fixed ε > 0. We show that this upper tail conjecture is false, by exhibiting an infinite family of graphs violating the conjectured bound. 相似文献
6.
Generalized random graphs are considered where the presence or absence of an edge depends on the weights of its nodes. Our main interest is to investigate large deviations for the number of edges per node in such a generalized random graph, where the node weights are deterministic under some regularity conditions, as well as chosen i.i.d. from a finite set with positive components. When the node weights are random variables, obstacles arise because the independence among edges no longer exists, our main tools are some results of large deviations for mixtures. After calculating, our results show that the corresponding rate functions for the deterministic case and the random case are very different. 相似文献
7.
GAO ZhiQiang School of Mathematical Sciences Beijing Normal University Laboratory of Mathematics Complex Systems Ministry of Education Beijing China Laboratoire de Mathatiques et Applications des Mathmatiques Universit de Bretagne-Sud BP Vannes France 《中国科学 数学(英文版)》2010,(2)
Suppose that the integers are assigned i.i.d. random variables {(β gx , . . . , β 1x , α x )} (each taking values in the unit interval and the sum of them being 1), which serve as an environment. This environment defines a random walk {X n } (called RWRE) which, when at x, moves one step of length 1 to the right with probability α x and one step of length k to the left with probability β kx for 1≤ k≤ g. For certain environment distributions, we determine the almost-sure asymptotic speed of the RWRE and show that the chance of the RWRE deviating below this speed has a polynomial rate of decay. This is the generalization of the results by Dembo, Peres and Zeitouni in 1996. In the proof we use a large deviation result for the product of random matrices and some tail estimates and moment estimates for the total population size in a multi-type branching process with random environment. 相似文献
8.
This paper is a continuation of [1]-[3]. 相似文献
9.
This paper is a continuation of [1]–[2]. 相似文献
10.
This paper is a continuation of [1]. 相似文献
11.
We prove a local limit theorem (LLT) on Cramer-type large deviations for sums S
V
=
t
V (
t
), where
t
, t Z
, 1, is a Markov Gaussian random field, V Z
, and is a bounded Borel function. We get an estimate from below for the variance of S
V
and construct two classes of functions , for which the LLT of large deviations holds. 相似文献
12.
Yijun Hu 《中国科学A辑(英文版)》1997,40(7):697-706
LetX
ɛ = {X
ɛ (t ; 0 ⩽t ⩽ 1 } (ɛ > 0) be the processes governed by the following stochastic differential equations:
wherev(t) is a random process independent of the Brownian motionB(·). Some large deviation (LD) properties of { (X
ɛ, ν(.)); ɛ > 0} are proved. For a particular case, an explicit representation of the rate function is also given, which solves
a problem posed by Eizenberg and Freidlin. In the meantime, an abstract LD theorem is obtained.
Project supported by the National Natural Science Foundation of China and the State Education Commission Ph. D. Station Foundation. 相似文献
13.
Let M
n
denote the n-th moment space of the set of all probability measures on the interval [0, 1], P
n
the uniform distribution on the set M
n
and r
n + 1 the maximal range of the (n + 1)-th moments corresponding to a random moment point C
n
with distribution P
n
on M
n
. We study several asymptotic properties of the stochastic process (r
⌊nt⌋+1)
t∈[0,T] if n → ∞. In particular weak convergence to a Gaussian process and a large deviation principle are established.
相似文献
14.
M-negatively associated random variables,which generalizes the classical one of negatively associated random variables and includes m-dependent sequences as its par- ticular case,are introduced and studied.Large deviation principles and moderate devi- ation upper bounds for stationary m-negatively associated random variables are proved. Kolmogorov-type and Marcinkiewicz-type strong laws of large numbers as well as the three series theorem for m-negatively associated random variables are also given. 相似文献
15.
16.
江涛 《高校应用数学学报(A辑)》2003,18(1):77-80
设｛Xκ,κ≥1｝为一列独立同分布的非随机变量,且具有共同的分布函数F。记Sn为序列｛Xκ,κ≥1｝的前n项部分和。在F属于ERV分布族的假定下,文中证明了关于随机和SN(t)的随机中心化的精细大偏差结果。这里N（t）为一个与｛Xκ,κ≥1｝独立的非负整数值的随机过程。 相似文献
17.
18.
Let G be a k-regular vertex transitive graph with connectivity κ(G)=k and let mk(G) be the number of vertex cuts with k vertices. Define m(n,k)=min{mk(G): GTn,k}, where Tn,k denotes the set of all k-regular vertex transitive graphs on n vertices with κ(G)=k. In this paper, we determine the exact values of m(n,k). 相似文献
19.
Raphaël Cerf 《Journal of Theoretical Probability》2000,13(2):491-517
We consider supercritical two-dimensional Bernoulli percolation. Conditionally on the event that the open cluster C containing the origin is finite, we prove that: the laws of C/N satisfy a large deviations principle with respect to the Hausdorff metric; let f(N) be a function from
to
such that f(N)/ln N+ and f(N)/N0 as N goes to the laws of {x
2 : d(x, C)f(N)}/N satisfy a large deviations principle with respect to the L
1 metric associated to the planer Lebesgue measure. We link the second large deviations principle with the Wulff construction. 相似文献
20.
本文得到次线性期望下独立同分布的随机变量的样本轨道大偏差. 在次线性期望下所得的结果推广了概率空间的相应结果. 相似文献