Can anyone provide me with a proof in probability. I am a bit rusty
with my probability terminology but I will try to describe the problem
as best I can.

I have n numbers between 0 and 1 (iid), lets call these bit error
rates, and I choose k of these (with repetition). So we have ber_1 ?
ber_k.
I take these k bit error rates and assume out of them the first m are
correct bits and the remaining k-m are incorrect. Next I make the
calculation of the probability of a correct decode by taking the
product of the ber_1 through ber_m and 1-ber_k-m to 1-ber_k.

I repeat these steps to compute a probability of correct decode but
with a new set of k bit error rates choosen from the n numbers. After
choosing all possible combinations with repetition and computing the
probability of a correct decode each time, I average all of them and
come up with an average probability of correct decode.

I need to prove that this average probability of correct decode is the
same as if I just averaged the n numbers to get a ber_avg and then
used (ber_avg)^m*(1-ber_avg)^(k-m) to compute the average probability
of correct decode.


For example for n = 5, k = 2, and m = 1
[.1 .2 .3 .4 .5] are the n bit errors rates
For each of the 10 permutations I make the computation
For example for ber_1, ber_2 = .1, .2 the successful decode
computation is .1*.8 =  .08
After going through all ten permutations, take the average and get .21
as the average prob of successful decode.

Now do the same with the mean of [.1 .2 .3 .4 .5], 0.3
.3*(1-.3) = .21

The results are the same..

I am offering a lot of money not because I think it is difficult, but
because I am not sure how do to the proof or whether this is a common
proof. I would like a mathematical proof with subsitution etc not just
a paragraph explanation. Please only answer if you can give a complete
proof (as I have already supplied a specific case of this working).
This is probably not a question you can google for either.

Hi twopair,

This one is not terribly hard to do, but a change of notation will help.

I'll use _ to indicate subscripting, as in (La)TeX style, so b_1 is a
b with a subscript 1, and so on. I'll also use sum(i=1..k, f(i)) for
summation (that is, the sum of f(i) as i goes from 1 to k).

Also, a couple of minor errors in your original question: in the
second paragraph you want ber_1 to ber_m and 1 - ber_m+1 to 1-ber_k.
In your example there are twenty-five combinations, not ten.

Now, for the solution. Let the bit error rates be B_1, ..., B_n and
select a particular combination by choosing i_1, ..., i_k from {1, 2,
..., n} - that is, choose i_1, ..., i_k to be the indexes into the
B's. Any particular combination of bit error rates is then just a
specific choice of i_1, ..., i_k.

The probability for the given combination defined by i_1, ..., i_k is

(B_i_1) (B_i_2) ... (B_i_m) (1 - B_i_m+1) (1 - B_i_m+2) ... (1 - B_k)

There are n^k possible choices for i_1, ..., i_k (since you're
choosing with repetition), and so the average probability will be

[sum(i_1=1..n, sum(i_2=1..n, ..., sum(i_k=1..n, 
  B_i_1 . ... B_i_m . (1 - B_i_m+1) ... (1 - B_i_k)))...)] / n^k

Now because this is a finite sum, and each index appears in only one
factor of the product, we can split this out for each index.

In other words, if we have sum(a=1..n, sum(b=1..n, f(a).g(b))) we can
rewrite this as sum(a=1..n, f(a)).sum(b=1..n, g(b)). Since only the
first factor depends on i_1, we can rewrite the whole sum as a sum
over i_1 multiplied by a sum over the remaining variables; and we can
repeat this process to get a whole lot of sums over one variable each.

At the same time, we can split up the denominator n^k to assign one
factor of n in the denominator for each sum.

So we wind up with 

[sum(i_1=1..n, B_i_1) / n] . [sum(i_2=1..n, B_i_2) / n] . ...
[sum(i_m=1..n, B_i_m) / n] . [sum(i_m+1=1..n, (1 - B_i_m+1)) / n] . ...
[sum(i_k=1..n, (1 - B_i_k)) / n]

Now the first m sums are the same and the last k-m sums are also the
same. So we have

[sum(i=1..n, B_i) / n]^m . [sum(j=1..n, (1-B_j)) / n]^(k-m)

So if we let B be the average of the B_i, i.e. B = sum(i=1..n, B_i) /
n, then we get (noting also that 1 - B is the average of the (1 -
B_i))

B^m . (1-B)^(k-m)

which is what you want.

Cheers, manuka-ga

Oh thanks!! you rule, i read googles policy and they don't pay
registered users only researchers! that's weird. i am going to cancel
this question before a researcher takes your answer and pastes it as
their own. thanks again!! yay