Welcome to the resource topic for 2009/047
Title:
On Approximating Addition by Exclusive OR
Authors: Palash Sarkar
Abstract:Let X^{(1)},X^{(2)},\ldots,X^{(n)} be independent and uniformly distributed over the non-negative integers \{0,1,\ldots,2^i-1\}; S^{(n)}=X^{(1)}+X^{(2)}+\cdots+X^{(n)} and L^{(n)}=X^{(1)}\oplus X^{(2)}\oplus \cdots\oplus X^{(n)}. Denote the i-th bits of S^{(n)} and L^{(n)} by S^{(n)}_i and L^{(n)}_i respectively. We show that as i\rightarrow \infty, \pr[S^{(n)}_i=L^{(n)}_i]\rightarrow \gamma^{(n)}= \frac{1}{2}+\frac{2^{n+1}(2^{n+1}-1)}{2(n+1)}\times\frac{b_{n+1}}{n!}, where b_n is the n-th Bernoulli number. As a consequence, \gamma^{(2r)}=1/2 for every r; and we show that \gamma^{(2r+1)}\rightarrow 1/2 as r\rightarrow \infty. For small values of r, \gamma^{(2r+1)} is significantly different from 1/2; for example \gamma^{(3)}=1/3 and \gamma^{(5)}=17/30. The behaviour of \gamma^{(n)} for even and odd values of n was earlier shown by Staffelbach and Meier without actually obtaining the formula mentioned above. For every fixed n\geq 2, we give a simple method for computing \pr[S^{(n)}_i=L^{(n)}_i] for each i\geq 0. The expression involving Bernoulli numbers is arrived at via the Eulerian number triangle which in turn arises in relation to the stationary distribution of a Markov chain formed by the carry values.
ePrint: https://eprint.iacr.org/2009/047
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .