On the possible patterns of inputs for block sorting in the Burrows–Wheeler transformation

Block sorting in the Burrows–Wheeler transformation is to sort all of the n circular shifts of a string of length n lexicographically. We introduce a notion called the width of a sequence of n strings of length n and show that the values of widths are very different between the two types of sequences of strings; (1) a sequence of n randomly generated strings of length n, and (2) the sequence of n circular shifts of a randomly generated string of length n.

► We compare patterns of two types of sequences of n strings of length n.
► A first type sequence is a sequence of n independent random strings.
► A second type sequence is the sequence of n circular shifts of one random string.
► We define a notion called the “width” of a sequence of n strings of length n.
► Second type sequences have smaller widths than first type sequences.