Average number of pigeon holes.

Question

I'm an engineer not a mathematician, and I have a 3 part question that's applicable to a parallel computer system my team is designing.

We have 10 CPU cores (ie - 10 pigeons) randomly reading from 10 disks (ie - 10 holes).

Part 1) On average, how many disks are idle?

Part 2) Let's say each core is reading 100MB, and each disk can read at a rate of 100 MB/sec, so ideally if all 10 disks happen to be used, all reads are done after 1 sec. However, if all cores happen to hit the same disk, then all reads will be done after 10 sec. On average, how long will it take for all reads to finish?

Part 3) What's the standard deviation in the time completion of a read operation?

Many thanks!

Jeff

Answer 1

A start: Number the disks from $1$ to $10$. Let $X_i=1$ if disk $i$ is idle, and $0$ otherwise.

Then the random variable $X_1+\cdots+X_{10}$ is the number of idle disks.

By the linearity of expectation, we have $E(X_1+\cdots+X_{10})=E(X_1)+\cdots+E(X_{10})$.

To calculate $E(X_i)$, calculate the probability disk $i$ is idle. This is the probability everybody chooses another disk, which is $\left(\frac{9}{10}\right)^{10}$.

Thus the expected number of idle disks is $10 \left(\frac{9}{10}\right)^{10}$.