On number of samples needed

Question

Suppose we get $m+1$-bit signed noise samples $n_i$ with magnitude of noise as high as $m$ bits.

• Does averaging say $m\log m$ samples suffice to get average of $n_i$ to magnitude within few LSBs?
• How many samples do we need?

This is a purely theoretical question.

My noise samples are independent with magnitude uniformly distributed and sign equidistributed.

1. Assume magnitude of noise is uniform in range $(2^{m−1},2^{m}−1)$.
2. Also assume your working precision is very large say of $2^{2^{2^m}}$ bits so you never run into precision problems.

Answer 1

Look at the plot below. It generates noise according to the distribution you mentioned, and averages it (with different numbers of measurements). What is shown is the histogram of the obtained averaged noise values. As you can see, the more you average, the more the noise goes to the center. However, for $m \log m$ measurements, the noise has still significant contributions up to $2^{m-2}$, I dont know, if you would consider these the LSB. If you average more, you can get the gross of noise samples close to zero.

However, note that the minimum and maximum possible values of the averaged noise are still $\pm2^m-1$, which happens when all noise realizations are the maximum (which becomes more and more unlikely, when you have many measurements).

m = 16;
def getnoise(realizations, measurements):
    lowest = 2**(m-1)
    highest = 2**m - 1
    width = highest - lowest
    shape = (realizations, measurements)
    sign = (1-2*(np.random.randn(*shape)>0).astype(float))
    value = np.random.uniform(lowest, highest, size=shape)

    return sign * value

N = 10000
plt.hist(getnoise(realizations=N, measurements=1), bins=50, label='noise distribution');
plt.hist(np.mean(getnoise(realizations=N, measurements=2), axis=1), bins=50, label="2 average");
plt.hist(np.mean(getnoise(realizations=N, measurements=3), axis=1), bins=50, label="3 average");
plt.hist(np.mean(getnoise(realizations=N, measurements=int(m*np.log2(m))), axis=1), bins=50, label="mlogm average");
plt.hist(np.mean(getnoise(realizations=N, measurements=1000), axis=1), bins=50, label="1000 average");
plt.legend();

Some analytic result: Actually, the central limit theorem kicks in here. You have i.i.d. random variables of finite variance $\sigma^2=\frac{2}{3}(-1+2^m)^3$ (asking Mathematica):

Simplify[Integrate[x*x, {x, -(2^m - 1), 2^(m - 1)}] + 
  Integrate[x*x, {x, 2^(m - 1), 2^m - 1}]]

$=\frac{2}{3} \left(2^m-1\right)^3$

Hence, according to the central limit theorem, if you take the average of enough of those measurements, you will end up with a Gaussian distribution of variance

$$Var(\frac{1}{n}\sum_{i=0}^{n-1}X_i)\approx\frac{\sigma^2}{n},$$

So, with this result, you can calculate how much measurements you need, to get the required reduction in noise.