The Setting
Take two points and of the complex plane and look for the smallest square holding both in a random hierarchy of dyadic squares. For every integer a grid of squares of side is shifted at random, and before the grids are laid down the plane is turned by a uniform angle and contracted by , with a uniform phase . Minus the logarithm of the side of that smallest square, measured in the original plane, is the depth of the pair, a hierarchical counterpart of .
The library builds the random shifts from independent increments, defines the depth , its grid error and the mean of that error, and states two almost sure facts about the squares and the depth.
Shifted Dyadic Grids
For a real , the uniform law on is the probability measure obtained from Lebesgue measure restricted to that interval by dividing by , and the fair step of size is the law on giving each of and probability .✦ The axis law is the law of a real sequence with independent terms, uniform on and a fair step of size for : (1)✦ At a level , the offset of such a sequence is the partial sum (2)✦ A grid sample is a pair of real sequences, for the first axis and for the second✦, and the grid law makes the two sequences independent, each with the axis law: (3)✦
On a line, the grid of side and offset cuts into the intervals , , and a real lies in the one of index .✦ Two points and of share level under , written , when they lie in one square of the grid of side with offsets and : The shared level of and under is the least level at which they share a square: (5)✦
Rotation and Phase
The phase law is the law of a pair of independent reals, the phase uniform on and the angle uniform on .✦ A full sample is a triple of a phase, an angle and a grid sample✦, and its law is (6)✦ The rotation of phase and angle is the map from to sending to the real and imaginary parts of : (7)✦
The Claim
Definition 1. Let be a grid sample and points of . The grid depth of and is (8)✦ Let be a full sample and points of . The depth is the grid depth of the rotated points less the phase, and the grid error is the excess of the depth over the raw depth : (9)✦ (10)✦ For reals and , the polar mean is the expected grid depth of the origin and the point , plus , and the mean error is the average of over the phase and the angle: (11)✦ (12)✦
In the paper, the setting reads: a random orientation, a logarithmic phase uniform on and nested shifted square grids of side , with being minus the logarithm of the smallest side shared by and and , where and are vertices, is the -th coordinate of a vertex as a complex number and indexes these coordinates, and , and the raw depth are the page’s , and at and .
Theorem 1. Let be an integer and points of . For -almost every grid sample , sharing level implies sharing level : (13)✦ Let be pairwise distinct points of . For -almost every full sample, the depth satisfies the ultrametric inequality (14)✦
What Is Checked
The definitions and the theorem are stated over points of for the grids and of for the depth, under the grid law on pairs of real sequences and the full law on phases, angles and grid samples, both built from uniform laws and fair steps.