Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA note on the Poincare and Cheeger inequalities for simple random walk on a connected graph
103
0
0.0
(
0
)
Authors
John Pike
Ask ChatGPT about the research
No Arabic abstract
In 1991, Persi Diaconis and Daniel Stroock obtained two canonical path bounds on the second largest eigenvalue for simple random walk on a connected graph, the Poincare and Cheeger bounds, and they raised the question as to whether the Poincare bound is always superior. In this paper, we present some background on these issues, provide an example where Cheeger beats Poincare, establish some sufficient conditions on the canonical paths for the Poincare bound to triumph, and show that there is always a choice of paths for which this happens.
rate research
Read More
We define a correlated random walk (CRW) induced from the time evolution matrix (the Grover matrix) of the Grover walk on a graph $G$, and present a formula for the characteristic polynomial of the transition probability matrix of this CRW by using a determinant expression for the generalized weighted zeta function of $G$. As applications, we give the spectrum of the transition probability matrices for the CRWs induced from the Grover matrices of regular graphs and semiregular bipartite graphs. Furthermore, we consider another type of the CRW on a graph.
Let $X, Y$ be two independent identically distributed (i.i.d.) random variables taking values from a separable Banach space $(mathcal{X}, |cdot|)$. Given two measurable subsets $F, Ksubseteqcal{X}$, we established distribution free comparison inequalities between $mathbb{P}(Xpm Y in F)$ and $mathbb{P}(X-Yin K)$. These estimates are optimal for real random variables as well as when $mathcal{X}=mathbb{R}^d$ is equipped with the $|cdot|_infty$ norm. Our approach for both problems extends techniques developed by Schultze and Weizsacher (2007).
We work under the A{i}d{e}kon-Chen conditions which ensure that the derivative martingale in a supercritical branching random walk on the line converges almost surely to a nondegenerate nonnegative random variable that we denote by $Z$. It is shown that $mathbb{E} Zmathbf{1}_{{Zle x}}=log x+o(log x)$ as $xtoinfty$. Also, we provide necessary and sufficient conditions under which $mathbb{E} Zmathbf{1}_{{Zle x}}=log x+{rm const}+o(1)$ as $xtoinfty$. This more precise asymptotics is a key tool for proving distributional limit theorems which quantify the rate of convergence of the derivative martingale to its limit $Z$. The methodological novelty of the present paper is a three terms representation of a subharmonic function of at most linear growth for a killed centered random walk of finite variance. This yields the aforementioned asymptotics and should also be applicable to other models.
We prove infinite-dimensional second order Poincare inequalities on Wiener space, thus closing a circle of ideas linking limit theorems for functionals of Gaussian fields, Steins method and Malliavin calculus. We provide two applications: (i) to a new second order characterization of CLTs on a fixed Wiener chaos, and (ii) to linear functionals of Gaussian-subordinated fields.
We study the trajectory of a simple random walk on a d-regular graph with d>2 and locally tree-like structure as the number n of vertices grows. Examples of such graphs include random d-regular graphs and large girth expanders. For these graphs, we investigate percolative properties of the set of vertices not visited by the walk until time un, where u>0 is a fixed positive parameter. We show that this so-called vacant set exhibits a phase transition in u in the following sense: there exists an explicitly computable threshold u* such that, with high probability as n grows, if u<u*, then the largest component of the vacant set has a volume of order n, and if u>u*, then it has a volume of order log(n). The critical value u* coincides with the critical intensity of a random interlacement process (introduced by Sznitman [arXiv:0704.2560]) on a d-regular tree. We also show that the random interlacement model describes the structure of the vacant set in local neighbourhoods.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
