Displaying similar documents to “Consistent minimal displacement of branching random walks.”

Giant vacant component left by a random walk in a random d-regular graph

Jiří Černý, Augusto Teixeira, David Windisch (2011)

Annales de l'I.H.P. Probabilités et statistiques

Similarity:

We study the trajectory of a simple random walk on a -regular graph with ≥ 3 and locally tree-like structure as the number of vertices grows. Examples of such graphs include random -regular graphs and large girth expanders. For these graphs, we investigate percolative properties of the set of vertices not visited by the walk until time , where > 0 is a fixed positive parameter. We show that this so-called set exhibits a phase transition in in the following sense: there exists...

Large deviations for transient random walks in random environment on a Galton–Watson tree

Elie Aidékon (2010)

Annales de l'I.H.P. Probabilités et statistiques

Similarity:

Consider a random walk in random environment on a supercritical Galton–Watson tree, and let be the hitting time of generation . The paper presents a large deviation principle for /, both in quenched and annealed cases. Then we investigate the subexponential situation, revealing a polynomial regime similar to the one encountered in one dimension. The paper heavily relies on estimates on the tail distribution of the first regeneration time.

An upper bound on the space complexity of random formulae in resolution

Michele Zito (2002)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

We prove that, with high probability, the space complexity of refuting a random unsatisfiable Boolean formula in k -CNF on n variables and m = Δ n clauses is O n · Δ - 1 k - 2 .