Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

(Probability Question)

I have a number of $N$ types of gems that I have handed out to $M$ people, using some random probability function for each person. Thus: $$ \begin{align} P_1^1 + P_2^1 + P_3^1 + P_4^1 + \dotsb + P_n^1 &= 1 \\ P_1^2 + P_2^2 + P_3^2 + P_4^2 + \dotsb + P_n^2 &= 1 \\ P_1^3 + P_2^3 + P_3^3 + P_4^3 + \dotsb + P_n^3 &= 1 \\ P_1^4 + P_2^4 + P_3^4 + P_4^4 + \dotsb + P_n^4 &= 1 \\ P_1^5 + P_2^5 + P_3^5 + P_4^5 + \dotsb + P_n^5 &= 1 \\ \vdots & \\ P_1^m + P_2^m + P_3^m + P_4^m + \dotsb + P_n^m &= 1 \end{align} $$

Thus, each person has a type of gem with a certain probability (each person can only have one type of gem).

An example for $N = 3$ , $M = 3$ would be (each row is a different person, each column a gem of type different type):

$0.3 ~0.5~ 0.2$
$0.8 ~0.1~ 0.1$
$0.4 ~0.3~ 0.3$

Is there a way of finding out the probability of at least one person having a gem of type $n$, at least one person having a gem of type $n-1$, but none having one of $n$, at least one person having a gem of type $n-2$, but none having a gem of type $(n-1)$ and $n$ etc., without enumerating all the joint probabilities ($N^M$ possible combinations) ?

share|cite|improve this question
up vote 1 down vote accepted

To answer whether at least one person has a gem of type $n$, just take the product of probabilities that each person does not choose type $n$. Then one minus that product is your answer.

For example, in your matrix above it's $1- 0.8 \times 0.9 \times 0.7 = 0.496$.

Now that you have this, you can leverage it to answer the next question you posed: there is a $0.504$ probability that no one had a type $n$ gem, so take the products over the sums of each $n-2$ entries from each row and compute $0.504$ minus this product. Etc.

If you're shooting for algorithmic efficiency, you can avoid having to recompute the sums and full products each time by tabulating values you know you'll need later when you first compute them to obtain the initial answer above. Leave a comment if you're not clear how to do this and I can elaborate. If you do it right, the resulting algorithm should be $O(MN)$.

share|cite|improve this answer
Hello, I don't think I understand how the second part of the answer works, I wonder if you can elaborate a bit (thanks) – Bob Jun 1 '11 at 8:54

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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