On the Spread of Random Interleaver

Abstract

For a given blocklength we determine the number of interleavers which have spread equal to two. Using this, we find out the probability that a randomly chosen interleaver has spread two. We show that as blocklength increases, this probability increases but very quickly converges to the value $1-e^{-2}\approx 0.8647$. Subsequently, we determine a lower bound on the probability of an interleaver having spread at least $s$. We show that this lower bound converges to the value $e^{-2(s-2{)}^2}$, as the blocklength increases.

5 pages, published in Proceedings of IEEE International Symposium on Information Theory 2005, Adelaide, Australia