$n$ users placed in cells randomly and independently and figure out the expected value

59 Views Asked by At

Suppose $n$ users placed in $m$ cells randomly and independently. Let $i$ belongs from $1$ to $n$, and each user $i$ wants to get file $f_i$. Now suppose each different users independently has file $f_i$ with probability $p$. Then how do I figure out the expected value of the number of cells that have at least one user who has the file desired by other user in the same cell?

I am confused on how to model the problem since there are too many variables here.

1

There are 1 best solutions below

0
On

I interpret the question to mean that different users want different files, where user $i$ wants file $f_i$, and that there is a fixed probability $p$ such that for each pair of user $i$ and file $f_j$ with $i\ne j$ there is an independent probability $p$ of that user having that file, with zero probability of user $i$ having their own file $f_i$.

In this case, a cell with $k$ users has probability $1-(1-p)^{k(k-1)}$ of having a matching user and file, so the expected number of such cells is

$$ m\sum_{k=0}^n\binom nk\left(\frac1m\right)^k\left(1-\frac1m\right)^{n-k}\left(1-(1-p)^{k(k-1)}\right)\\ =m\left(1-\frac1m\right)^n\sum_{k=0}^n\binom nk(m-1)^{-k}\left(1-(1-p)^{k(k-1)}\right)\;. $$