Eight processes writing to random memory blocks

Question

Eight independent processes each write to a memory block chosen uniformly at random from 64 blocks. What is the probability that at least two processes pick the same block?

Accepted Answer

Compute the safe case, all eight blocks distinct, and subtract from 1. Take the processes one at a time, each choosing a block not yet used: - Process 1: probability 64/64. - Process 2: avoids 1 used block, probability 63/64. - Process 3: avoids 2 used blocks, probability 62/64. - down to process 8, which avoids 7 used blocks, probability 57/64. Multiplying the eight factors: P(	ext{all distinct}) = \frac{64}{64}\cdot\frac{63}{64}\cdots\frac{57}{64} \approx 0.634. So P(	ext{at least two collide}) = 1 - 0.634 \approx 0.366, about 37\%. Even with eight writers into sixty-four slots, roughly a…

Eight processes writing to random memory blocks

Your answer

Discussion

Learn the concepts

Related questions