Question

A total of$m$items are to be sequentially distributed among $n$cells, with each item independently being put in a cell $j$with probability role="math" localid="1647437056272" $pj,j=1,...,n$. Find the expected number of collisions that occur, where a collision occurs whenever an item is put into a non-empty cell.

Short answer

The expected number of collisions that occur, where a collision occurs whenever an item is put into a non-empty cell,

$\mathrm{E}\left[\mathrm{X}\right]=m-n+\sum _{j=1}^n {\left(1-p_j\right)}^m$

Step-by-step solution

Step 1:Concept Introduction

Given that

$X_i=1$if a collision occurs when the item is placed

$=0$otherwise

$X=Totalnumberofcollisions$

$=\sum _{i=1}^m {\mathrm{X}}_i$

$\Rightarrow \mathrm{E}\left[\mathrm{X}\right]=\sum _{\mathrm{i}=1}^{\mathrm{m}} \mathrm{E}\left[{\mathrm{X}}_{\mathrm{i}}\right]$

Step 2:Explanation

Molding on the cell in which it is set.

$E\left[X_i\right]=\sum _j^{} E\left[X_i\mid \text{placed in cell}j\right]p_j$

$=\sum _j E[\mathrm{i}\text{causes collision}\mid \text{Placed in cell}\mathrm{j}]p_j$

localid="1647435990293" $=\sum _j^{} \left[1-{\left(1-p_j\right)}^{i-1}\right]p_j$

localid="1647436010058" $=1-\sum _j^{} {\left(1-p_j\right)}^{i-1}{p}_j$

Step 3:Final Answer

The close to last uniformity utilized that, restrictive on the item$i$being set in the cell$j$, item$i$ will cause a collision if any of the previous$(i-1)$ items were placed in a cell$\mathrm{j}$, Thus,

$\mathrm{E}\left[\mathrm{X}\right]=\mathrm{m}-\sum _{i=1}^m \sum _{j=1}^n {\left(1-p_j\right)}^{i-1}{p}_j$

Exchanging the request for the summation gives

$\mathrm{E}\left[\mathrm{X}\right]=m-n+\sum _{j=1}^n {\left(1-p_j\right)}^m$