The Number of Generations Entirely Visited for Recurrent Random Walks in a Random Environment

In this paper we deal with a random walk in a random environment on a super-critical Galton–Watson tree. We focus on the recurrent cases already studied by Hu and Shi (Ann. Probab. 35:1978–1997, 2007; Probab. Theory Relat. Fields 138:521–549, 2007), Faraud et al. (Probab. Theory Relat. Fields, 2011, in press), and Faraud (Electron. J. Probab. 16(6):174–215, 2011). We prove that the largest generation entirely visited by these walks behaves like logn, and that the constant of normalization, which differs from one case to another, is a function of the inverse of the constant of Biggins’ law of large numbers for branching random walks (Biggins in Adv. Appl. Probab. 8:446–459, 1976).     

Group-Theoretic Dimension of Stationary Symmetric α-Stable Random Fields

The growth rate of the partial maximum of a stationary stable process was first studied in the works of Samorodnitsky (Ann. Probab. 32:1438–1468, 2004; Adv. Appl. Probab. 36:805–823, 2004), where it was established, based on the seminal works of Rosiński (Ann. Probab. 23:1163–1187, 1995; 28:1797–1813, 2000), that the growth rate is connected to the ergodic-theoretic properties of the flow that generates the process. The results were generalized to the case of stable random fields indexed by ? ^d in Roy and Samorodnitsky (J. Theor. Probab. 21:212–233, 2008), where properties of the group of nonsingular transformations generating the stable process were studied as an attempt to understand the growth rate of the partial maximum process. This work generalizes this connection between stable random fields and group theory to the continuous parameter case, that is, to fields indexed by ? ^d .     

Linear SPDEs Driven by Stationary Random Distributions

Using tools from the theory of stationary random distributions developed in It? (Mem. Coll. Sci., Univ. Kyoto, Ser. A: Math., 28:209?C223,?1954) and Yaglom (Theory Probab. Appl., 2:273?C320,?1957), we introduce a new class of processes which can be used as a model for the noise perturbing an SPDE. This type of noise is not necessarily Gaussian, but it includes the spatially homogeneous Gaussian noise introduced in Dalang (Electron. J. Probab. 4(6)?1999), and the fractional noise considered in Balan and Tudor (Stoch. Process. Appl., 120:2468?C2494,?2010). We derive some general conditions for the existence of a random field solution of a linear SPDE with this type of noise, under some mild conditions imposed on the Green function of the differential operator which appears in this equation. This methodology is applied to the study of the heat and wave equations (possibly replacing the Laplacian by one of its fractional powers), extending in this manner the results of Balan and Tudor (Stoch. Process. Appl., 120:2468?C2494,?2010) to the case H<1/2.     

Positive recurrence for reflecting Brownian motion in?higher dimensions

Semimartingale reflecting Brownian motions (SRBMs) are diffusion processes with state space the d-dimensional nonnegative orthant, in the interior of which the processes evolve according to a Brownian motion, and that reflect against the boundary in a specified manner. A standard problem is to determine under what conditions the process is positive recurrent. Necessary and sufficient conditions for positive recurrence are easy to formulate in d=2, but not in d??3. Fluid paths are solutions of deterministic equations that correspond to the random equations of the SRBM. A standard result of Dupuis and Williams (in Ann. Probab. 22:680?C702, 1994) states that when every fluid path associated with the SRBM is attracted to the origin, the SRBM is positive recurrent. Employing this result, El Kharroubi et al. (in Stoch. Stoch. Rep. 68:229?C253, 2000; Math. Methods Oper. Res. 56:243?C258, 2002) gave sufficient conditions involving fluid paths for positive recurrence of SRBM in d=3. Here, we discuss two recent results regarding necessary conditions for positive recurrence of SRBM in d??3. Bramson et al. (in Ann. Appl. Probab. 20:753?C783, 2010) showed that the conditions in El Kharroubi et al. (Math. Methods Oper. Res. 56:243?C258, 2002) are, in fact, necessary in d=3. On the other hand, Bramson (in Ann. Appl. Probab., to appear, 2011) provided a family of positive recurrent SRBMs, in d??6, with linear fluid paths that diverge to infinity. The latter result shows in particular that the converse of the Dupuis?CWilliams result does not hold.     

Adjustment Coefficient for Risk Processes in Some Dependent Contexts

Following Müller and Pflug (Insur Math Econ 28:381?C392, 2001) and Nyrhinen (Adv Appl Probab 30:1008?C1026, 1998; J Appl Probab 36:733?C746, 1999), we study the adjustment coefficient of ruin theory in a context of temporal dependency. We provide a consistent estimator for this coefficient, and perform some simulations.     

A BK inequality for randomly drawn subsets of fixed size

The BK inequality (van den Berg and Kesten in J Appl Probab 22:556?C569, 1985) says that, for product measures on {0, 1} ⁿ , the probability that two increasing events A and B ??occur disjointly?? is at most the product of the two individual probabilities. The conjecture in van den Berg and Kesten (1985) that this holds for all events was proved by Reimer (Combin Probab Comput 9:27?C32, 2000). Several other problems in this area remained open. For instance, although it is easy to see that non-product measures cannot satisfy the above inequality for all events, there are several such measures which, intuitively, should satisfy the inequality for all increasing events. One of the most natural candidates is the measure assigning equal probabilities to all configurations with exactly k 1??s (and probability 0 to all other configurations). The main contribution of this paper is a proof for these measures. We also point out how our result extends to weighted versions of these measures, and to products of such measures.     

Precise large deviations for dependent regularly varying sequences

We study a precise large deviation principle for a stationary regularly varying sequence of random variables. This principle extends the classical results of Nagaev (Theory Probab Appl 14:51–64, 193–208, 1969) and Nagaev (Ann Probab 7:745–789, 1979) for iid regularly varying sequences. The proof uses an idea of Jakubowski (Stoch Proc Appl 44:291–327, 1993; 68:1–20, 1997) in the context of central limit theorems with infinite variance stable limits. We illustrate the principle for stochastic volatility models, real valued functions of a Markov chain satisfying a polynomial drift condition and solutions of linear and non-linear stochastic recurrence equations.     

A Characterization of the Locally Finite Networks Admitting Non-Constant Harmonic Functions of Finite Energy

We characterize the locally finite networks admitting non-constant harmonic functions of finite energy. Our characterization unifies the necessary existence criteria of Thomassen (J Comb Theory, Ser B 49:87?C102, 1990) and of Lyons and Peres (2011) with the sufficient criterion of Soardi (1991). We also extend a necessary existence criterion for non-elusive non-constant harmonic functions of finite energy due to Georgakopoulos (J Lond Math Soc, 2010).     

Simple random walk on the uniform infinite planar quadrangulation: subdiffusivity via pioneer points

We study the pioneer points of the simple random walk on the uniform infinite planar quadrangulation (UIPQ) using an adaptation of the peeling procedure of Angel (Geom Funct Anal 13:935–974, 2003) to the quadrangulation case. Our main result is that, up to polylogarithmic factors, n ³ pioneer points have been discovered before the walk exits the ball of radius n in the UIPQ. As a result we verify the KPZ relation Knizhnik et al. (Modern Phys Lett A 3:819–826, 1988) in the particular case of the pioneer exponent and prove that the walk is subdiffusive with exponent less than 1/3. Along the way, new geometric controls on the UIPQ are established.     

Convergence to extremal processes in random environments and extremal ageing in SK models

This paper extends recent results on ageing in mean field spin glasses on short time scales, obtained by Ben Arous and Gün (Commun Pure Appl Math 65:77–127, 2012) in law with respect to the environment, to results that hold almost surely, respectively in probability, with respect to the environment. It is based on the methods put forward in (Gayrard in Aging in reversible dynamics of disordered systems. II. Emergence of the arcsine law in the random hopping time dynamics of the REM, 2010; Electron J Probab 17(58): 1–33, 2012) and naturally complements (Bovier and Gayrard in Ann Probab, 2012).     

Asymptotics of q-plancherel measures

In this paper, we are interested in the asymptotic size of the rows and columns of a random Young diagram under a natural deformation of the Plancherel measure coming from Hecke algebras. The first lines of such diagrams are typically of order n, so it does not fit in the context of the work of Biane (Int Math Res Notices 4:179–192, 2001) and ?niady (Probab. Theory Relat Fields 136:263–297, 2006). Using the theory of polynomial functions on Young diagrams of Kerov and Olshanski, we are able to compute explicitly the first- and second-order asymptotics of the length of the first rows. Our method also works for other measures, for example those coming from Schur–Weyl representations.     

Extended Formulations for Polygons

The extension complexity of a polytope?P is the smallest integer?k such that?P is the projection of a polytope?Q with?k facets. We study the extension complexity of n-gons in the plane. First, we give a new proof that the extension complexity of regular n-gons is O(logn), a result originating from work by Ben-Tal and Nemirovski (Math. Oper. Res. 26(2), 193?C205, 2001). Our proof easily generalizes to other permutahedra and simplifies proofs of recent results by Goemans (2009), and Kaibel and Pashkovich (2011). Second, we prove a lower bound of $\sqrt{2n}$ on the extension complexity of generic n-gons. Finally, we prove that there exist n-gons whose vertices lie on an O(n)×O(n ²) integer grid with extension complexity $\varOmega (\sqrt{n}/\sqrt{\log n})$ .     

More about λ-support iterations of (<λ)-complete forcing notions

This article continues Ros?anowski and Shelah (Int J Math Math Sci 28:63–82, 2001; Quaderni di Matematica 17:195–239, 2006; Israel J Math 159:109–174, 2007; 2011; Notre Dame J Formal Logic 52:113–147, 2011) and we introduce here a new property of (<λ)-strategically complete forcing notions which implies that their λ-support iterations do not collapse λ ⁺ (for a strongly inaccessible cardinal λ).     

Right-convergence of sparse random graphs

The paper is devoted to the problem of establishing right-convergence of sparse random graphs. This concerns the convergence of the logarithm of number of homomorphisms from graphs or hyper-graphs \(\mathbb{G }_N, N\ge 1\) to some target graph \(W\) . The theory of dense graph convergence, including random dense graphs, is now well understood (Borgs et al. in Ann Math 176:151–219, 2012; Borgs et al. in Adv Math 219:1801–1851, 2008; Chatterjee and Varadhan in Eur J Comb 32:1000–1017, 2011; Lovász and Szegedy in J Comb Theory Ser B 96:933–957, 2006), but its counterpart for sparse random graphs presents some fundamental difficulties. Phrased in the statistical physics terminology, the issue is the existence of the limits of appropriately normalized log-partition functions, also known as free energy limits, for the Gibbs distribution associated with \(W\) . In this paper we prove that the sequence of sparse Erdös-Rényi graphs is right-converging when the tensor product associated with the target graph \(W\) satisfies a certain convexity property. We treat the case of discrete and continuous target graphs \(W\) . The latter case allows us to prove a special case of Talagrand’s recent conjecture [more accurately stated as level III Research Problem 6.7.2 in his recent book (Talagrand in Mean Field Models for Spin Glasses: Volume I: Basic examples. Springer, Berlin, 2010)], concerning the existence of the limit of the measure of a set obtained from \(\mathbb{R }^N\) by intersecting it with linearly in \(N\) many subsets, generated according to some common probability law. Our proof is based on the interpolation technique, introduced first by Guerra and Toninelli (Commun Math Phys 230:71–79, 2002) and developed further in (Abbe and Montanari in On the concentration of the number of solutions of random satisfiability formulas, 2013; Bayati et al. in Ann Probab Conference version in Proceedings of 42nd Ann. Symposium on the Theory of Computing (STOC), 2010; Contucci et al. in Antiferromagnetic Potts model on the Erdös-Rényi random graph, 2011; Franz and Leone in J Stat Phys 111(3/4):535–564, 2003; Franz et al. in J Phys A Math Gen 36:10967–10985, 2003; Montanari in IEEE Trans Inf Theory 51(9):3221–3246, 2005; Panchenko and Talagrand in Probab Theory Relat Fields 130:312–336, 2004). Specifically, Bayati et al. (Ann Probab Conference version in Proceedings of 42nd Ann. Symposium on the Theory of Computing (STOC), 2010) establishes the right-convergence property for Erdös-Rényi graphs for some special cases of \(W\) . In this paper most of the results in Bayati et al. (Ann Probab Conference version in Proceedings of 42nd Ann. Symposium on the Theory of Computing (STOC), 2010) follow as a special case of our main theorem.     

An Interacting Particle Model and a Pieri-Type Formula for the Orthogonal Group

We introduce a new interacting particle model with blocking and pushing interactions. Particles evolve on ?₊ jumping on their own volition rightwards or leftwards according to geometric jumps with parameter q∈(0,1). We show that the model involves a Pieri-type formula for the orthogonal group. We prove that the two extreme cases—q=0 and q=1—lead, respectively, to the random tiling model studied in Borodin and Kuan (Commun. Pure Appl. Math. 67:831–894, 2010) and the random matrix model considered in forthcoming paper of Defosseux (Electr. Commun. Probab., 2012).     

L p -theory for second-order elliptic operators with unbounded coefficients

Second-order elliptic operators with unbounded coefficients of the form ${Au := -{\rm div}(a\nabla u) + F . \nabla u + Vu}$ in ${L^{p}(\mathbb{R}^{N}) (N \in \mathbb{N}, 1 < p < \infty)}$ are considered, which are the same as in recent papers Metafune et?al. (Z Anal Anwendungen 24:497–521, 2005), Arendt et?al. (J Operator Theory 55:185–211, 2006; J Math Anal Appl 338: 505–517, 2008) and Metafune et?al. (Forum Math 22:583–601, 2010). A new criterion for the m-accretivity and m-sectoriality of A in ${L^{p}(\mathbb{R}^{N})}$ is presented via a certain identity that behaves like a sesquilinear form over L ^p ×?L ^p'. It partially improves the results in (Metafune et?al. in Z Anal Anwendungen 24:497–521, 2005) and (Metafune et?al. in Forum Math 22:583–601, 2010) with a different approach. The result naturally extends Kato’s criterion in (Kato in Math Stud 55:253–266, 1981) for the nonnegative selfadjointness to the case of p ≠?2. The simplicity is illustrated with the typical example ${Au = -u\hspace{1pt}'' + x^{3}u\hspace{1pt}' + c |x|^{\gamma}u}$ in ${L^p(\mathbb{R})}$ which is dealt with in (Arendt et?al. in J Operator Theory 55:185–211, 2006; Arendt et?al. in J Math Anal Appl 338: 505–517, 2008).     

A new existence proof for Steiner quadruple systems

A Steiner quadruple system of order v is an ordered pair ${(X, \mathcal{B})}$ , where X is a set of cardinality v, and ${\mathcal{B}}$ is a set of 4-subsets of X, called blocks, with the property that every 3-subset of X is contained in a unique block. Such designs exist if and only if ${v \equiv 2,4\, (\bmod\, 6)}$ . The first and second proofs of this result were given by Hanani in 1960 and in 1963, respectively. All the existing proofs are rather cumbersome, even though simplified proofs have been given by Lenz in 1985 and by Hartman in 1994. To study Steiner quadruple systems, Hanani introduced the concept of H-designs in 1963. The purpose of this paper is to provide an alternative existence proof for Steiner quadruple systems via H-designs of type 2 ⁿ . In 1990, Mills showed that for n > 3, n ≠ 5, an H-design of type g ⁿ exists if and only if ng is even and g(n ? 1)(n ? 2) is divisible by 3, where the main context is the complicated existence proof for H-designs of type 2 ⁿ . However, Mill’s proof was based on the existence result of Steiner quadruple systems. In this paper, by using the theory of candelabra systems and H-frames, we give a new existence proof for H-designs of type 2 ⁿ independent of the existence result of Steiner quadruple systems. As a consequence, we also provide a new existence proof for Steiner quadruple systems.     

Averaging Fluctuations in Resolvents of Random Band Matrices

We consider a general class of random matrices whose entries are centred random variables, independent up to a symmetry constraint. We establish precise high-probability bounds on the averages of arbitrary monomials in the resolvent matrix entries. Our results generalize the previous results of Erd?s et al. (Ann Probab, arXiv:1103.1919, 2013; Commun Math Phys, arXiv:1103.3869, 2013; J Combin 1(2):15–85, 2011) which constituted a key step in the proof of the local semicircle law with optimal error bound in mean-field random matrix models. Our bounds apply to random band matrices and improve previous estimates from order 2 to order 4 in the cases relevant to applications. In particular, they lead to a proof of the diffusion approximation for the magnitude of the resolvent of random band matrices. This, in turn, implies new delocalization bounds on the eigenvectors. The applications are presented in a separate paper (Erd?s et al., arXiv:1205.5669, 2013).     

A Capped Optimal Stopping Problem for the Maximum Process

This paper concerns an optimal stopping problem driven by the running maximum of a spectrally negative Lévy process X. More precisely, we are interested in capped versions of the American lookback optimal stopping problem (Gapeev in J. Appl. Probab. 44:713–731, 2007; Guo and Shepp in J. Appl. Probab. 38:647–658, 2001; Pedersen in J. Appl. Probab. 37:972–983, 2000), which has its origins in mathematical finance, and provide semi-explicit solutions in terms of scale functions. The optimal stopping boundary is characterised by an ordinary first-order differential equation involving scale functions and, in particular, changes according to the path variation of X. Furthermore, we will link these capped problems to Peskir’s maximality principle (Peskir in Ann. Probab. 26:1614–1640, 1998).