I generate $N$ independent uncorrelated random numbers, normally distributed with mean $\mu$ and variance $\sigma^2$ and place them into an array $a[i]; 1 \le i \le N$.

I then compute the sum $A = \sum_{i=1}^{N} a[i]$ of the array. Then $A \sim N(N \mu, N \sigma^2)$.

Now I copy the array $a$ to another array $t$ and select $k$ elements in $t$ at random, $1 < k < N$, and reverse the sign of those elements.

$t[i] = -a[i]$ if $i$ is one of the $k$ randomly selected elements.

$t[i] = a[i]$ otherwise.

Then I compute the sum $T = \sum_{i=1}^{N} t[i]$.

Fixing the original array $a$ and the number of elements $k$ to negate, I repeat many times the copying to $t$, each time selecting a new random $k$ elements to negate and summing to get a new $T$. My question is, what is the mean and variance of the series of $T$ values?

Numerical trials suggest the mean of $T$ is $N \mu (1 - 2k/N)$ which seems reasonable. What I'm hoping for is a formula for the variance of $T$ in terms of $A, k, N,\mu$ and $\sigma$.

The problem arises in my attempts to calculate the error rate of a binary linear block code. $N$ is the length of a codeword, $a[]$ is a received noisy all-zero codeword with $A$ as its log likelihood, and $k$ is the hamming weight of codewords which might be mistaken for the all-zero message if $T$ is large enough.

Ultimately what I need is P(T > A | a[], k) which is the probability that a codeword of weight $k$ will exceed the likelihood of the correct message (which has weight zero). I then have to integrate over the probability distribution of A and over the weight spectrum of my block code.

If I just assume $\operatorname{Var}(T) = \operatorname{Var}(A)$, I get a fairly weak upper bound on the code performance. For example predicting 74% error rate when the code actually achieves 57%. I seem to need roughly $\operatorname{Var}(T) \approx 0.9 \operatorname{Var}(A)$ to get good predictions when integrating over the weight spectrum.

I ran some numerical experiments. Each experiment begins by filling the array $a[]$ with random samples from $N(\mu,\sigma^2)$ and calculating the sum $A$. The experiment then makes $10^8$ trials in which $a[]$ is copied to $t[]$ and a randomly selected $k$ elements are negated in $t[]$. The experiment ends by logging $A$ and the mean and variance of the $10^8$ $T$ values. Fixing $N=352, \mu=1, \sigma=3.2$ the experiments span a range of $k$.

For $k=48$ a scatter plot of $\operatorname{Var}(T)$ against $A$, 160102k48.gif with one point per experiment. There seems to be no correlation with $A$ which simplifies things. For $k=48$ the average of $\operatorname{Var}(T)$ is 1706. ($\operatorname{Var}(A) = 3604.48$). Plotting the average of $\operatorname{Var}(T)$ for a range of $k$ gives 160102kp.gif. This nice curve is what I'm looking for a formula for. It seems that once $k \ge N/2$ the $\operatorname{Var}(T)$ is practically equal to $\operatorname{Var}(A)$. This is not so important, it is the lower values of $k$ (lower weight codewords) which are the more significant for code performance.

  • $\begingroup$ I tried to improve TeX code. However, do you mean $1 \le i \le N$ at the start and then $1 < k < N$ for the elements selected? $\endgroup$ – BruceET Jan 1 '16 at 23:35

Due to the observations being IID, it makes no difference which $k$ of the $N$ observations in the sample we negate. It suffices to assume that the first $k$ observations are negated. Then these first $k$ observations are each normally distributed with mean $-\mu$ and variance $\sigma^2$. Their sum is normal with mean $-k\mu$ and variance $k\sigma^2$.

Similarly, the remaining $N - k$ observations not negated have a sum that is normal with mean $(N-k)\mu$ and variance $(N-k)\sigma^2$.

Therefore, the resulting total sum is normal with mean $$-k\mu + (N-k)\mu = (N - 2k)\mu,$$ and variance equal to the sum of their component variances; i.e., $$\operatorname{Var}[T] = k\sigma^2 + (N-k)\sigma^2 = N\sigma^2.$$ This last property arises because although the sum of the first $k$ observations and the sum of the last $N-k$ observations are not identically distributed, they remain independent; therefore, the variance of their sum is equal to the sum of their variances. Throughout, we exploit the fact that the sum of independent normal variates is itself normal.

  • $\begingroup$ Note that I am filling $a[]$ just once from my iid source of noisy samples, then making observations of $T$ while $A, a[]$ and $k$ are fixed. If every trial selects the first $k$ to negate I will always get the same $T$ value. $\endgroup$ – Paul Jan 2 '16 at 5:04
  • $\begingroup$ @Paul Based on my understanding of the conditional probability you wish to calculate, I am not sure if the requested parameters for T will be sufficient for you to actually calculate what you want. The reason is that the conditional distribution of $T$ given the sample is not normally distributed. To see why, suppose $N = 2$ and the sample observed is $\boldsymbol a = (0,1)$. Then $T \mid \boldsymbol a, k$ isn't even continuous let alone normal. $\endgroup$ – heropup Jan 2 '16 at 17:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.