What is the possibility that some of top numbers are missing in a non-exact distributed largest N algorithm? I have a classical programing problem at hand and although I know the exact solution, but my math knowledge failed short when I tried to reason further, and I really hope somebody here can shed some light so I know where I can start from.
Suppose I have a million numbers, and I want to find the largest 100 numbers among them.  The classical distributed sorting algorithm will be something like the following: find 10 machines, and split the million numbers evenly into 10 shards, so that each machine takes one shard and find out the largest 100 numbers in its own shard, then we combine the largest 100 numbers from each shard (in total we have 10 * 100 = 1000) and again find the largest 100 numbers from the combined result above.
The above solution is exact, meaning that however badly the numbers are distributed among the 10 shards (for example, even all the 100 largest numbers are in the same shard), we will still be able to find all of them.  But, in reality, intuitively,  the chance of this extreme situation is very small as number of shards increase (Suppose 1 million number split into 1000 shards, all the top 100 numbers are very unlikely in the same shard!), so I guess I can collect fewer numbers than the final required number from each shard (say, collect 50 from each shard), and I still have a good chance to get the final top 100 numbers right, but I don't know how to estimate the probability that some of the top 100 numbers will be missing based on the choice (say, the total number 1M, the final required number 100, number of shards 10, number to collect in each shard is 50, etc. Suppose numbers are randomly assigned to shards, what is the probability that one top 100 number is missing from the final result? How about 2 numbers missing?).
I vaguely guess the estimation has something to do with statistics, but I could not find a way to apply my preliminary statistics knowledge (such as normal distribution, bayesian conditional probability, etc.) to the problem. I also tried combinatorics but still could not work it out. I guess there is actually another sub-field math specifically targets problems like this (Stochastic Processes maybe?), but I never took class in that area.  Could somebody here shed some light on the right approach to estimate the probability? Such as recommending a math book suitable for undergraduates, and after read this book, I will learn a systematically approach to solve this problem is also fine.
 A: I’ll assume that all possible distributions of the numbers over the shards are equiprobable.
Let $n=1000000$ denote the total number of numbers, $m=100$ the number of numbers sought, $s=10$ the number of shards and $k=50$ the number of numbers to collect in each shard. In this example $m\le2k$, which simplifies things quite considerably: We miss numbers by having more than $k$ of the numbers we seek assigned to the same shard, and if $m\le2k$ this can’t happen for more than one shard. Since you say that it’s already quite unlikely to happen for one shard, we can neglect the probability that it happens in more than one shard simultaneously even for $m\gt2k$.
Then the $s$ events that a particular one of the shards is assigned more than $k$ of the numbers are disjoint, and the probability that one of them occurs is just $s$ times the probability that a particular one of them occurs. You miss exactly $j$ of the numbers if $k+j$ of them are assigned to the same shard, that is, if you pick $k+j$ numbers for the shard out of the $m$ numbers sought and the remaining $\frac ns-(k+j)$ numbers for the shard out of the remaining $n-m$ numbers. Thus, the probability to miss $j$ numbers is
$$
s\cdot\frac{\binom m{k+j}\binom{n-m}{n/s-(k+j)}}{\binom n{n/s}}\;.
$$
In your example, this is
$$
10\cdot\frac{\binom{100}{50+j}\binom{1000000-100}{1000000/10-(50+j)}}{\binom {1000000}{1000000/10}}=10\cdot\frac{\binom{100}{50+j}\binom{999900}{99950-j}}{\binom {1000000}{100000}}\;.
$$
This is already only about $5.6\cdot10^{-24}$ for $j=1$, and it decreases by roughly a factor of $10$ when you increment $j$.
