The path of a simple random walk on a graph is simply the subgraph consisting of all the edges crossed and vertices visited by the walk. We prove that the path of a simple random walk on any graph is a.s. recurrent, i.e. a simple random walk on it is recurrent.
We show that the edges crossed by a random walk in a network form a recurrent graph a.s. In fact, the same is true when those edges are weighted by the number of crossings.
We consider a Branching Random Walk on R whose step size decreases by a fixed factor, 1>b>0, with each turn. This process generates a random probability measure on R, that is, the limit of uniform distribution among the 2^n particles of the n-th step. We present an initial investigation of the limit measure and its support. We show, in particular, that:
(1) for almost every b>1/2 the limit measure is a.s. absolutely continuous with respect to the Lebesgue measure, but for Pisot 1/b it is a.s. singular;
(2) for all b>(\sqrt{5}-1)/2 the support of the measure is a.s. the closure of its interior;
(3) for Pisot 1/b the support of the measure is fractured: it is a.s. disconnected and the components of the complement are not isolated on both sides.
In the Biham-Middleton-Levine traffic model cars are placed with some density p on a two dimensional torus, and move according to a (simple) set of predefined rules. Computer simulations show this system exhibits many interesting phenomena: for low densities the system self organizes such that cars flow freely while for densities higher than some critical density the system gets stuck in an endless traffic jam. However, apart from the simulation results very few properties of the system were proven rigorously to date.
We introduce a simplified version of this model in which cars are placed in a single row and column (a junction) and show that similar phenomena of self-organization of the system and phase transition still occur.
A random graph process, G1(n), is a sequence of graphs on n vertices which begins with the edgeless graph, and where at each step a single edge is added according to a uniform distribution on the missing edges. It is well known that in such a process a giant component (of linear size) typically emerges after (1+o(1))n/2 edges (a phenomenon known as ``the double jump''), i.e., at time t=1 when using a timescale of n/2 edges in each step.
We consider a generalization of this process, GK(n), which gives a weight of size 1 to missing edges between pairs of isolated vertices, and a weight of size K otherwise. This corresponds to a case where links are added between n initially isolated settlements, where the probability of a new link in each step is biased according to whether or not its two endpoint settlements are still isolated.
Combining methods of [13] with analytical techniques, we describe the typical emerging time of a giant component in this process, tc(K), as the singularity point of a solution to a set of differential equations. We proceed to analyze these differential equations and obtain properties of GK, and in particular, we show that tc(K) strictly decreases from 3/2 to 0 as K increases from 0 to infinity, and that tc(K)=(4+o(1))/(3K)1/2. Numerical approximations of the differential equations agree both with computer simulations of the process GK(n) and with the analytical results.
Consider the Cayley graph of the cyclic group of prime order q with k uniformly chosen generators. For fixed k, we prove that the diameter of said graph is asymptotically (in q) of order q^(1/k).
The same also holds when the generating set is taken to be a symmetric set of size 2k.
Pursuit-Evasion Games (in discrete time) are stochastic games with nonnegative daily payoffs, with the final payoff being the cumulative sum of payoffs during the game. We show that such games admit a value even in the presence of incomplete information and that this value is uniform, i.e. there are epsilon-optimal strategies for both players that are epsilon-optimal in any long enough prefix of the game. We give an example to demonstrate that nonnegativity is essential and expand the results to Leavable Games.
We pursue a systematic study of the following problem. Let f:{0,1}^n->{0,1} be a (usually monotone) boolean function whose behaviour is well understood when the input bits are identically independently distributed. What can be said about the behaviour of the function when the input bits are not completely independent, but only k-wise independent, i.e. every subset of k bits is independent? more precisely, how high should k be so that any k-wise independent distribution fools the function, i.e. causes it to behave nearly the same as when the bits are completely independent?
In this paper, we are mainly interested in asymptotic results about monotone functions which exhibit sharp thresholds, i.e. there is a critical probability, pc, such that P(f=1) under the completely independent distribution with marginal p, makes a sharp transition, from being close to 0 to being close to 1, in the vicinity of p_c. For such (sequences of) functions we define 2 notions of fooling: K_1 is the independence needed in order to force the existence of the sharp threshold (which must then be at p_c). K_2 is the independence needed to fool the function at p_c.
In order to answer these questions, we explore the extremal properties of k-wise independent distributions and provide ways of constructing such distributions. These constructions are connected to linear error correcting codes.
We also utilize duality theory and show that for the function f to behave (almost) the same under all k-wise independent inputs is equivalent to the function f being well approximated by a real polynomial in a certain fashion. This type of approximation is stronger than approximation in L_1.
We analyze several well known boolean functions (including AND, Majority, Tribes and Percolation among others), some of which turn out to have surprising properties with respect to these questions.
In some of our results we use tools from the theory of the classical moment problem, seemingly for the first time in this subject, to shed light on these questions.
We consider a planar Poisson process and its associated Voronoi map. We show that there is a proper coloring with 6 colors of the map which is a deterministic isometry-equivariant function of the Poisson process. As part of the proof we show that the 6-core of the corresponding Delaunay triangulation is empty.
Generalizations, extensions and some open questions are discussed.
We construct a bounded degree graph G, such that a simple random walk on it is transient but the random walk path (i.e., the subgraph of all the edges the random walk has crossed) has only finitely many cutpoints, almost surely. We also prove that the expected number of cutpoints of any transient Markov chain is infinite. This answers two questions of James, Lyons and Peres.
Additionally, we consider a simple random walk on a finite connected graph G that starts at some fixed vertex x and is stopped when it first visits some other fixed vertex y. We provide a lower bound on the expected effective resistance between x and y in the path of the walk, giving a partial answer to a question raised here.
In the classical balls-and-bins paradigm, where n balls are placed independently and uniformly in n bins, typically the number of bins with at least two balls in them has order n and the maximum number of balls in a bin has order (log n)/(log log n). It is well known that when each round offers k independent uniform options for bins, it is possible to typically achieve a constant maximal load if and only if k is at least of order (log n). Moreover, it is possible whp to avoid any collisions between (n/2) balls if (k> log_2 n).
In this work, we extend this into the setting where only m bits of memory are available. We establish a tradeoff between the number of choices k and the memory m, dictated by the quantity km/n. Roughly put, we show that for (k m) larger than n, one can achieve a constant maximal load, while for (k m) smaller than n no substantial improvement can be gained over the case k=1 (i.e., a random allocation).
For any (k = \Omega(log n)) and (m = \Omega(log^2 n)), one can achieve a constant load whp if (k m = \Omega(n)), yet the load is unbounded if (k m =o(n)). Similarly, if (k m > C n) then (n/2) balls can be allocated without any collisions whp, whereas for (k m < \epsilon n) there are typically order n collisions. Furthermore, we show that the load is whp at least log(n/m)/[log k + log log(n/m)]. In particular, for k=polylog(n), if m = n^{1-\delta} the optimal maximal load is of order (log n)/(log log n) (the same as in the case k=1), while m=2n suffices to ensure a constant load. Finally, we analyze non-adaptive allocation algorithms and give tight upper and lower bounds for their performance.
We prove that for the Activated Random Walks model on transitive unimodular graphs, if there is fixation, then every particle eventually fixates, almost surely. We deduce that the critical density is at most 1.
Our methods apply for much more general processes on unimodular graphs. Roughly put, our result apply whenever the path of each particle has an automorphism invariant distribution and is independent of other particles' paths, and the interaction between particles is automorphism invariant and local. This allows us to answer a question of Rolla and Sidoravicius, in a more general setting then had been previously known (by Shellef).
Let X be a Poisson point process of intensity lambda on the real line. A thickening of it is a (deterministic) measurable function f such that the union of X and f(X) is a Poisson point process of intensity lambda' where lambda'>lambda. An equivariant thickening is a thickening which commutes with all shifts of the line. We show that a thickening exists but an equivariant thickening does not. We prove similar results for thickenings which commute only with integer shifts and in the discrete and multi-dimensional settings. This answers 3 questions of Holroyd, Lyons and Soo.
We show that the distribution of the first return time tau to the origin, v, of a simple random walk on an infinite recurrent graph is heavy tailed and non-concentrated. More precisely, if d_v is the degree of v then for any t>1 we have P_v(tau \ge t) > c d_v^{-1} t^{-1/2} and P_v(tau = t | tau \ge t) < C log(d_v t) t^{-1}. The first bound is attained for all t when the underlying graph is Z, and as for the second bound, we construct an example of a recurrent graph G for which it is attained for infinitely many t's.
Furthermore, we show that in the comb product of G with Z, two independent random walks collide infinitely many times almost surely. This answers negatively a question of Krishnapur and Peres who asked whether any comb product of two infinite recurrent graphs has the finite collision property.
The whitespace-discovery problem describes two parties, Alice and Bob, trying to establish a communication channel over one of a given large segment of whitespace channels. Subsets of the channels are occupied in each of the local environments surrounding Alice and Bob, as well as in the global environment between them (Eve). In the absence of a common clock for the two parties, the goal is to devise time-invariant (stationary) strategies minimizing the synchronization time. This emerged from recent applications in discovery of wireless devices.
We model the problem as follows. There are N channels, each of which is open (unoccupied) with probability p1,p2,q independently for Alice, Bob and Eve respectively. Further assume that N » 1/(p1p2q) to allow for sufficiently many open channels. Both Alice and Bob can detect which channels are locally open and every time-slot each of them chooses one such channel for an attempted sync. One aims for strategies that, with high probability over the environments, guarantee a shortest possible expected sync time depending only on the pi's and q.
Here we provide a stationary strategy for Alice and Bob with a guaranteed expected sync time of O(1/p1p2q2)) given that each party also has knowledge of p1,p2,q. When the parties are oblivious of these probabilities, analogous strategies incur a cost of a poly-log factor, i.e. Õ(1/(p1p2q2)). Furthermore, this performance guarantee is essentially optimal as we show that any stationary strategies of Alice and Bob have an expected sync time of at least W(1/(p1p2q2)).
We are given a graph G with n vertices, where a random subset of k vertices has been made into a clique, and the remaining edges are chosen independently with probability 1/2. This random graph model is denoted G(n,1/2,k). The hidden clique problem is to design an algorithm that finds the k-clique in polynomial time with high probability. An algorithm due to Alon, Krivelevich and Sudakov uses spectral techniques to find the hidden clique with high probability when k = C n1/2 for a sufficiently large constant C > 0. Recently, an algorithm that solves the same problem was proposed by Feige and Ron. It has the advantages of being simpler and more intuitive, and of an improved running time of O(n2). However, the analysis in the paper gives success probability of only 2/3. In this paper we present a new algorithm for finding hidden cliques that both runs in time O(n^2), and has a failure probability that is less than polynomially small.
We show that the probability that a simple random walk covers a finite, bounded degree graph in linear time is exponentially small.
More precisely, for every D and C, there exists a=a(D,C)>0 such that for any graph G, with n vertices and maximal degree D, the probability that a simple random walk, started anywhere in G, will visit every vertex of G in its first Cn steps is at most e-an.
We conjecture that the same holds for a=a(C) that does not depend on D, provided that the graph G is simple.