11 - Pseudo-randomness of a random Kronecker sequence. An instance of dynamical analysis

Summary

Introduction

A measure of randomness on the unit interval ℐ := [0,1] tests how a sequence X ⊂ℐ differs from a ‘truly random’ sequence. See books (Drmota and Tichy, 1997; Kuipers and Niederreiter, 1974) for a general discussion on the subject. Such a measure describes the difference between the behaviour of the truncated sequence X_⟨T⟩ formed with the first T terms of the sequence and a ‘truly random’ sequence formed with T elements of ℐ, and explains what happens when the truncation T becomes large.

Here, we focus on the case of the Kronecker sequence K (α), formed of the fractional parts of the multiples of a real α. The three-distance theorem states that there are at most three possible distinct distances between geometric consecutive points in the truncated sequence K_⟨T⟩(α). For some values of T, only two distances occur (we refer to this situation as the two-distance phenomenon below). The length and the exact number of these distinct distances depend on the continued fraction expansion of the real α. Such a sequence K(α) is thus very particular, and is surely not pseudo-random at all. On the other hand, it can be precisely studied since its main parameters are expressed as a function of the continued fraction expansion of the real α. This explains why there are many existing works that deal with various randomness measures of the Kronecker sequence, notably the discrepancy. However, they all adopt an ‘individual’ point of view: for which reals α, and for which integers T, the discrepancy of the sequence K (α) is minimal, maximal?

Our points of view

Here, we adopt different points of view, which appear to be new.

1. (1) We focus on the special case when the truncation T gives rise to the two-distance phenomenon: the computations are easier, but already show very interesting phenomena. In particular, we introduce two different types of truncation (see Section 11.2.2), which depend on the position μ ∈ [0,1] of the truncation: the boundary positions which correspond to μ = 0 or μ = 1, and the generic positions, with μ ∈]0,1[and we describe how they lead to different probabilistic behaviours.

2. […]