The Setting
Take a walk of Gaussian integers with steps at most , observed at a random time reached from a starting time by a run of random advances, each read off from the differences of a stretch of the walk, and a final uniform offset. The question is how far past the start can lie, and what the displacement of the walk over that stretch costs in entropy. When the final offset is uniform on , a second question is how much a further shift by steps can change the probability of an event, or a conditional entropy, observed at that time.
Laws and Entropy
A finite probability law on a finite set is a function with for every and . The probability of a property of the points of is the total mass of the points where it holds.✦ The uniform law on a nonempty finite set gives every element of the mass ; write for the uniform law on .✦
The pushforward of along a map from to a finite set is the finite probability law on that gives each point the mass of its preimage; for a random variable on , the law of is . Given a finite probability law on a finite set and, for each , a finite probability law on , the joint law is the finite probability law on with mass at , the law of a pair drawn by taking from and then from .✦
The entropy of a finite probability law on a finite set is the Shannon sum (1)✦ with . For random variables and on with values in finite sets and , the entropy is the entropy of the law of ✦, and the conditional entropy of given is (2)✦ where is the entropy of the pair .
Forward Kernels and the Common Schedule
A forward kernel consists of a natural number , its bound, and for every time a finite probability law on , the law of the advance taken from time . The composite of forward kernels and is the forward kernel of bound whose law at time is that of the sum of offsets , with drawn from and then from : (3)✦ The smoothing kernel of window is the forward kernel of bound whose law at every time is .✦
Let be a walk of Gaussian integers and . The walk segment is the set of points the walk visits up to time . The difference set of a finite set of Gaussian integers is the set of all differences with .✦ The difference representative of an element of is a pair of times in with , chosen once and for all✦, and the difference law of over steps is the finite probability law on such pairs obtained by drawing uniformly from and returning its representative.✦
The difference kernel of with window is the forward kernel of bound whose law at time is that of the following advance: toss a fair coin, draw from the difference law of the shifted walk over steps, and advance by on heads and by on tails.✦ Given segment lengths and an offset window , the common schedule of is the forward kernel (4)✦ of difference transitions followed by a uniform offset. The terminal time of the common schedule of started at time is , where is the advance drawn from the law of the schedule at .
The Claim
Theorem 1. Let be a walk of Gaussian integers, let and be natural numbers, and let be the bound of the common schedule of with segment lengths and offset window . Then (5)✦ If moreover is a real number with for every , and , then (6)✦
Let , , and be real numbers and and natural numbers, with , , , , and . Then (7)✦
Let be a finite probability law on a finite set , a random time, and natural numbers. Draw from , so that the offset is uniform on and independent of , and put ; probabilities and entropies are taken under this law. For every set of natural numbers, (8)✦ and for all sequences and with values in finite sets and , (9)✦ where is the binary entropy.
In the paper, the result reads: for a scheduled scale in a band with parameter and all sufficiently large , the total forward shift from the checkpoint before to any later checkpoint is at most a deterministic with , so that its displacement has entropy , and from any earlier exact start the total variation distance between the laws of and is at most for all integers .
In the library, the bound of (5) plays the part of , and the smoothing inequalities (8) and (9) stand in place of the total variation bound.
What Is Checked
The claim is stated over the common schedule (4) of a walk of Gaussian integers, composed by (3) from the smoothing kernel and from difference kernels built on the difference law of a walk segment and its difference set; and over the joint law of a finite probability law and the uniform law on offsets, with the probability of an event and the conditional entropy (2) taken under it. About these constructions the library proves that every difference of a walk segment is realised by a pair of times: for each there are with .✦