Expected-time asymptotics for binary border aggregation

About 6 years old · traced to

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=2K−2K+12log⁡2K−1log⁡2+log⁡2K42K.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(K−1/2))=2K−2K+12log⁡2K−1log⁡2+log⁡2K42K+O(K−1/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.

References

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.