BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Ofer Zeitouni

Ofer Zeitouni appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.PRData Structures and Algorithmsmath-phmath.COmath.MPcond-mat.stat-mechCryptography and Securitymath.SPmath.STStatistics Theorycond-mat.dis-nnDiscrete MathematicsInformation TheoryMachine Learningmath.APmath.CVmath.ITmath.MGmath.OAmath.OCquant-ph

Catalog footprint

What is connected

56works
21topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

56 published item(s)

preprint2022arXiv

Lower Bounds on the Generalization Error of Nonlinear Learning Models

We study in this paper lower bounds for the generalization error of models derived from multi-layer neural networks, in the regime where the size of the layers is commensurate with the number of samples in the training data. We show that unbiased estimators have unacceptable performance for such nonlinear networks in this regime. We derive explicit generalization lower bounds for general biased estimators, in the cases of linear regression and of two-layered networks. In the linear case the bound is asymptotically tight. In the nonlinear case, we provide a comparison of our bounds with an empirical study of the stochastic gradient descent algorithm. The analysis uses elements from the theory of large random matrices.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

On the limiting law of line ensembles of Brownian polymers with geometric area tilts

We study the line ensembles of non-crossing Brownian bridges above a hard wall, each tilted by the area of the region below it with geometrically growing pre-factors. This model, which mimics the level lines of the $(2+1)$D SOS model above a hard wall, was studied in two works from 2019 by Caputo, Ioffe and Wachtel. In those works, the tightness of the law of the top $k$ paths, for any fixed $k$, was established under either zero or free boundary conditions, which in the former setting implied the existence of a limit via a monotonicity argument. Here we address the open problem of a limit under free boundary conditions: we prove that as the interval length, followed by the number of paths, go to $\infty$, the top $k$ paths converge to the same limit as in the free boundary case, as conjectured by Caputo, Ioffe and Wachtel.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

The maximum of log-correlated Gaussian fields in random environments

We study the distribution of the maximum of a large class of Gaussian fields indexed by a box $V_N\subset Z^d$ and possessing logarithmic correlations up to local defects that are sufficiently rare. Under appropriate assumptions that generalize those in Ding, Roy and Zeitouni (Annals Probab. (45) 2017, 3886-3928), we show that asymptotically, the centered maximum of the field has a randomly-shifted Gumbel distribution. We prove that the two dimensional Gaussian free field on a super-critical bond percolation cluster with $p$ close enough to $1$, as well as the Gaussian free field in i.i.d. bounded conductances, fall under the assumptions of our general theorem.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Universality of Poisson limits for moduli of roots of Kac polynomials

We give a new proof of a recent resolution by Michelen and Sahasrabudhe of a conjecture of Shepp and Vanderbei that the moduli of roots of Gaussian Kac polynomials of degree $n$, centered at $1$ and rescaled by $n^2$, should form a Poisson point process. We use this new approach to verify a conjecture of Michelen and Sahasrabudhe that the Poisson statistics are in fact universal.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Everything is a Race and Nakamoto Always Wins

Nakamoto invented the longest chain protocol, and claimed its security by analyzing the private double-spend attack, a race between the adversary and the honest nodes to grow a longer chain. But is it the worst attack? We answer the question in the affirmative for three classes of longest chain protocols, designed for different consensus models: 1) Nakamoto's original Proof-of-Work protocol; 2) Ouroboros and SnowWhite Proof-of-Stake protocols; 3) Chia Proof-of-Space protocol. As a consequence, exact characterization of the maximum tolerable adversary power is obtained for each protocol as a function of the average block time normalized by the network delay. The security analysis of these protocols is performed in a unified manner by a novel method of reducing all attacks to a race between the adversary and the honest nodes.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Maximum of Branching Brownian motion in a periodic environment

We study the maximum of Branching Brownian motion (BBM) with branching rates that vary in space, via a periodic function of a particle's location. This corresponds to a variant of the F-KPP equation in a periodic medium, extensively studied in the last 15 years, admitting pulsating fronts as solutions. Recent progress on this PDE due to Hamel, Nolen, Roquejoffre and Ryzhik ('16) implies tightness for the centered maximum of BBM in a periodic environment. Here we establish the convergence in distribution of specific subsequences of this centered maximum, and identify the limiting distribution. Consequently, we find the asymptotic shift between the solution to the corresponding F-KPP equation with Heavyside initial data and the pulsating wave, thereby answering a question of Hamel et al. Analogous results are given for the cases where the Brownian motion is replaced by an Ito diffusion with periodic coefficients, as well as for nearest-neighbor branching random walks.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Outliers of random perturbations of Toeplitz matrices with finite symbols

Consider an $N\times N$ Toeplitz matrix $T_N$ with symbol ${a }(λ) := \sum_{\ell=-d_2}^{d_1} a_\ell λ^\ell$, perturbed by an additive noise matrix $N^{-γ} E_N$, where the entries of $E_N$ are centered i.i.d.~random variables of unit variance and $γ>1/2$. It is known that the empirical measure of eigenvalues of the perturbed matrix converges weakly, as $N\to\infty$, to the law of ${a}(U)$, where $U$ is distributed uniformly on $\mathbb{S}^1$. In this paper, we consider the outliers, i.e. eigenvalues that are at a positive ($N$-independent) distance from ${a}(\mathbb{S}^1)$. We prove that there are no outliers outside ${\rm spec} \, T({a})$, the spectrum of the limiting Toeplitz operator, with probability approaching one, as $N \to \infty$. {In contrast,} in ${\rm spec}\, T({a})\setminus {a}({\mathbb S}^1)$ the process of outliers converges to the point process described by the zero set of certain random {analytic} functions. The limiting random {analytic} functions can be expressed as linear combinations of the determinants of finite sub-matrices of an infinite dimensional matrix, whose entries are i.i.d.~having the same law as that of $E_N$. The coefficients in the linear combination depend on the roots of the polynomial $P_{z, {a}}(λ):= ({a}(λ) -z)λ^{d_2}=0$ and semi-standard Young Tableaux with shapes determined by the number of roots of $P_{z,{a}}(λ)=0$ that are greater than one in moduli.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Proof-of-Stake Longest Chain Protocols: Security vs Predictability

The Nakamoto longest chain protocol is remarkably simple and has been proven to provide security against any adversary with less than 50% of the total hashing power. Proof-of-stake (PoS) protocols are an energy efficient alternative; however existing protocols adopting Nakamoto's longest chain design achieve provable security only by allowing long-term predictability (which have serious security implications). In this paper, we prove that a natural longest chain PoS protocol with similar predictability as Nakamoto's PoW protocol can achieve security against any adversary with less than 1/(1+e) fraction of the total stake. Moreover we propose a new family of longest chain PoS protocols that achieve security against a 50% adversary, while only requiring short-term predictability. Our proofs present a new approach to analyzing the formal security of blockchains, based on a notion of adversary-proof convergence.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Universality for Langevin-like spin glass dynamics

We study dynamics for asymmetric spin glass models, proposed by Hertz et al. and Sompolinsky et al. in the 1980's in the context of neural networks: particles evolve via a modified Langevin dynamics for the Sherrington--Kirkpatrick model with soft spins, whereby the disorder is i.i.d. standard Gaussian rather than symmetric. Ben Arous and Guionnet (1995), followed by Guionnet (1997), proved for Gaussian interactions that as the number of particles grows, the short-term empirical law of this dynamics converges a.s. to a non-random law $μ_\star$ of a ``self-consistent single spin dynamics,'' as predicted by physicists. Here we obtain universality of this fact: For asymmetric disorder given by i.i.d. variables of zero mean, unit variance and exponential or better tail decay, at every temperature, the empirical law of sample paths of the Langevin-like dynamics in a fixed time interval has the same a.s. limit $μ_\star$.

0 citations0 reviewsNo code linkedOpen access
preprint2017arXiv

Homogenization of a class of one-dimensional nonconvex viscous Hamilton-Jacobi equations with random potential

We prove the homogenization of a class of one-dimensional viscous Hamilton-Jacobi equations with random Hamiltonians that are nonconvex in the gradient variable. Due to the special form of the Hamiltonians, the solutions of these PDEs with linear initial conditions have representations involving exponential expectations of controlled Brownian motion in a random potential. The effective Hamiltonian is the asymptotic rate of growth of these exponential expectations as time goes to infinity and is explicit in terms of the tilted free energy of (uncontrolled) Brownian motion in a random potential. The proof involves large deviations, construction of correctors which lead to exponential martingales, and identification of asymptotically optimal policies.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Convergence in law of the maximum of nonlattice branching random walk

Let $η^*_n$ denote the maximum, at time $n$, of a nonlattice one-dimensional branching random walk $η_n$ possessing (enough) exponential moments. In a seminal paper, Aidekon demonstrated convergence of $η^*_n$ in law, after recentering, and gave a representation of the limit. We give here a shorter proof of this convergence by employing reasoning motivated by Bramson, Ding and Zeitouni. Instead of spine methods and a careful analysis of the renewal measure for killed random walks, our approach employs a modified version of the second moment method that may be of independent interest.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Hafnians, perfect matchings and Gaussian matrices

We analyze the behavior of the Barvinok estimator of the hafnian of even dimension, symmetric matrices with nonnegative entries. We introduce a condition under which the Barvinok estimator achieves subexponential errors, and show that this condition is almost optimal. Using that hafnians count the number of perfect matchings in graphs, we conclude that Barvinok's estimator gives a polynomial-time algorithm for the approximate (up to subexponential errors) evaluation of the number of perfect matchings.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Local asymptotics for controlled martingales

We consider controlled martingales with bounded steps where the controller is allowed at each step to choose the distribution of the next step, and where the goal is to hit a fixed ball at the origin at time $n$. We show that the algebraic rate of decay (as $n$ increases to infinity) of the value function in the discrete setup coincides with its continuous counterpart, provided a reachability assumption is satisfied. We also study in some detail the uniformly elliptic case and obtain explicit bounds on the rate of decay. This generalizes and improves upon several recent studies of the one dimensional case, and is a discrete analogue of a stochastic control problem recently investigated in Armstrong and Trokhimtchouck [Calc. Var. Partial Differential Equations 38 (2010) 521-540].

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The extremal process of critical points of the pure $p$-spin spherical spin glass model

Recently, sharp results concerning the critical points of the Hamiltonian of the $p$-spin spherical spin glass model have been obtained by means of moments computations. In particular, these moments computations allow for the evaluation of the leading term of the ground-state, i.e., of the global minimum. In this paper, we study the extremal point process of critical points - that is, the point process associated to all critical values in the vicinity of the ground-state. We show that the latter converges in distribution to a Poisson point process of exponential intensity. In particular, we identify the correct centering of the ground-state and prove the convergence in distribution of the centered minimum to a (minus) Gumbel variable. These results are identical to what one obtains for a sequence of i.i.d variables, correctly normalized; namely, we show that the model is in the universality class of REM.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Weak and Strong disorder for the stochastic heat equation and the continuous directed polymer in $d\geq 3$

We consider the smoothed multiplicative noise stochastic heat equation $$d u_{\eps,t}= \frac 12 Δu_{\eps,t} d t+ β\eps^{\frac{d-2}{2}}\, \, u_{\eps, t} \, d B_{\eps,t} , \;\;u_{\eps,0}=1,$$ in dimension $d\geq 3$, where $B_{\eps,t}$ is a spatially smoothed (at scale $\eps$) space-time white noise, and $β>0$ is a parameter. We show the existence of a $\barβ\in (0,\infty)$ so that the solution exhibits weak disorder when $β<\barβ$ and strong disorder when $β> \barβ$. The proof techniques use elements of the theory of the Gaussian multiplicative chaos.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Extremal eigenvalue fluctuations in the GUE minor process and the law of fractional logarithm

We consider the GUE minor process, where a sequence of GUE matrices is drawn from the corner of a doubly infinite array of i.i.d. standard normal variables subject to the symmetry constraint. From each matrix, we take its largest eigenvalue, appropriately rescaled to converge to the standard Tracy-Widom distribution. We show the analogue of the law of iterated logarithm for this sequence, i.e. we divide the normalized n-th eigenvalue by a logarithmic factor and show the limsup of this sequence is a constant almost surely. We also give almost sure bounds for the appropriately scaled liminf.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Large deviations for the two-dimensional two-component plasma

We derive a large deviations principle for the two-dimensional two-component plasma in a box. As a consequence, we obtain a variational representation for the free energy, and also show that the macroscopic empirical measure of either positive or negative charges converges to the uniform measure. An appendix, written by Wei Wu, discusses applications to the supercritical complex Gaussian multiplicative chaos.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Freezing and decorated Poisson point processes

The limiting extremal processes of the branching Brownian motion (BBM), the two-speed BBM, and the branching random walk are known to be randomly shifted decorated Poisson point processes (SDPPP). In the proofs of those results, the Laplace functional of the limiting extremal process is shown to satisfy $L[θ_y f]=g(y-τ_f)$ for any nonzero, nonnegative, compactly supported, continuous function $f$, where $θ_y$ is the shift operator, $τ_f$ is a real number that depends on $f$, and $g$ is a real function that is independent of $f$. We show that, under some assumptions, this property characterizes the structure of SDPPP. Moreover, when it holds, we show that $g$ has to be a convolution of the Gumbel distribution with some measure. The above property of the Laplace functional is closely related to a `freezing phenomenon' that is expected by physicists to occur in a wide class of log-correlated fields, and which has played an important role in the analysis of various models. Our results shed light on this intriguing phenomenon and provide a natural tool for proving an SDPPP structure in these and other models.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Matrix optimization under random external fields

We consider the quadratic optimization problem $$F_n^{W,h}:= \sup_{x \in S^{n-1}} ( x^T W x/2 + h^T x )\,, $$ with $W$ a (random) matrix and $h$ a random external field. We study the probabilities of large deviation of $F_n^{W,h}$ for $h$ a centered Gaussian vector with i.i.d. entries, both conditioned on $W$ (a general Wigner matrix), and unconditioned when $W$ is a GOE matrix. Our results validate (in a certain region) and correct (in another region), the prediction obtained by the mathematically non-rigorous replica method in Y. V. Fyodorov, P. Le Doussal, J. Stat. phys. 154 (2014).

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

On the limitation of spectral methods: From the Gaussian hidden clique problem to rank one perturbations of Gaussian tensors

We consider the following detection problem: given a realization of a symmetric matrix ${\mathbf{X}}$ of dimension $n$, distinguish between the hypothesis that all upper triangular variables are i.i.d. Gaussians variables with mean 0 and variance $1$ and the hypothesis where ${\mathbf{X}}$ is the sum of such matrix and an independent rank-one perturbation. This setup applies to the situation where under the alternative, there is a planted principal submatrix ${\mathbf{B}}$ of size $L$ for which all upper triangular variables are i.i.d. Gaussians with mean $1$ and variance $1$, whereas all other upper triangular elements of ${\mathbf{X}}$ not in ${\mathbf{B}}$ are i.i.d. Gaussians variables with mean 0 and variance $1$. We refer to this as the `Gaussian hidden clique problem.' When $L=(1+ε)\sqrt{n}$ ($ε>0$), it is possible to solve this detection problem with probability $1-o_n(1)$ by computing the spectrum of ${\mathbf{X}}$ and considering the largest eigenvalue of ${\mathbf{X}}$. We prove that this condition is tight in the following sense: when $L<(1-ε)\sqrt{n}$ no algorithm that examines only the eigenvalues of ${\mathbf{X}}$ can detect the existence of a hidden Gaussian clique, with error probability vanishing as $n\to\infty$. We prove this result as an immediate consequence of a more general result on rank-one perturbations of $k$-dimensional Gaussian tensors. In this context we establish a lower bound on the critical signal-to-noise ratio below which a rank-one signal cannot be detected.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Performance of the Metropolis algorithm on a disordered tree: The Einstein relation

Consider a $d$-ary rooted tree ($d\geq3$) where each edge $e$ is assigned an i.i.d. (bounded) random variable $X(e)$ of negative mean. Assign to each vertex $v$ the sum $S(v)$ of $X(e)$ over all edges connecting $v$ to the root, and assume that the maximum $S_n^*$ of $S(v)$ over all vertices $v$ at distance $n$ from the root tends to infinity (necessarily, linearly) as $n$ tends to infinity. We analyze the Metropolis algorithm on the tree and show that under these assumptions there always exists a temperature $1/β$ of the algorithm so that it achieves a linear (positive) growth rate in linear time. This confirms a conjecture of Aldous [Algorithmica 22 (1998) 388-412]. The proof is obtained by establishing an Einstein relation for the Metropolis algorithm on the tree.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Regularization of non-normal matrices by Gaussian noise

We consider the regularization of matrices $M^N$ written in Jordan form by additive Gaussian noise $N^{-γ}G^N$, where $G^N$ is a matrix of i.i.d. standard Gaussians and $γ>1/2$ so that the operator norm of the additive noise tends to $0$ with $N$. Under mild conditions on the structure of $M^N$ we evaluate the limit of the empirical measure of eigenvalues of $M^N+N^{-γ} G^N$ and show that it depends on $γ$, in contrast with the case of a single Jordan block.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Singular values of Gaussian matrices and permanent estimators

We present estimates on the small singular values of a class of matrices with independent Gaussian entries and inhomogeneous variance profile, satisfying a broad-connectedness condition. Using these estimates and concentration of measure for the spectrum of Gaussian matrices with independent entries, we prove that for a large class of graphs satisfying an appropriate expansion property, the Barvinok--Godsil-Gutman estimator for the permanent achieves sub-exponential errors with high probability.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Extreme values for two-dimensional discrete Gaussian free field

We consider in this paper the collection of near maxima of the discrete, two dimensional Gaussian free field in a box with Dirichlet boundary conditions. We provide a rough description of the geometry of the set of near maxima, estimates on the gap between the two largest maxima, and an estimate for the right tail up to a multiplicative constant on the law of the centered maximum.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Fluctuations of recentered maxima of discrete Gaussian Free Fields on a class of recurrent graphs

We provide conditions that ensure that the recentered maximum of the Gaussian free field on a sequence of graphs fluctuates at the same order as the field at the point of maximal variance. In particular, on a sequence of such graphs the recentered maximum is not tight, similarly to the situation in Z but in contrast with the situation in Z^2. We show that our conditions cover a large class of "fractal" graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Localization for controlled random walks and martingales

We consider controlled random walks that are martingales with uniformly bounded increments and nontrivial jump probabilities and show that such walks can be constructed so that P(S_n^u=0) decays at polynomial rate n^{-α} where α>0 can be arbitrarily small. We also show, by means of a general delocalization lemma for martingales, which is of independent interest, that slower than polynomial decay is not possible.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Maximal Arithmetic Progressions in Random Subsets

Let U(N) denote the maximal length of arithmetic progressions in a random uniform subset of {0,1}^N. By an application of the Chen-Stein method, we show that U(N)- 2 log(N)/log(2) converges in law to an extreme type (asymmetric) distribution. The same result holds for the maximal length W(N) of arithmetic progressions (mod N). When considered in the natural way on a common probability space, we observe that U(N)/log(N) converges almost surely to 2/log(2), while W(N)/log(N) does not converge almost surely (and in particular, limsup W(N)/log(N) is at least 3/log(2)).

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

A sharp estimate for cover times on binary trees

We compute the second order correction for the cover time of the binary tree of depth $n$ by (continuous-time) random walk, and show that with probability approaching 1 as $n$ increases, $\sqrt{τ_{\mathrm{cov}}}=\sqrt{|E|}[\sqrt{2\log 2}\cdot n - {\log n}/{\sqrt{2\log 2}} + O((\log\logn)^8]$, thus showing that the second order correction differs from the corresponding one for the maximum of the Gaussian free field on the tree.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Branching Random Walks in Time Inhomogeneous Environments

We study the maximal displacement of branching random walks in a class of time inhomogeneous environments. Specifically, binary branching random walks with Gaussian increments will be considered, where the variances of the increments change over time macroscopically. We find the asymptotics of the maximum up to an $O_P(1)$ (stochastically bounded) error, and focus on the following phenomena: the profile of the variance matters, both to the leading (velocity) term and to the logarithmic correction term, and the latter exhibits a phase transition.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Hard edge tail asymptotics

Let $Λ$ be the limiting smallest eigenvalue in the general (β, a)-Laguerre ensemble of random matrix theory. Here β>0, a >-1; for β=1,2,4 and integer a, this object governs the singular values of certain rank n Gaussian matrices. We prove that P(Λ> λ) = e^{- (β/2) λ+ 2 γλ^{1/2}} λ^{- (γ(γ+1))/(2β) + γ/4} E (β, a) (1+o(1)) as λgoes to infinity, in which γ= (β/2) (a+1)-1 and E(β, a) is a constant (which we do not determine). This estimate complements/extends various results previously available for special values of βand a.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Mixing times for random k-cycles and coalescence-fragmentation chains

Let $\mathcal{S}_n$ be the permutation group on $n$ elements, and consider a random walk on $\mathcal{S}_n$ whose step distribution is uniform on $k$-cycles. We prove a well-known conjecture that the mixing time of this process is $(1/k)n\log n$, with threshold of width linear in $n$. Our proofs are elementary and purely probabilistic, and do not appeal to the representation theory of $\mathcal{S}_n$.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Quenched invariance principle for random walks in balanced random environment

We consider random walks in a balanced random environment in $\mathbb{Z}^d$, $d\geq 2$. We first prove an invariance principle (for $d\ge2$) and the transience of the random walks when $d\ge 3$ (recurrence when $d=2$) in an ergodic environment which is not uniformly elliptic but satisfies certain moment condition. Then, using percolation arguments, we show that under mere ellipticity, the above results hold for random walks in i.i.d. balanced environments.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Quenched limits for transient, zero speed one-dimensional random walk in random environment

We consider a nearest-neighbor, one dimensional random walk $\{X_n\}_{n\geq0}$ in a random i.i.d. environment, in the regime where the walk is transient but with zero speed, so that $X_n$ is of order $n^s$ for some $s<1$. Under the quenched law (i.e., conditioned on the environment), we show that no limit laws are possible: There exist sequences $\{n_k\}$ and $\{x_k\}$ depending on the environment only, such that $X_{n_k}-x_k=o(\log n_k)^2$ (a localized regime). On the other hand, there exist sequences $\{t_m\}$ and $\{s_m\}$ depending on the environment only, such that $\log s_m/\log t_m\to s<1$ and $P_ω(X_{t_m}/s_m\leq x)\to1/2$ for all $x>0$ and $\to0$ for $x\leq0$ (a spread out regime).

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Differing averaged and quenched large deviations for random walks in random environments in dimensions two and three

We consider the quenched and the averaged (or annealed) large deviation rate functions $I_q$ and $I_a$ for space-time and (the usual) space-only RWRE on $\mathbb{Z}^d$. By Jensen's inequality, $I_a\leq I_q$. In the space-time case, when $d\geq3+1$, $I_q$ and $I_a$ are known to be equal on an open set containing the typical velocity $ξ_o$. When $d=1+1$, we prove that $I_q$ and $I_a$ are equal only at $ξ_o$. Similarly, when d=2+1, we show that $I_a<I_q$ on a punctured neighborhood of $ξ_o$. In the space-only case, we provide a class of non-nestling walks on $\mathbb{Z}^d$ with d=2 or 3, and prove that $I_q$ and $I_a$ are not identically equal on any open set containing $ξ_o$ whenever the walk is in that class. This is very different from the known results for non-nestling walks on $\mathbb{Z}^d$ with $d\geq4$.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Recursions and tightness for the maximum of the discrete, two dimensional Gaussian Free Field

We consider the maximum of the discrete two dimensional Gaussian free field in a box, and prove the existence of a (dense) deterministic subsequence along which the maximum, centered at its mean, is tight; this still leaves open the conjecture that tightness holds without the need for subsequences. The method of proof relies on an argument developed by Dekking and Host for branching random walks with bounded increments and on comparison results specific to Gaussian fields.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

The single ring theorem

We study the empirical measure $L_{A_n}$ of the eigenvalues of non-normal square matrices of the form $A_n=U_nD_nV_n$ with $U_n,V_n$ independent Haar distributed on the unitary group and $D_n$ real diagonal. We show that when the empirical measure of the eigenvalues of $D_n$ converges, and $D_n$ satisfies some technical conditions, $L_{A_n}$ converges towards a rotationally invariant measure on the complex plan whose support is a single ring. In particular, we provide a complete proof of Feinberg-Zee single ring theorem \cite{FZ}. We also consider the case where $U_n,V_n$ are independent Haar distributed on the orthogonal group.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Tightness of Fluctuations of First Passage Percolation on Some Large Graphs

The theorem of Dekking and Host regarding tightness around the mean of first passage percolation on the binary tree, from the root to a boundary of a ball, is generalized to a class of graphs which includes all lattices in hyperbolic spaces and the lamplighter graph over N. This class of graphs is closed under product with any bounded degree graph. Few open problems and conjectures are gathered at the end.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Tightness of the recentered maximum of the two-dimensional discrete Gaussian Free Field

We consider the maximum of the discrete two dimensional Gaussian free field (GFF) in a box, and prove that its maximum, centered at its mean, is tight, settling a long-standing conjecture. The proof combines a recent observation of Bolthausen, Deuschel and Zeitouni with elements from (Bramson 1978) and comparison theorems for Gaussian fields. An essential part of the argument is the precise evaluation, up to an error of order 1, of the expected value of the maximum of the GFF in a box. Related Gaussian fields, such as the GFF on a two-dimensional torus, are also discussed.

0 citations0 reviewsNo code linkedOpen access
preprint2003arXiv

The Poisson-Dirichlet law is the unique invariant distribution for uniform split-merge transformations

We consider a Markov chain on the space of (countable) partitions of the interval [0,1], obtained first by size biased sampling twice (allowing repetitions) and then merging the parts (if the sampled parts are distinct) or splitting the part uniformly (if the same part was sampled twice). We prove a conjecture of Vershik stating that the Poisson-Dirichlet law with parameter theta=1 is the unique invariant distribution for this Markov chain. Our proof uses a combination of probabilistic, combinatoric, and representation-theoretic arguments.

0 citations0 reviewsNo code linkedOpen access