2
$\begingroup$

Let:
\begin{align*} &i = 1,...,m \quad \textrm{(index $i$ represent customers)} \\ &j = 1,...,n \quad \textrm{(index $j$ represent facilities)} \\ &y_{ij} = \dfrac{1}{n},\,\forall i,j \quad \textrm{represent the probability that customer $i$ chooses facility $j$} \\ \end{align*}

Each customer chooses 1 and only 1 facility independent of other customers. So here are a few questions that I couldn't solve:

$$P(\textrm{at least 1 facility gets no customer})\,=\,?$$ $$P(\textrm{1 and only 1 facility gets no customer})\,=\,?$$

Here is an attempt to solve the first problem:
$$P(\textrm{at least 1 facility gets no customer})=1-P(\textrm{all facilities get at least 1 customer})$$ It likely requires some sort of combinatoric analysis involving partitioning of the customers (elements) into facilities (buckets) but I don't think it is a trivial counting problem since all such partitions are not going to be equally likely to occur. I don't even know where to begin with in the first place, so any help would be much appreciated!

Edit 1:
With the help of Jimmy R., I found answer of the first question to be $1-\frac{\binom{m}{n}.n!.n^{m-n}}{n^m}$ and answer of the second question to be (both different from my comment below) $\frac{\binom{n}{1}.\binom{m}{n-1}.(n-1)!.(n-1)^{m-(n-1)}}{n^m}$ .

$\endgroup$
1
$\begingroup$

Hints: I assume that $m>n$, otherwise the problems are trivial. To tackle the first, think as follows: First assign one customer to each facility. So, "all facilities get at least 1 customer". Now, you need to distribute the $m-n$ remaining customers randomly to the $m$ facilities.

To tackle the second: just exclude one facility. You can do this in $n$ ways. Now, distribute all $m$ customers among the remaining $n-1$ facility, as if this one never existed.

$\endgroup$
  • $\begingroup$ Thanks for the hint! So answer of the first question would be $1-\binom{m}{n}.\left(\frac{1}{n}\right)^n.\left(\frac{n-1}{n}\right)^{m-n}$ and answer of the second question would be $\binom{n}{1}.\left(\frac{n-1}{n}\right)^m$ . Am I right? $\endgroup$ – deniz Oct 21 '17 at 12:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.