Expected-time asymptotics for binary border aggregation

Let

K$ be the depth parameter for the binary border aggregation model, let

\xi_K$ be the number of particles or the corresponding absorption time, and define

mK=2K2K+12log2K1log2+log2K42K.m_K=2^{K-\sqrt{2K}+\frac12\log_2K-\frac{1}{\log 2}+\frac{\log_2K}{4\sqrt{2K}}}.

Expected-time asymptotics conjecture. The expectation satisfies

EξK=mK(1+O(K1/2))=2K2K+12log2K1log2+log2K42K+O(K1/2).\mathbb E\xi_K=m_K\bigl(1+O(K^{-1/2})\bigr)=2^{K-\sqrt{2K}+\frac12\log_2K-\frac{1}{\log 2}+\frac{\log_2K}{4\sqrt{2K}}+O(K^{-1/2})}.

The paper proves only the cruder estimate EξK=(1+o(1))mK\mathbb E\xi_K=(1+o(1))m_K and explains that stronger tail estimates would be needed to establish this conjecture; it is left open.

Sources & referencesView supporting material

Primary source

Svante Janson and Debleena Thacker, “Continuous time digital search tree and a border aggregation model”, arXiv:2004.13957 (2020).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.