Harnack inequalities on weighted graphs and some applications to the random conductance model

We establish elliptic and parabolic Harnack inequalities on graphs with unbounded weights. As an application we prove a local limit theorem for a continuous time random walk \(X\) in an environment of ergodic random conductances taking values in \((0, \infty )\) satisfying some moment conditions.     

Convergence of Martingale and Moderate Deviations for a Branching Random Walk with a Random Environment in Time

We consider a branching random walk on \({\mathbb {R}}\) with a stationary and ergodic environment \(\xi =(\xi _n)\) indexed by time \(n\in {\mathbb {N}}\). Let \(Z_n\) be the counting measure of particles of generation n and \(\tilde{Z}_n(t)=\int \mathrm{e}^{tx}Z_n(\mathrm{d}x)\) be its Laplace transform. We show the \(L^p\) convergence rate and the uniform convergence of the martingale \(\tilde{Z}_n(t)/{\mathbb {E}}[\tilde{Z}_n(t)|\xi ]\), and establish a moderate deviation principle for the measures \(Z_n\).     

Excited Random Walks with Non-nearest Neighbor Steps

Let W be an integer-valued random variable satisfying \(E[W] =: \delta \ge 0\) and \(P(W<0)>0\), and consider a self-interacting random walk that behaves like a simple symmetric random walk with the exception that on the first visit to any integer \(x\in \mathbb Z\), the size of the next step is an independent random variable with the same distribution as W. We show that this self-interacting random walk is recurrent if \(\delta \le 1\) and transient if \(\delta >1\). This is a special case of our main result which concerns the recurrence and transience of excited random walks (or cookie random walks) with non-nearest neighbor jumps.     

Existence of self-Cheeger sets on Riemannian manifolds

Let \(({\mathcal M},g)\) be a smooth compact Riemannian manifold of dimension \(N\ge 2\). We prove the existence of a family \((\Omega _\varepsilon )_{\varepsilon \in (0,\varepsilon _0)}\) of self-Cheeger sets in \(({\mathcal M},g)\). The domains \(\Omega _\varepsilon \subset {\mathcal M}\) are perturbations of geodesic balls of radius \(\varepsilon \) centered at \(p \in {\mathcal M}\), and in particular, if \(p_0\) is a non-degenerate critical point of the scalar curvature of g, then the family \((\partial \Omega _\varepsilon )_{\varepsilon \in (0,\varepsilon _0)}\) constitutes a smooth foliation of a neighborhood of \(p_0\).     

Fluctuation Theory for Markov Random Walks

Two fundamental theorems by Spitzer–Erickson and Kesten–Maller on the fluctuation-type (positive divergence, negative divergence or oscillation) of a real-valued random walk \((S_{n})_{n\ge 0}\) with iid increments \(X_{1},X_{2},\ldots \) and the existence of moments of various related quantities like the first passage into \((x,\infty )\) and the last exit time from \((-\infty ,x]\) for arbitrary \(x\ge 0\) are studied in the Markov-modulated situation when the \(X_{n}\) are governed by a positive recurrent Markov chain \(M=(M_{n})_{n\ge 0}\) on a countable state space \(\mathcal {S}\); thus, for a Markov random walk \((M_{n},S_{n})_{n\ge 0}\). Our approach is based on the natural strategy to draw on the results in the iid case for the embedded ordinary random walks \((S_{\tau _{n}(i)})_{n\ge 0}\), where \(\tau _{1}(i),\tau _{2}(i),\ldots \) denote the successive return times of M to state i, and an analysis of the excursions of the walk between these epochs. However, due to these excursions, generalizations of the aforementioned theorems are surprisingly more complicated and require the introduction of various excursion measures so as to characterize the existence of moments of different quantities.     

CLT for Random Walks of Commuting Endomorphisms on Compact Abelian Groups

Let \(\mathcal S\) be an abelian group of automorphisms of a probability space \((X, {\mathcal A}, \mu )\) with a finite system of generators \((A_1, \ldots , A_d).\) Let \(A^{{\underline{\ell }}}\) denote \(A_1^{\ell _1} \ldots A_d^{\ell _d}\), for \({{\underline{\ell }}}= (\ell _1, \ldots , \ell _d).\) If \((Z_k)\) is a random walk on \({\mathbb {Z}}^d\), one can study the asymptotic distribution of the sums \(\sum _{k=0}^{n-1} \, f \circ A^{\,{Z_k(\omega )}}\) and \(\sum _{{\underline{\ell }}\in {\mathbb {Z}}^d} {\mathbb {P}}(Z_n= {\underline{\ell }}) \, A^{\underline{\ell }}f\), for a function f on X. In particular, given a random walk on commuting matrices in \(SL(\rho , {\mathbb {Z}})\) or in \({\mathcal M}^*(\rho , {\mathbb {Z}})\) acting on the torus \({\mathbb {T}}^\rho \), \(\rho \ge 1\), what is the asymptotic distribution of the associated ergodic sums along the random walk for a smooth function on \({\mathbb {T}}^\rho \) after normalization? In this paper, we prove a central limit theorem when X is a compact abelian connected group G endowed with its Haar measure (e.g., a torus or a connected extension of a torus), \(\mathcal S\) a totally ergodic d-dimensional group of commuting algebraic automorphisms of G and f a regular function on G. The proof is based on the cumulant method and on preliminary results on random walks.     

Transience and Recurrence of Random Walks on Percolation Clusters in an Ultrametric Space

We study transience and recurrence of simple random walks on percolation clusters in the hierarchical group of order N, which is an ultrametric space. The connection probability on the hierarchical group for two points separated by distance k is of the form \(c_k/N^{k(1+\delta )}, \delta >0\), with \(c_k=C_0+C_1\log k+C_2k^\alpha \), non-negative constants \(C_0, C_1, C_2\), and \(\alpha >0\). Percolation occurs for \(\delta <1\), and for the critical case, \(\delta =1\), \(\alpha >0\) and sufficiently large \(C_2\). We show that in the case \(\delta <1\) the walk is transient, and in the case \(\delta =1,C_2>0,\alpha >0\) there exists a critical \(\alpha _\mathrm{c}\in (0,\infty )\) such that the walk is recurrent for \(\alpha <\alpha _\mathrm{c}\) and transient for \(\alpha >\alpha _\mathrm{c}\). The proofs involve ultrametric random graphs, graph diameters, path lengths, and electric circuit theory. Some comparisons are made with behaviours of simple random walks on long-range percolation clusters in the one-dimensional Euclidean lattice.     

Heavy-Tailed Random Walks on Complexes of Half-Lines

We study a random walk on a complex of finitely many half-lines joined at a common origin; jumps are heavy-tailed and of two types, either one-sided (towards the origin) or two-sided (symmetric). Transmission between half-lines via the origin is governed by an irreducible Markov transition matrix, with associated stationary distribution \(\mu _k\). If \(\chi _k\) is 1 for one-sided half-lines k and 1 / 2 for two-sided half-lines, and \(\alpha _k\) is the tail exponent of the jumps on half-line k, we show that the recurrence classification for the case where all \(\alpha _k \chi _k \in (0,1)\) is determined by the sign of \(\sum _k \mu _k \cot ( \chi _k \pi \alpha _k )\). In the case of two half-lines, the model fits naturally on \({{\mathbb {R}}}\) and is a version of the oscillating random walk of Kemperman. In that case, the cotangent criterion for recurrence becomes linear in \(\alpha _1\) and \(\alpha _2\); our general setting exhibits the essential nonlinearity in the cotangent criterion. For the general model, we also show existence and non-existence of polynomial moments of return times. Our moments results are sharp (and new) for several cases of the oscillating random walk; they are apparently even new for the case of a homogeneous random walk on \({{\mathbb {R}}}\) with symmetric increments of tail exponent \(\alpha \in (1,2)\).     

Convergence and Precise Asymptotics for Series Involving Self-normalized Sums

Let \(X, X_{1}, X_{2}, \ldots \) be i.i.d. random variables, and set \(S_{n}=X_{1}+\cdots +X_{n}\) and \( V_{n}^{2}=X_{1}^{2}+\cdots +X_{n}^{2}.\) Without any moment conditions on \(X\), assuming that \(\{S_{n}/V_{n}\}\) is tight, we establish convergence of series of the type (*) \(\sum \nolimits _{n}w_{n}P(\left| S_{n}\right| /V_{n}\ge \varepsilon b_{n}),\) \(\varepsilon >0.\) Then, assuming that \(X\) is symmetric and belongs to the domain of attraction of a stable law, and choosing \(w_{n}\) and \(b_{n}\) suitably\(,\) we derive the precise asymptotic behavior of the series (*) as \(\varepsilon \searrow 0. \)     

Random walks with different directions

As an extension of Polya’s classical result on random walks on the square grids (\({\mathbf {Z}}^d\)), we consider a random walk where the steps, while still have unit length, point to different directions. We show that in dimensions at least 4, the returning probability after n steps is at most \(n^{-d/2 - d/(d-2) +o(1) }\), which is sharp. The real surprise is in dimensions 2 and 3. In dimension 2, where the traditional grid walk is recurrent, our upper bound is \(n^{-\omega (1) }\), which is much worse than in higher dimensions. In dimension 3, we prove an upper bound of order \(n^{-4 +o(1) }\). We find a new conjecture concerning incidences between spheres and points in \({\mathbf {R}}^3\), which, if holds, would improve the bound to \(n^{-9/2 +o(1) }\), which is consistent to the \(d \ge 4\) case. This conjecture resembles Szemerédi-Trotter type results and is of independent interest.     

The Sobolev Stability Threshold for 2D Shear Flows Near Couette

We consider the 2D Navier–Stokes equation on \(\mathbb T \times \mathbb R\), with initial datum that is \(\varepsilon \)-close in \(H^N\) to a shear flow (U(y), 0), where \(\Vert U(y) - y\Vert _{H^{N+4}} \ll 1\) and \(N>1\). We prove that if \(\varepsilon \ll \nu ^{1/2}\), where \(\nu \) denotes the inverse Reynolds number, then the solution of the Navier–Stokes equation remains \(\varepsilon \)-close in \(H^1\) to \((e^{t \nu \partial _{yy}}U(y),0)\) for all \(t>0\). Moreover, the solution converges to a decaying shear flow for times \(t \gg \nu ^{-1/3}\) by a mixing-enhanced dissipation effect, and experiences a transient growth of gradients. In particular, this shows that the stability threshold in finite regularity scales no worse than \(\nu ^{1/2}\) for 2D shear flows close to the Couette flow.     

Error Bounds for Consistent Reconstruction: Random Polytopes and Coverage Processes

Consistent reconstruction is a method for producing an estimate \(\widetilde{x} \in {\mathbb {R}}^d\) of a signal \(x\in {\mathbb {R}}^d\) if one is given a collection of \(N\) noisy linear measurements \(q_n = \langle x, \varphi _n \rangle + \epsilon _n\), \(1 \le n \le N\), that have been corrupted by i.i.d. uniform noise \(\{\epsilon _n\}_{n=1}^N\). We prove mean-squared error bounds for consistent reconstruction when the measurement vectors \(\{\varphi _n\}_{n=1}^N\subset {\mathbb {R}}^d\) are drawn independently at random from a suitable distribution on the unit-sphere \({\mathbb {S}}^{d-1}\). Our main results prove that the mean-squared error (MSE) for consistent reconstruction is of the optimal order \({\mathbb {E}}\Vert x - \widetilde{x}\Vert ^2 \le K\delta ^2/N^2\) under general conditions on the measurement vectors. We also prove refined MSE bounds when the measurement vectors are i.i.d. uniformly distributed on the unit-sphere \({\mathbb {S}}^{d-1}\) and, in particular, show that in this case, the constant \(K\) is dominated by \(d^3\), the cube of the ambient dimension. The proofs involve an analysis of random polytopes using coverage processes on the sphere.     

Hankel Determinants of Random Moment Sequences

For \(t \in [0,1]\) let \(\underline{H}_{2\lfloor nt \rfloor } = (m_{i+j})_{i,j=0}^{\lfloor nt \rfloor }\) denote the Hankel matrix of order \(2\lfloor nt \rfloor \) of a random vector \((m_1,\ldots ,m_{2n})\) on the moment space \(\mathcal {M}_{2n}(I)\) of all moments (up to the order 2n) of probability measures on the interval \(I \subset \mathbb {R}\). In this paper we study the asymptotic properties of the stochastic process \(\{ \log \det \underline{H}_{2\lfloor nt \rfloor } \}_{t\in [0,1]}\) as \(n \rightarrow \infty \). In particular weak convergence and corresponding large deviation principles are derived after appropriate standardization.     

Banach Random Walk in the Unit Ball $$S\subset l^{2}$$ and Chaotic Decomposition of $$l^{2}\left( S,{{\mathbb {P}}}\right) $$l2S,P

A Banach random walk in the unit ball S in \(l^{2}\) is defined, and we show that the integral introduced by Banach (Theory of the integral. Warszawa-Lwów, 1937) can be expressed as the expectation with respect to the measure \({{\mathbb {P}}}\) induced by this walk. A decomposition \(l^{2}\left( S,{{\mathbb {P}}}\right) =\bigoplus _{i=0}^{\infty } {{\mathfrak {B}}}_{i}\) in terms of what we call Banach chaoses is given.     

On the L1-convergence and behavior of coefficients of Fourier–Vilenkin series

In this paper, we prove the following statement that is true for both bounded and some type of unbounded Vilenkin systems: for any \( \varepsilon \in (0,1)\), there exists a measurable set \(E\subset [0,1)\) of measure bigger than \(1-\varepsilon \) such that for any function \(f \in L^{1}[0,1)\), it is possible to find a function \(g\in L^{1}[0,1)\) coinciding with f on E, Fourier series of g with respect to Vilenkin system are convergent in \(L^{1}\)-norm and the absolute values of non zero Fourier coefficients of g are monotonically decreasing.     

Two-step estimation of ergodic Lévy driven SDE

We consider high frequency samples from ergodic Lévy driven stochastic differential equation with drift coefficient \(a(x,\alpha )\) and scale coefficient \(c(x,\gamma )\) involving unknown parameters \(\alpha \) and \(\gamma \). We suppose that the Lévy measure \(\nu _{0}\), has all order moments but is not fully specified. We will prove the joint asymptotic normality of some estimators of \(\alpha \), \(\gamma \) and a class of functional parameter \(\int \varphi (z)\nu _0(dz)\), which are constructed in a two-step manner: first, we use the Gaussian quasi-likelihood for estimation of \((\alpha ,\gamma )\); and then, for estimating \(\int \varphi (z)\nu _0(dz)\) we make use of the method of moments based on the Euler-type residual with the the previously obtained quasi-likelihood estimator.     

Uniform Bounds on the Relative Error in the Approximation of Upper Quantiles for Sums of Arbitrary Independent Random Variables

Fix any \(n\ge 1\). Let \(\tilde{X}_1,\ldots ,\tilde{X}_n\) be independent random variables. For each \(1\le j \le n\), \(\tilde{X}_j\) is transformed in a canonical manner into a random variable \(X_j\). The \(X_j\) inherit independence from the \(\tilde{X}_j\). Let \(s_y\) and \(s_y^*\) denote the upper \(\frac{1}{y}{\underline{\text{ th }}}\) quantile of \(S_n=\sum _{j=1}^nX_j\) and \(S^*_n=\sup _{1\le k\le n}S_k\), respectively. We construct a computable quantity \(\underline{Q}_y\) based on the marginal distributions of \(X_1,\ldots ,X_n\) to produce upper and lower bounds for \(s_y\) and \(s_y^*\). We prove that for \(y\ge 8\)

$$\begin{aligned} 6^{-1} \gamma _{3y/16}\underline{Q}_{3y/16}\le s^*_{y}\le \underline{Q}_y \end{aligned}$$

where

$$\begin{aligned} \gamma _y=\frac{1}{2w_y+1} \end{aligned}$$

and \(w_y\) is the unique solution of

$$\begin{aligned} \Big (\frac{w_y}{e\ln (\frac{y}{y-2})}\Big )^{w_y}=2y-4 \end{aligned}$$

for \(w_y>\ln (\frac{y}{y-2})\), and for \(y\ge 37\)

$$\begin{aligned} \frac{1}{9}\gamma _{u(y)}\underline{Q}_{u(y)}<s_y \le \underline{Q}_y \end{aligned}$$

where

$$\begin{aligned} u(y)=\frac{3y}{32} \left( 1+\sqrt{1-\frac{64}{3y}}\right) . \end{aligned}$$

The distribution of \(S_n\) is approximately centered around zero in that \(P(S_n\ge 0) \ge \frac{1}{18}\) and \(P(S_n\le 0)\ge \frac{1}{65}\). The results extend to \(n=\infty \) if and only if for some (hence all) \(a>0\)

$$\begin{aligned} \sum _{j=1}^{\infty }E\{(\tilde{X}_j-m_j)^2\wedge a^2\}<\infty . \end{aligned}$$

(1)

     

The Difference Between a Discrete and Continuous Harmonic Measure

We consider a discrete-time, continuous-state random walk with steps uniformly distributed in a disk of radius h. For a simply connected domain D in the plane, let \(\omega _h(0,\cdot ;D)\) be the discrete harmonic measure at \(0\in D\) associated with this random walk, and \(\omega (0,\cdot ;D)\) be the (continuous) harmonic measure at 0. For domains D with analytic boundary, we prove there is a bounded continuous function \(\sigma _D(z)\) on \(\partial D\) such that for functions g which are in \(C^{2+\alpha }(\partial D)\) for some \(\alpha >0\) we have

$$\begin{aligned} \lim _{h\downarrow 0} \frac{\int _{\partial D} g(\xi ) \omega _h(0,|\mathrm{d}\xi |;D) -\int _{\partial D} g(\xi )\omega (0,|\mathrm{d}\xi |;D)}{h} = \int _{\partial D}g(z) \sigma _D(z) |\mathrm{d}z|. \end{aligned}$$

We give an explicit formula for \(\sigma _D\) in terms of the conformal map from D to the unit disk. The proof relies on some fine approximations of the potential kernel and Green’s function of the random walk by their continuous counterparts, which may be of independent interest.

     

Extremal eigenvalues and eigenvectors of deformed Wigner matrices

We consider random matrices of the form \(H = W + \lambda V, \lambda \in {\mathbb {R}}^+\), where \(W\) is a real symmetric or complex Hermitian Wigner matrix of size \(N\) and \(V\) is a real bounded diagonal random matrix of size \(N\) with i.i.d. entries that are independent of \(W\). We assume subexponential decay of the distribution of the matrix entries of \(W\) and we choose \(\lambda \sim 1\), so that the eigenvalues of \(W\) and \(\lambda V\) are typically of the same order. Further, we assume that the density of the entries of \(V\) is supported on a single interval and is convex near the edges of its support. In this paper we prove that there is \(\lambda _+\in {\mathbb {R}}^+\) such that the largest eigenvalues of \(H\) are in the limit of large \(N\) determined by the order statistics of \(V\) for \(\lambda >\lambda _+\). In particular, the largest eigenvalue of \(H\) has a Weibull distribution in the limit \(N\rightarrow \infty \) if \(\lambda >\lambda _+\). Moreover, for \(N\) sufficiently large, we show that the eigenvectors associated to the largest eigenvalues are partially localized for \(\lambda >\lambda _+\), while they are completely delocalized for \(\lambda <\lambda _+\). Similar results hold for the lowest eigenvalues.     

Zeta functions and asymptotic additive bases with some unusual sets of primes

Fix \(\delta \in (0,1]\), \(\sigma _0\in [0,1)\) and a real-valued function \(\varepsilon (x)\) for which \(\varlimsup _{x\rightarrow \infty }\varepsilon (x)\leqslant 0\). For every set of primes \(\mathcal {P}\) whose counting function \(\pi _\mathcal {P}(x)\) satisfies an estimate of the form

$$\begin{aligned} \pi _\mathcal {P}(x)=\delta \,\pi (x)+O\bigl (x^{\sigma _0+\varepsilon (x)}\bigr ), \end{aligned}$$

we define a zeta function \(\zeta _\mathcal {P}(s)\) that is closely related to the Riemann zeta function \(\zeta (s)\). For \(\sigma _0\leqslant \frac{1}{2}\), we show that the Riemann hypothesis is equivalent to the non-vanishing of \(\zeta _\mathcal {P}(s)\) in the region \(\{\sigma >\frac{1}{2}\}\).

For every set of primes \(\mathcal {P}\) that contains the prime 2 and whose counting function satisfies an estimate of the form

$$\begin{aligned} \pi _\mathcal {P}(x)=\delta \,\pi (x)+O\bigl ((\log \log x)^{\varepsilon (x)}\bigr ), \end{aligned}$$

we show that \(\mathcal {P}\) is an exact asymptotic additive basis for \(\mathbb {N}\), i.e. for some integer \(h=h(\mathcal {P})>0\) the sumset \(h\mathcal {P}\) contains all but finitely many natural numbers. For example, an exact asymptotic additive basis for \(\mathbb {N}\) is provided by the set

$$\begin{aligned} \{2,547,1229,1993,2749,3581,4421,5281\ldots \}, \end{aligned}$$

which consists of 2 and every hundredth prime thereafter.