Lipschitz embeddings of random sequences

Basu, Riddhipratim; Sly, Allan
August 2014
Probability Theory & Related Fields;Aug2014, Vol. 159 Issue 3/4, p721
Academic Journal
We develop a new multi-scale framework flexible enough to solve a number of problems involving embedding random sequences into random sequences. Grimmett et al. (Random Str Algorithm 37(1):85-99, ) asked whether there exists an increasing $$M$$ -Lipschitz embedding from one i.i.d. Bernoulli sequence 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 $$\mathbb R $$ are roughly isometric (or quasi-isometric). Our approach also applies in this case answering a conjecture of Szegedy and of Peled (Ann Appl Probab 20:462-494, ). Our theorem also gives a new proof to Winkler's compatible sequences problem. Our approach does not explicitly depend on the particular geometry of the problems and we believe it will be applicable to a range of multi-scale and random embedding problems.


Related Articles

  • Relaxation and nonoccurrence of the Lavrentiev phenomenon for nonconvex problems. Hüsseinov, Farhad // Acta Mathematica Sinica;Jun2013, Vol. 29 Issue 6, p1185 

    The paper studies a relaxation of the basic multidimensional variational problem, when the class of admissible functions is endowed with the Lipschitz convergence introduced by Morrey. It is shown that in this setup, the integral of a variational problem must satisfy a classical growth...

  • Poissonian subordinators, the Wiener-Ornstein-Uhlenbeck field, and a relation between the Ornstein-Uhlenbeck processes and Brownian bridges. Rusakov, O. // Journal of Mathematical Sciences;Jul2011, Vol. 176 Issue 2, p232 

    We apply to a sequence of i.i.d. random variables a time change operator via a Poisson process that is independent of this sequence. We consider sums of independent copies of processes constructed in this way and having continuous time. Finite limit distributions of these sums coincide with the...

  • Distribution of the smallest visited point in a greedy walk on the line. Gabrysch, Katja // Journal of Applied Probability;Sep2016, Vol. 53 Issue 3, p880 

    We consider a greedy walk on a Poisson process on the real line. It is known that the walk does not visit all points of the process. In this paper we first obtain some useful independence properties associated with this process which enable us to compute the distribution of the sequence of...

  • A LINEARIZATION ALGORITHM FOR NONSMOOTH MINIMIZATION. Kiwiel, Krzysztof Czeseaw // Mathematics of Operations Research;May85, Vol. 10 Issue 2, p185 

    We present a readily implementable algorithm for finding stationary points for locally Lipschitzian functions that are not necessarily convex or differentiable. The algorithm is an extension to the nonconvex case of the aggregate subgradient method. The user can impose an upper bound on storage...

  • 12 days of Christmas Puzzles.  // Actuary;Dec2014, p5 

    No abstract available.

  • Nagata dimension, quasisymmetric embeddings, and Lipschitz extensions. Lang, Urs; Schlichenmaier, Thilo // IMRN: International Mathematics Research Notices;2005, Vol. 2005 Issue 58, p3625 

    We investigate a variant of Gromov's notion of asymptotic dimension that was introduced and named Nagata dimension by Assouad. This turns out to be a quasisymmetry invariant of metric spaces. The class of metric spaces with finite Nagata dimension includes doubling spaces, Gromov hyperbolic...

  • The interior proximal extragradient method for solving equilibrium problems. Thi Thu Van Nguyen; Strodiot, Jean-Jacques; Van Hien Nguyen // Journal of Global Optimization;Jun2009, Vol. 44 Issue 2, p175 

    In this article we present a new and efficient method for solving equilibrium problems on polyhedra. The method is based on an interior-quadratic proximal term which replaces the usual quadratic proximal term. This leads to an interior proximal type algorithm. Each iteration consists in a...

  • Local analysis of a polynomial system and its perturbations. Khodi-zade, P. // Differential Equations;Feb2008, Vol. 44 Issue 2, p286 

    On the real ( x, y)-plane, we consider an autonomous system of differential equations whose right-hand sides are polynomials of special form in x and y and a perturbed system obtained from the former by varying the coefficients in the class of functions of ( x, y) satisfying the Lipschitz...

  • Global optimization of expensive black box functions using potential Lipschitz constants and response surfaces. Liu, Haitao; Xu, Shengli; Ma, Ying; Wang, Xiaofang // Journal of Global Optimization;Oct2015, Vol. 63 Issue 2, p229 

    This article develops a novel global optimization algorithm using potential Lipschitz constants and response surfaces (PLRS) for computationally expensive black box functions. With the usage of the metamodeling techniques, PLRS proposes a new approximate function $${\hat{F}}$$ to describe the...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics