The Hamming weight of the non-adjacent-form under various input statistics (Q950295)

The Hamming weight of the integer \(\sum \varepsilon_j2^j\) with \(\varepsilon_j\in \{-1,0,+1\}\) is the number of non-zero \(\varepsilon'\)s. It is known that every integer admits a unique such representation satisfying \(\varepsilon_j\varepsilon_{j+1}=0\) for all \(j\), and that this representation minimizes the Hamming weight. It is also known that the expected weight of an integer \(< 2^n\) is \(\frac 13 n+O(1)\). In the paper under review the authors study the expected Hamming weight for integers satisfying certain properties. Two typical results are: let \(a_{k,n}\) be the normalized excepted Hamming weight for a nonnegative integer \(<2^n\) written as \(\sum\varepsilon_j 2^j\) \(\varepsilon_j \varepsilon_{j+1}=0\), and whose usual binary expansion has \(k\) nonzero digits. Then 1) if \(k\) and \(n\) tend to infinity with \(0<c\leq k/n\leq d<1\), then \[ a_{k,n}\sim\frac{1-4\big(\frac k n -\frac 12\big)^2}{3+4\big(\frac kn -\frac 12\big)^2} n\quad \text{uniformly}; \] 2) \ if \(k\) is fixed and \(n\) goes to infinity, then \[ a_{k,n}=k-\frac{k(k-1)(k-2)}{n^2}+O\left(\frac{1}{n^3}+\frac{1}{n^{k-1}}\right). \]