The height of symmetric digital search trees: two-point concentration and the law of the height

For each integer b ≥ 2, let H_n be the height of the symmetric b-ary digital search tree on n independent uniform keys, and e_D(n) the expected number of depth-D nodes. We prove Pr (H_n < D) = exp (−e_D(n)) + o_b(1) uniformly in integers D > log_b n. Thus H_n concentrates on two consecutive values with explicit probabilities. Almost surely, for every s > 0, eventually −1 − s < H_n − ν_b(n) < s, where ν_b(n), the last unit crossing of the interpolated profile, is expanded to O_b((log n)^(−1/2)); H_n − ν_b(n) has bounded absolute moments. In border aggregation on a complete height-K b-ary tree, ξ_K particles make the root sticky, with log_b ξ_K = K − √(2K) + (1/2)log_b K + O_p(1) and a Gumbel-type limit law after normalisation. These results transfer to the longest Lempel–Ziv phrase. MSC 2020: Primary 60C05; Secondary 05C05, 60F05, 60F15, 68P05, 68P30, 68Q87. The accompanying files contain the manuscript, its LaTeX source, and the programs and numerical data for the exact distributions, expected profiles, interval certificates, and simulations.