# What is the probability of having the same numbers in two sets

• Jan 22nd 2013, 10:51 AM
ajlakanen
What is the probability of having the same numbers in two sets
Hello,

let's assume we draw a set of four numbers, each of which can be 1, 2 or 3.

Then we draw a set of two numbers, each can be 1, 2 or 3.

Now, what is the probability that both numbers of the latter set exist in the first set?

Example 1: first set is {3, 1, 1, 2}, second {1, 2} ==> OK (both 1 and 2 are in the first set)

Example 2: first set is {3, 1, 1, 2}, second {2, 2} ==> Not OK (theres only one pieces of 2's in the first set, not two).

Cheers,
Antti-Jussi
• Jan 22nd 2013, 06:24 PM
kylehk
Re: What is the probability of having the same numbers in two sets
Quote:

Originally Posted by ajlakanen
Hello,

let's assume we draw a set of four numbers, each of which can be 1, 2 or 3.

Then we draw a set of two numbers, each can be 1, 2 or 3.

Now, what is the probability that both numbers of the latter set exist in the first set?

Example 1: first set is {3, 1, 1, 2}, second {1, 2} ==> OK (both 1 and 2 are in the first set)

Example 2: first set is {3, 1, 1, 2}, second {2, 2} ==> Not OK (theres only one pieces of 2's in the first set, not two).

Cheers,
Antti-Jussi

Hi Antti-Jussi,

Your description is clear enough for us to understand. Here are some thoughts on your q

We could start from finding the probability P' of a number of the latter set NOT in the first set. Then the probability of it in the first set is 1-P'.

Below's a possible way to find P':
1. Let s1 and s2 represent the first and second item in the latter set. Either of s1 and s2 could be 1, 2, or 3 with probability of 1/3. For example, s1 = 1 is with probability 1/3 since s1 is randomly chosen from three numbers.

2. Now let's consider a specific case, say when s1 = 1 AND s1 is NOT in the first set. In this case, all items of the first set should be chosen from the other two numbers 2 and 3 (right?). Since there are totally three choices (i.e., 1, 2, 3) but only two (i.e., 2 ,3) are feasible, the probability for s1 = 1 NOT in the first set should be $\displaystyle \frac{2}{3} \times \frac{2}{3} \times \frac{2}{3} \times \frac{2}{3}$.

3. Step 2 considers one specific case (s1 = 1) out of three possible cases (i.e., s1 = 1, 2, or 3). So combining all the three cases, the probability for s1 NOT in the first set should be $\displaystyle \sum_{i=1}^{3}\frac{1}{3} \times(\frac{2}{3} \times \frac{2}{3} \times \frac{2}{3} \times \frac{2}{3})=\frac{2^{4}}{3^{4}}$.

4. Given the probability of s1 NOT in the first set is $\displaystyle \frac{2^{4}}{3^{4}}$, the probability that s1 exists in the first set is $\displaystyle 1-\frac{2^{4}}{3^{4}}$ (right?)

5. Still remember the other item s2? I think now you could similarly find that the probability of s2 in the first set is also $\displaystyle 1-\frac{2^{4}}{3^{4}}$ (according to Steps 2-4).

5. So now we can go for the probability for both s1 AND s2 in the first set: $\displaystyle (1-\frac{2^{4}}{3^{4}}) \times (1-\frac{2^{4}}{3^{4}})$.

So the above is how I think to solve the question. I try to make it specific enough for us to more easily spot where could go wrong. Let me know if more explanations could be useful and welcome any further discussion.
• Jan 22nd 2013, 06:39 PM
chiro
Re: What is the probability of having the same numbers in two sets
Hey ajlakanen.

Do you know how to express the probability in set-theoretic form? (It will make your life a lot easier for these kinds of problems).
• Jan 23rd 2013, 03:36 AM
ajlakanen
Re: What is the probability of having the same numbers in two sets
Quote:

Originally Posted by kylehk
So the above is how I think to solve the question. I try to make it specific enough for us to more easily spot where could go wrong. Let me know if more explanations could be useful and welcome any further discussion.

I can be wrong, but I think there is an error in this solution.

I couldn't (yet) find the analytic solution for this, but I ran a simulation, and got a very different answer. (I ran the simulation about a million times.)
• Jan 23rd 2013, 06:11 AM
kylehk
Re: What is the probability of having the same numbers in two sets
Quote:

Originally Posted by ajlakanen
I can be wrong, but I think there is an error in this solution.

I couldn't (yet) find the analytic solution for this, but I ran a simulation, and got a very different answer. (I ran the simulation about a million times.)

Hi Antti-Jussi,

Seems that didn't help you out yet. Guess you could discuss with your classmates a little bit more... Keep me updated when you got the solution. Best of luck:)
• Jan 23rd 2013, 07:17 AM
ebaines
Re: What is the probability of having the same numbers in two sets
Quote:

Originally Posted by kylehk
5. So now we can go for the probability for both s1 AND s2 in the first set: $\displaystyle (1-\frac{2^{4}}{3^{4}}) \times (1-\frac{2^{4}}{3^{4}})$.

I disagree with this. The probability of the first draw having a match is indeed $\displaystyle 1- (\frac 2 3 )^4$, but if that match is made then the probability of the second draw being a match is $\displaystyle 1 - (\frac 2 3 )^3$; the exponent is 3 because there are only three numbers of the original 4 that are left to be a match.
So the overall probability of matching both numbers is $\displaystyle [1-(\frac 2 3 )^4] \times [1-( \frac 2 3 )^3] = 0.5647...$
• Jan 23rd 2013, 07:26 AM
Plato
Re: What is the probability of having the same numbers in two sets
Quote:

Originally Posted by ajlakanen
I ran a simulation, and got a very different answer. (I ran the simulation about a million times.)

• Jan 23rd 2013, 11:53 AM
johng
Re: What is the probability of having the same numbers in two sets
Hi Aj,
Since you mentioned simulation, I assume you can program in some language. My favorite language is Java, but for quick programs, C is probably easier. In any event here's a C program which solves your problem -- not a simulation but the solution. In fact, the program allows different total values in the first set -- for your original 4, total.
Total Number Probability
4 11/27
5 131/247
6 473/729
7 179/243
8 5281/6561

As you can see the probabilities increase, which is what you expect. Also, I haven't seen the correct answer of 11/27 yet. Here's the program. Any questions, let me know. Sorry, I just noticed this app removed all the tabs in the C file; I hope you can still decipher it.

#include <stdio.h>
int base; // the uniform random variable is uniformly distributed on [0,base-1]
int length; // the total number of r.v.'s in the random sample
int x[16];
// x is array of all possible outcomes; i.e. all base base(3) integers of length(6);
// make 16 components to allow for longer lengths
void nextX(void); // compute next integer in given base
int bothIn_lengthminus2(void); // do both occur as array component x[i], 0<=i<length-2?
int gcd(int a,int b); // standard Euclidean algorithm for positive integers a,b

int main() {
base=3,length=5;
int i,j,last,count;
for (j=6;j<=10;j++) {
length++;
for (last=1,i=0;i<length;i++) {
x[i]=0;
last*=base;
}
// now last is total number of outcomes
count=0;
for (i=0;i<last;i++) {
if (bothIn_lengthminus2()) {
count++;
}
nextX();
}
i=gcd(count,last);
printf("event probability is %d / %d\n",count/i,last/i);
}
return(0);
}

void nextX() {
int carry=1,i;
for (i=0;i<length && carry;i++) {
x[i]+=carry;
if (x[i]>=base) {
x[i]-=base;
}
else {
carry=0;
}
}
}

int bothIn_lengthminus2() {
int u=x[length-2], v=x[length-2];
int i,last=length-2,countu=0,countv=0;
if (u==v) {
for (i=0;i<last && countu<2;i++) {
if (x[i]==u) {
countu++;
}
}
return(countu==2 ? 1 : 0);
}
for (i=0;i<last;i++) {
if (x[i]==u) {
countu++;
}
else if (x[i]==v) {
countv++;
}
}
return(countu && countv);
}

int gcd(int a,int b) {
int r=1;
while (r) {
r=a%b;
a=b;
b=r;
}
return(a);
}
• Jan 23rd 2013, 01:02 PM
ebaines
Re: What is the probability of having the same numbers in two sets
johng - I believe your simulation is incorrect and underestimates the probability of both the 2nd set of numbers being present in the first. It seems to count only those cases where the relative order of placement of the numbers in the 2nd set is the same as in the first, whereas the only criteria is that both numbers be present, regardless of order. For example: if the first set is {1,2,1,3)} and the second set is {3,2} I believe your program would not count it as a success because in the first set the 2 comes before the 3 whereas in the second set the 2 comes after the 3. But this should be counted as a success since both of the numbers of the second set are present in the first set. So your calculation of the probability of suceess equaling 11/27 is too low.
• Jan 23rd 2013, 03:46 PM
johng
Re: What is the probability of having the same numbers in two sets
OOPS - my bad. I blindly copied down the computer output without thinking. The bug in the above program is in function bothIn_lengthminus2. u=x[length-1], v=x[length-2] is the correction. As written it just checks on the next to last component instead of both components.
Here are the correct probabilities:
6 133/243 - original problem
7 491/729
8 559/329
etc.

Here is one way of obtaining the correct probability 133/243:

Attachment 26682
• Jan 23rd 2013, 05:44 PM
kylehk
Re: What is the probability of having the same numbers in two sets
Quote:

Originally Posted by ebaines
I disagree with Step 5. The probability of the first draw having a match is indeed $\displaystyle 1- (\frac 2 3 )^4$, but if that match is made then the probability of the second draw being a match is $\displaystyle 1 - (\frac 2 3 )^3$; the exponent is 3 because there are only three numbers of the original 4 that are left to be a match.
So the overall probability of matching both numbers is $\displaystyle [1-(\frac 2 3 )^4] \times [1-( \frac 2 3 )^3] = 0.5647...$

Thanks for pointing it out. Step 5 does ignore the case that both numbers in the second set matches with only one number in the first set (like Example 2 as in the original post).