Thread: 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).

Sorry for my bad English.

Cheers,
Antti-Jussi

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

Sorry for my bad English.

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 s₁ and s₂ represent the first and second item in the latter set. Either of s₁ and s₂ could be 1, 2, or 3 with probability of 1/3. For example, s₁ = 1 is with probability 1/3 since s₁ is randomly chosen from three numbers.

2. Now let's consider a specific case, say when s₁ = 1 AND s₁ 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 s₁ = 1 NOT in the first set should be .

3. Step 2 considers one specific case (s₁ = 1) out of three possible cases (i.e., s₁ = 1, 2, or 3). So combining all the three cases, the probability for s₁ NOT in the first set should be .

4. Given the probability of s₁ NOT in the first set is , the probability that s₁ exists in the first set is (right?)

5. Still remember the other item s₂? I think now you could similarly find that the probability of s₂ in the first set is also (according to Steps 2-4).

5. So now we can go for the probability for both s₁ AND s₂ in the first set: .

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.

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

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

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

Originally Posted by kylehk

5. So now we can go for the probability for both s₁ AND s₂ in the first set: .

I disagree with this. The probability of the first draw having a match is indeed , but if that match is made then the probability of the second draw being a match is ; 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

Originally Posted by ajlakanen

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

What answer did your simulation give you?

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);
}

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.

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:

Originally Posted by ebaines

I disagree with Step 5. The probability of the first draw having a match is indeed , but if that match is made then the probability of the second draw being a match is ; 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

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