Probability
Random walks (RWs) on networks have been extensively studied due to their relevance in various fields including Mathematics, Physics and Computer Science. RWs serve as a versatile tool for understanding the underlying network as well as dynamical processes that take place on them. Focusing on Random Regular Graphs (RRGs), I will present various analytical results describing important events in the life-cycle of RWs on RRGs, namely the distributions of the first hitting time, the first return time, the first passage time and the cover time.
The properties of materials are often understood in terms of their structure and symmetries.
Order is often manifested in correlations of an order parameter that extends throughout the system. In this talk I will discuss an exotic ordering that is paradoxically found in disordered systems. This ordering is known as hyperuniformity, and is defined as having suppressed fluctuations on arbitrary long length scales. While the fluctuations of a random uncorrelated arrangement of particles scales as the enclosed volume, hyperuniform fluctuations grow as the volume^alpha, with alpha<1.
I will discuss the occurrence of hyperuniformity in two distinct non-equilibrium phase transitions: (1) An absorbing phase transition found in sheared colloidal suspensions. (2) The jamming transitions of soft spheres at zero temperature. Hyperuniformity in these systems is manifested in two different fields and is characterized by different exponents. Interestingly, near both these transitions there are two different diverging correlation lengths. Our work demonstrates that exotic order can be hidden in plain sight, and that structures that form out of equilibrium may be fundamentally different from their equilibrium counterparts.
We study the optimal use of information in Markov games with incomplete information on one side and two states.
We provide a finite-stage algorithm for calculating the limit value as the gap between stages goes to 0, and an optimal strategy for the informed player in the limiting game in continuous time.
This limiting strategy induces an epsilon-optimal strategy for the informed player, provided the gap between stages is small.
Our results demonstrate when the informed player should use her information and how.
This is joint work with Eilon Solan and Catherine Rainer.
The probabilistic intuition is a surprisingly successful heuristic which links the theory of positional games and the theory of random graphs. Positional games are finite, perfect information two player games with no chance moves and no possibility of a draw. It is known from classical game theory that both players have deterministic optimal strategies for each such game. The probabilistic intuition suggests that a good way of predicting the outcome of such a game under optimal play, is to study what happens when both players play randomly. In this talk I will present several new results of this type.
~~A graph property is first order expressible if it can be written as a logical sentence using the universal and existential quantifiers with variables ranging over the vertices of the graph, the usual connectives and the relations = and ~, where x ~ y stands for adjacency. Starting from the sixties, first order expressible properties have been studied using random models. That is, by looking on the possible behavior of first order properties given a probability space of models. The most extensively studied probability space of graphs is the Erdos-Renyi probability space. A number of very attractive and surprising results have been obtained, and by now we have a fairly full description of the behaviour of first order expressible properties on this model.
The Gilbert model of random graphs is obtained as follows. We take n points uniformly at random from the d-dimensional unit torus, and join two points by an edge if and only their distance is at most r.
In this talk I will discuss a few results which tells a nearly complete story on first order expressible properties of the Gilbert random graph model. In particular we settle several conjectures of McColm and of Agarwal-Spencer.
(Joint with T. Muller)
~~
In this talk, I will give an overview of research topics stemming from applied and random topology, a relatively new field resulting from the application of point-set and algebraic topological methods to data that arise from random processes. The use of topological methods to analyze data is particularly applicable to information technology and networks (e.g. analyzing internet traffic and communications systems), physics (e.g. analyzing cosmological data), biology (e.g. brain imaging and studying gene regulation), and engineering (e.g. studying coordinated robotics). From the perspective of statistics, such methods are applicable to data mining and image processing.
I will outline the methodology of topological data analysis, and discuss recent results on the algebraic topology of random fields and complexes. I will then present some problems that are currently being studied. In particular, I will underline some contributions of applied topology to resolving statistical problems, and how statistical methodology can contribute to resolving applied topological problems.
Continuous Time Random Walks Limits(CTRWL) are used to model fractional diffusion processes (where Var(X_t) is no longer proportional to t). It turns out that the fractional Poisson process(FPP) which is a generalization of the Poisson Process is a CTRWL . While the one dimensional distribution of the FPP is governed by a fractional Fokker-Planck equation, in general fractional diffusion processes are not Markovian a fact that make the process of finding its finite dimensional very complicated. In a recent paper by Mark Meerscheart, a new method for finding the finite dimensional of CTRWL is introduced. We use this method to obtain an interesting representation of the FPP increments.
~~How does a uniformly chosen metric space on n points look like? To formalize this we consider the set of all metric spaces on n points whose diameter is at most 2. Viewing every metric space as a vector of distances, this set becomes a convex polytope in R^{n choose 2} - the metric polytope. A uniformly random metric space is then a space chosen according to the normalized Lebesgue measure on this polytope. It is simple to see that the metric polytope contains the cube [1,2]^{n choose 2}. Our main result is that it does not contain much more. Precisely, that a random metric space is very rigid, having all distances in an interval of the form [1 - n^{-a}, 2] with high probability. We consider three approaches to the problem, with varying degrees of accuracy, based on exchangeability, the Szemerédi regularity lemma and entropy techniques.
Joint work with Gady Kozma, Tom Meyerovitch and Wojciech Samotij.
~~
The limiting spectral distributions of many sparse random graph models are known to contain atoms. But do they also have some continuous part? In this talk, I will give affirmative answer to this question for several widely studied models of random graphs including Erdos-Renyi random graph G(n,c/n) with c > 1, random graphs with certain degree distributions and supercritical bond percolation on Z^2. I will also present several open problems.
This is joint work with Charles Bordenave and Balint Virag.
We present a new definition of the fractional Poisson process (FPP2) with Hurst parameter $H < \frac{1}{2}$, based on a decomposition in law of fractional Brownian motion (FBM), which presented by Covo and Elalouf.
This definition is completely analoguous with the classic case of FBM.
We present two somewhat related results regarding the properties of the Set-indexed H-fractional Brownian motion (sifBm). (1). A proof that almost surely, the sample paths of sifBm have infinite beta=1/H variation on every set. (2). A proof about the convergence of the beta-variation of a sifBm.
Exclusion process and the Zero-range process are two important examples of particle systems on Z that gathered a lot of attention in statistical physics. In this talk I will focus on the totally asymmetric exclusion process and the constant-rate totally asymmetric zero-range process. I will define the two models and discuss their basic properties such as their density evolution and stationary measures. We will then introduce multi-type version of these processes (where particles of several types walk on Z according to the dynamics of the model, with lower type particles having priority over higher type ones) and study initial conditions in when a 2nd class particle develops a random asymptotic speed. We will use these to define new "speed processes" and develop some of their properties. An important tool is an extension of a classic bijection between these two models to their multi-type version which allows translation of results between the two models.
The talk is based on joint work with O. Angel and B. Valko (TASEP) and current work in progress with P. Goncalves and J. Martin.
Hausdorff dimension for non stationary processes
We show that with sufficiently small initial weights, the random walk is recurrent and strongly localized in any graph with bounded degrees. All terms will be explained in the talk.
Random walks on groups have been studied for many years. The corresponding theory on semigroups has lain dormant until the past 15 years, when it was realized that a number of important Markov chains were modeled by random walks on semigroups. These include the Tsetlin library and related models.
The class of semigroups that arise has the property that all of their representations by matrices are triangularizable and have eignvalues either 0 or 1. This allows for the use of representation theoretic methods to rapidly gain information on the corresponding Markov chain.
No previous knowledge of semigroup theory nor of representation theoretic methods in probability are assumed for the talk.
Abstract: A graph homomorphism from a graph G to a graph H is a mapping which preserves edges. By choosing various H, this class includes many well-studied models such as proper colorings, independent sets and Lipschitz functions on G. We show that if G is a regular bipartite expander graph with good expansion, then typical graph homomorphisms on G are very rigid, exhibiting strong spatial correlations. Specifically, in typical realizations, a maximal bipartite subgraph of H is chosen and the homomorphism sends almost all vertices of G into this subgraph. For example, in a typical proper coloring of G each of the partite classes will be colored with only half of the colors, with few exceptions (fewer than would occur deterministically).
No prior knowledge of graph homomorphisms or expander graphs will be assumed. Joint work with Wojciech Samotij and Amir Yehudayoff.
Consider a symmetric random walk on a group G. If the trace of the random walk generates G as a semigroup almost surely, then we say that G is algebraically recurrent. In this talk, we will present some initial steps towards understanding algebraic recurrence, including examples of algebraically recurrent and non-algebraically recurrent groups. We will conclude with some open questions.
This is joint work with Itai Benjamini and Romain Tessera.
We consider balanced environments in Z^d which are stationary and ergodic. We then investigate three features: the behavior of the random walk on them, percolation behavior, and Harnack type inequalities. The study of these objects started with Lawler in 1983, where he completely
analyzed the uniformly elliptic case. Much later, in 2010, Guo and Zeitouni analyzed the merely elliptic case. In this talk I will report on work done in the
non-elliptic case. No background is assumed.
The talk is based on joint works with Jean-Dominique Deuschel and Moran Cohen.
