Q.7.17 - A First Course in Probability

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 $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.

Step-by-Step Solution

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 1:Concept Introduction

Given that 

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

$=0$ otherwise

$X=Total number of collisions$

$=\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$

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

$=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$