Some Questions — Question 48

Definitions and mathematical statement

Let $(\xi_m)_{m\in\mathbb Z}$ and $(\eta_m)_{m\in\mathbb Z}$ be independent families of independent Bernoulli random variables, each taking zero and one with probability $1/2$. Define the random sets \[ A=\{m:\xi_m=1\},\qquad B=\{m:\eta_m=1\}. \] Give both sets the metric inherited from $\mathbb Z$, so $d(a,a')=|a-a'|$, rather than the path metric of the possibly disconnected induced graph.

Are $A$ and $B$ almost surely quasi-isometric? Explicitly, with probability one, do there exist a map $f:A\to B$ and constants $L\geq1$, $C\geq0$ such that \[ L^{-1}|a-a'|-C\leq |f(a)-f(a')|\leq L|a-a'|+C \] for all $a,a'\in A$, and every $b\in B$ has distance at most $C$ from $f(A)$?

The map and constants may depend on the two realized sets. The source does not require the map to be order-preserving, bijective, translation-equivariant or measurably selected as a function of the samples. Those additional constraints give different questions. Both random subsets are unbounded in both directions almost surely, but their random gaps have no deterministic upper bound. The same problem can be posed for independent Bernoulli subsets of other Cayley graphs, in particular a Cayley graph of $\operatorname{SL}_3(\mathbb Z)$, using their inherited word metrics.

Short English statement

Are two independent random subsets of the integers almost surely equivalent at large scales?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 1200048 (AMR-011-0048), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Abert - Some questions (pdf) (2010), Question 48. Original source indexed by AMR-011-0048. https://www.renyi.hu/~abert/questions.pdf.