On the distribution of runs of ones in binary strings

In this paper, we derive the number of binary strings which contain, for a given ik, exactly ik runs of 1ʹs of length k in all possible binary strings of length n, 1 k n. Such a knowledge about the distribution pattern of runs of 1ʹs in binary strings is useful in many engineering applications for example, data compression, bus encoding techniques to reduce crosstalk in VLSI chip design, computer arithmetic using redundant binary number system and design of energy-efficient communication schemes in wireless sensor networks by transformation of runs of 1ʹs into compressed information patterns, among others. We present, here, a generating function based approach to derive a solution to this counting problem. Our experimental results demonstrate that, for most commonly used file formats, the observed distributions of exactly ik runs of length k, 1 k n, closely follow the theoretically derived distributions, for a given n. For n D 8, we find that the experimentally obtained values for most file formats agree within 5% of the theoretically obtained values for all ik runs of length k, 1 k n. Also, the root mean square (RMS) values of these deviations across all file types studied in this paper are less than 5% for n D 8. In view of these facts, the results presented in this paper could be useful in various application domains, like the ones mentioned above.