[mnet-devel] analytical solution to the FEC reliability problem

[Zooko]

(Thanks to my combinatorics consultant, Amber, who explained this to me once 
again.)

Suppose there are M shares, and you need to recover any K of them in order to 
win.

Let's denote the probability that you win as "W".  

W = P(recover K shares) + P(recover K + 1 shares) + P(recover K + 2 shares) + 
   ... + P(recover all M shares)

So what's the probability that you recover exactly K shares?  Well, there are 
Choose(K, M) different combinations with which you can recover exactly K shares. 
The probability of recovering exactly K shares is equal to:

P(recovering exactly K shares in the first combination) +
P(recovering exactly K shares in the second combination) +
...
P(recovering exactly K shares in the last combination)

What's the probability of recovering exactly K shares in exactly one 
combination?  It's the probability that the K shares specified by this 
combination are recovered, *and* the M-K shares *not* specified by this 
combination are *not* recovered: P(S)^K * (1-P(S))^(K-M).

Since each of these terms that say "P(recovering exactly K shares in the Nth 
combination)" are disjoint, we add them together to get the probability of 
recovering exactly K shares in any combination.  Since they all have the same 
probability, adding them all together is the same as multiplying that 
probability by the number of them.  Therefore:

P(recover exactly K shares) = Choose(M, K) * P(S)^K * (1-P(S))^(K-M)

Now, don't forget to get the probability of recovering at *least* K shares, you 
have to add up P(recover exactly I shares) for all I from K to M.

That's it.

Regards,

Zooko



-------------------------------------------------------
This sf.net email is sponsored by:ThinkGeek
Welcome to geek heaven.
http://thinkgeek.com/sf
_______________________________________________
mnet-devel mailing list
mnet-devel at lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/mnet-devel