Random Feedback Shift Registers, and the Limit Distribution for Largest Cycle Lengths

Abstract

For a random binary noncoalescing feedback shift register of width $n$, with all $2^{2^{n-1}}$ possible feedback functions $f$ equally likely, the process of long cycle lengths, scaled by dividing by $N=2^n$, converges in distribution to the same Poisson-Dirichlet limit as holds for random permutations in ${\mathcal{S}}_N$, with all $N!$ possible permutations equally likely. Such behavior was conjectured by Golomb, Welch, and Goldstein in 1959.

42 pages; 21 references, 7 sections. The cover date, July 22 2022, is hard-wired. Revised proof for Lemma 3, and a few other minor changes