Lipschitz embeddings of random sequences

DOI10.1007/S00440-013-0519-7MaRDI QIDQ398782zbMATH OpenOpenAlexFDO

Authors Riddhipratim Basu, Allan Sly

Publication date 15 August 2014

Published in Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1204.2931

zbMATH Keywords

Poisson processespercolationrandom sequencesLipschitz embeddingBernoulli sequencecompatible sequencesrough isometry

Mathematics Subject Classification ID

Point processes (e.g., Poisson, Cox, Hawkes processes) (60G55) Geometric probability and stochastic geometry (60D05) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Abstract: We develop a new multi-scale framework flexible enough to solve a number of problems involving embedding random sequences into random sequences. Grimmett, Liggett and Richthammer asked whether there exists an increasing M-Lipschitz embedding from one i.i.d. Bernoulli sequences into an independent copy with positive probability. We give a positive answer for large enough M. A closely related problem is to show that two independent Poisson processes on R are roughly isometric (or quasi-isometric). Our approach also applies in this case answering a conjecture of Szegedy and of Peled. Our theorem also gives a new proof to Winkler's compatible sequences problem.

Recommendations

• Lipschitz embeddings of random fields
• Lattice embeddings in percolation
• Clairvoyant embedding in one dimension
• On Lipschitz embedding of finite metric spaces in Hilbert space
• On rough isometries of Poisson processes on the line

Cites work

• scientific article; zbMATH DE number 3732851 (Why is no real title available?)
• scientific article; zbMATH DE number 1416163 (Why is no real title available?)
• Almost all words are seen in critical site percolation on the triangular lattice
• Clairvoyant embedding in one dimension
• Clairvoyant scheduling of random walks
• Collisions Among Random Walks on a Graph
• Compatible Sequences and a Slow Winkler Percolation
• Dependent percolation in two dimensions
• Geometry of Lipschitz percolation
• Lattice embeddings in percolation
• Less than continuum many translates of a compact nullset may cover any infinite profinite group
• Lipschitz percolation
• On rough isometries of Poisson processes on the line
• On the Compatibility of Binary Sequences
• Oriented percolation in a random environment
• Percolation of Words on Z^d with Long-Range Connections
• Percolation of arbitrary words in \(\{0, 1\}^ \mathbb{N}\)
• Percolation of arbitrary words in one dimension
• Percolation of arbitrary words on the close-packed graph of \(\mathbb{Z}^2\)
• Plaquettes, spheres, and entanglement
• Rough isometries, and combinatorial approximations of geometries of non- compact Riemannian manifolds
• Stochastic domination and comb percolation
• Three problems for the clairvoyant demon

Cited in

(11)

• Dependent percolation on \(\mathbb{Z}^2\)
• On the Compatibility of Binary Sequences
• Random ε-nets and embeddings in l^N_∞
• Oriented percolation in a random environment
• Compatible sequences and a slow Winkler percolation
• Embedding binary sequences into Bernoulli site percolation on \(\mathbb{Z}^3\)
• Lipschitz embeddings of random fields
• Harry Kesten's work in probability theory
• Clairvoyant embedding in one dimension
• Scheduling of non-colliding random walks
• Random embedding of \({\ell_p^n}\) into \({\ell_r^N}\)

This page was built for publication: Lipschitz embeddings of random sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q398782)