matrices with entries being zero or one and the number of changes, i.e., the number of (horizontally or vertically) adjacent
entries which are different. We extend these results in many ways. For instance, we exhibit that the limiting distribution
is Gaussian and get explicit formul for some moments even in the general instance of d dimensions (instead of just two).
The Hamming weight of the non-adjacent form is studied in relation to the Hamming weight of the standard binary expansion.
In particular, we investigate the expected Hamming weight of the NAF of an n-digit binary expansion with k ones where k is either fixed or proportional to n. The expected Hamming weight of NAFs of binary expansions with large (≥ n/2) Hamming weight is studied. Finally, the covariance of the Hamming weights of the binary expansion and the NAF is computed.
Asymptotically, these Hamming weights become independent and normally distributed.
Authors:Guy Louchard, Helmut Prodinger and Mark Ward
This paper complements the analysis of Louchard and Prodinger [LP08] on the number of rounds in a coin-flipping selection algorithm that occurs in the presence of a demon. We precisely analyze a very different aspect
of the selection algorithm, using different methods of analysis. Specifically, we obtain precise descriptions of the distribution
and all moments of the number of participants ultimately selected during the execution of the algorithm. The selection algorithm is robust in at least two significant
ways. The presence of a demon allows for the precise analysis even when errors may occur between the rounds of the selection
process. (The analysis also handles the more traditional case, in which no demon is involved.) The selection algorithm can
also use either biased or unbiased coins.