4
$\begingroup$

(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) ?

1 Answers 1

1

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

  • 0
    Hello, I don't think I understand how the second part of the answer works, I wonder if you can elaborate a bit (thanks)2011-06-01