Generating Non-negative Matrices with Specified Row and Column Sums
Daniel Grier · 2015
The topic announced in the title is a spinoff of a problem recently solved, more or less, in (Foster and Johnson, 2012): Given an alphabet S = {s1, . . . , sm}, an integer k > 1, and a k-dimensional array [ f ] = [ f (i1, . . . , ik); 1 ≤ i1, . . . , ik ≤ m] of non-negative numbers, under what conditions on the array does there exist a “statistically stable source” producing text over S (a hypothetically endless stream of letters in S ) such that whenever 1 ≤ i1, . . . , ik ≤ m, f (i1, . . . , ik) is the relative frequency of si1 . . . sik among blocks of k consecutive letters in the source text; in other words, f (i1, . . . , ik) is the probability that a block of k consecutive letters chosen at random from the source text will be si1 . . . sik . From elementary probability comes a necessary condition on [ f ] for the existence of such a source, sometimes called the consistency condition: for any i1, . . . , ik−1 ∈ {1, . . . ,m},