question for MIT probability class

[etizzle]

thanks for any help


i've got 20 balls, 2 white, 8 red, 6 black, and 4 green. I have 4 distinguishable urns. The balls are placed randomly among the urns, and each urn can have any number of balls.

What is the probability that no urn will contain both green and black balls?

[pzhon]

[ QUOTE ]
What is the probability that no urn will contain both green and black balls?

[/ QUOTE ]
You can ignore the colors other than green and black.

I think the easiest approach is to determine the distribution of the number of urns containing green balls. Conditioned on these cases, you can compute the probability that the black balls are in the other urns.

[etizzle]

this is along the lines of what i was trying to do. The red and white balls are meaningless.

But I dont really know how to come up with the distribution for the 6 balls. Where I started was counting up the chances that every urn has a green ball in it, which means that there must be at least one urn with both. COunting backwards in this way seems like it may take a long time.

[pzhon]

[ QUOTE ]

[ QUOTE ]
I think the easiest approach is to determine the distribution of the number of urns containing green balls. Conditioned on these cases, you can compute the probability that the black balls are in the other urns.


[/ QUOTE ]

But I dont really know how to come up with the distribution for the 6 balls.

[/ QUOTE ]
You don't need this distribution to compute the answer. You can use the distribution of the number of urns containing at least one of the 4 green balls, which is simple enough to compute in an ad hoc fashion. For example, you can compute the probability that precisely two urns contain a green ball, then compute the probability that the 6 black balls are in the other 2 urns. It's easier to compute 1, 2, and 4, and then you can subtract these probabilities to get 3.

If you want a more general method to determine the distribution, you can imagine placing the balls of one color in the urns one at a time while keeping track of the number of urns containing at least one. If you have U urns and N are occupied, the probability of moving to the state of N+1 occupied is (U-N)/U, and the probability of staying at N occupied is N/U. You can encode these transitions in a transfer matrix, and adding B balls corresponds to applying the Bth power of the transfer matrix. It's also easily computable by hand when B is small.

These seem like combinatorics problems, not probability problems.

[AaronBrown]

phzon's approach is easy. You can choose to make the urns and balls distinguishable or not, I think it's easier to make them both distinguishable.

Let's start with the four green balls. They can be placed in all four urns in 24 different ways. They can be placed in three urns 144 different ways (4 different ways to eliminate one urn, 3 different ways to pick one urn to hold two balls, 4 different ways to pick the first stand-alone ball, 3 different ways to pick the second stand-alone ball). They can be placed in two urns 84 different ways and in one urn 4 different ways. These add up, as they should, to 4^4 = 256.

If they end up in four urns, the probability of no urn having both green and black balls is zero. If they end up in three, it's (1/4)^6. If they end up in 2 it's (1/2)^6. If they end up in 1 it's (3/4)^6.

Multiplying and adding up gives about 0.8%.

[etizzle]

thanks guys

[BruceZ]

[ QUOTE ]
thanks for any help


i've got 20 balls, 2 white, 8 red, 6 black, and 4 green. I have 4 distinguishable urns. The balls are placed randomly among the urns, and each urn can have any number of balls.

What is the probability that no urn will contain both green and black balls?

[/ QUOTE ]

There are 4^10 total ways to place the 10 black and green balls in 4 cups. We will partition the favorable outcomes into 3 cases:

All 4 greens in 1 cup:
4 ways to pick green cup times 3^6 ways to place 6 black balls in other 3 cups
= 4*3^6

All 4 greens in 2 cups:
C(4,2) ways to pick 2 green cups times 2^4<font color="red"> - 2</font> ways to place 4 green balls in 2 green cups times 2^6 ways to place 6 black balls in other 2 cups. <font color="blue">Note that the -2 subtracts off the cases where all 4 greens go into just one of the two urns, since these were counted in the last case.</font>
= C(4,2)*(2^4 - 2)*2^6

All 4 greens in 3 cups:
C(4,3) ways to pick 3 green cups times 3^4<font color="red"> - C(3,2)*2^4 + 3</font> ways to place 4 green balls in 3 green cups times 1 way to place 6 black balls in 1 cup. <font color="blue">Note that the -C(3,2)*2^4 subtracts off the cases where all of the green balls go into only two of the three urns, and these in turn include cases where they all go into just one urn, since these were counted by the previous two cases. The +3 adds back the number of cases where they all go into one urn since these were subtracted twice by the C(3,2)*2^4.</font>
= C(4,3)*[3^4 - C(3,2)*2^4 + 3]*1


Total probability = [4*3^6 + C(4,2)*(2^4<font color="red"> - 2</font>)*2^6 + C(4,3)*(3^4<font color="red"> - C(3,2)*2^4 + 3</font>)*1] / 4^10

= 8436 / 4^10

= <font color="red">2109 / 262,144 =~ 0.80%.</font>

[ QUOTE ]
[ QUOTE ]
thanks for any help


i've got 20 balls, 2 white, 8 red, 6 black, and 4 green. I have 4 distinguishable urns. The balls are placed randomly among the urns, and each urn can have any number of balls.

What is the probability that no urn will contain both green and black balls?

[/ QUOTE ]

There are 4^10 total ways to place the 10 black and green balls in 4 cups. We will partition the favorable outcomes into 3 cases:
.
.



[/ QUOTE ]

Hmm, I'm pretty sure that the answer you're getting is incorrect for several reasons:
The cases that all the green balls are in two urns include the cases where all the green balls are in one urn.
It also appears that you're treating the urns, and balls as distinguishable for calculating the number of possible arrangements, but calculating the 'successful' cases as if the urns were indistinguishable.

[BruceZ]

[ QUOTE ]
[ QUOTE ]
There are 4^10 total ways to place the 10 black and green balls in 4 cups. We will partition the favorable outcomes into 3 cases:
.
.



[/ QUOTE ]

Hmm, I'm pretty sure that the answer you're getting is incorrect for several reasons:
The cases that all the green balls are in two urns include the cases where all the green balls are in one urn.

[/ QUOTE ]

I just realized that I had this problem and came in to fix it before I saw your post. The case where all the green balls are in three urns also includes the cases where all the green balls are in two or one urn. See my corrections in red in the original post which properly subtract these cases. This was the only type of error. The change of 0.1% makes the final answer identical to Aaron’s. Also, his counting of the number of ways to put all 4 greens in 1-3 urns are also identical to mine (4, 84, 144).


[ QUOTE ]
It also appears that you're treating the urns, and balls as distinguishable for calculating the number of possible arrangements, but calculating the 'successful' cases as if the urns were indistinguishable.

[/ QUOTE ]

I'm treating both the balls and the urns as distinguishable for all purposes. I'm counting the ways that each distinguishable ball can select a distinguishable urn. There is no problem here.

So I was a bit bored and decided to solve this problem by hand, but I arrived at a different answer than the above posters. I would appreciate if someone told me where I went awry.

First, consider the possible arrangements of four green balls in four urns. There are four different overarching categories: 3 empty urns, 2 empty urns, 1 empty urn, and 0 empty urns.

If there are 3 empty urns, there are 4 possible configurations:

4000
0400
0040
0004

If there are two open urns, there are 18 possible configurations:

3100
3010
3001

1300
0310
0301

0031
1030
0130

1003
0103
0013

2020
2200
2002
0220
0202
0022

There are 12 possible configurations with 1 open urn:

2110
2101
2011

1201
1210
0211

1120
1021
0121

0112
1012
1102

Finally, there is one configuration with 0 open urns:

1111

This gives us 35 different configurations of green balls among the 4 urns, with 4/35ths leaving 3 open, 18/35ths leaving 2 open, 12/35ths leaving 1 open and 1/35 leaving 0 open urns.

Now, consider the configurations of the 6 black balls among the 4 urns:

Again, we have 4 possible cases, leaving 3, 2, 1 or 0 urns open.

There are 4 configurations leaving 3 open urns:

6000
0600
0060
0006

There are 30 configuations leaving 2 open urns:

5100
5010
5001

0501
0510
1500

1050
0150
0051

0105
1005
0015

4200
4020
4002

2400
0420
0402

2040
0240
0042

2004
0204
0024

3300
3030
3003
0330
0303
0033

There are 40 combinations leaving 1 open urn:

4110
4101
4011

1401
1410
0411

1041
1140
0141

1104
1014
0114

3210
3201
3102
3120
3021
3012

0321
0312
1320
1302
2310
2301

0132
0231
1230
1032
2031
2130

0123
0213
1023
1203
2103
2013

2220
2202
2022
0222

Finally, there are 10 configurations leaving 0 open urns:

3111
1311
1131
1113

2211
2121
2112
1221
1212
1122

This gives us 84 possible configurations of 6 black balls among 4 urns, with the following distribution:

4/84 leave 3 open urns.
30/84 leave 2 open urns.
40/84 leave 1 open urn.
10/84 leave 0 open urns.

Now it is not too difficult to figure out how many configurations have no green and black balls in the same urn.

First, if all the green balls are in one urn (p = 4/35):

4/84 times all the black balls are also in one urn, and 3/4 of the time they will not overlap. So, 4/35 * 4/84 * 3/4 = 12/2940.

30/84 times the black balls will be in 2 urns, leaving two open. 14 out of these 30 configurations will not overlap with any given placement of the green balls. (e.g., if there are four green balls in the first urn, and the black balls are distributed among 2 urns, there is a 14/30 chance that there are no black and green balls in the same urn.) Therefore:

4/35*30/84*14/30 = 56/2940.

Last, when the green balls are in a single urn, 40/84 times the black balls will be distributed among 3 urns, leaving 1 open. 1/4 of those times, the open urn will be the urn in which the green balls are placed. Therefore:

4/35 * 40/84 * 1/4 = 40/2940.

So, P(no overlap|all green balls in a single urn)=P(no overlap|all green balls in a single urn and all black balls in a single urn) + P(no overlap|all green balls in a single urn and all black balls in two urns) + P(no overlap|all green balls in a single urn and all black balls in three urns)

Or: P(no overlap|all green in a single urn) = 12/2940 + 56/2940 + 40/2940
= 108/2940

Next, we consider the cases when the green balls are distributed among 2 of the four urns. There will be only two configurations of black balls that could avoid overlap given 2 urns without green balls, those in which the black balls were distributed among 2 or 1 urns.

If the green balls are distributed in two urns, there are 6 different general configurations possible: 00XX, 0X0X, 0XX0, X00X, X0X0, XX00. If the general configuration of green balls does not overlap with the black balls, the black balls must be arranged in the inverse configuration (e.g., if green are in the 3rd and 4th, 00XX, black must be in the first and second XX00.) So, looking at the 30 configurations of black balls which leave 2 open urns, we see that, for any generic configuration of green balls, there will be 5 of the 30 non-overlapping configurations of black balls.

So: P(no overlap|green balls in 2 urns and black balls in two urns) =
P(green balls in two urns) * P(black balls in two urns) * P(they don't overlap)=
18/35 * 30/84 * 1/6 =
90/2940

Next, consider the possibility that the green balls are distributed among 2 urns, and the black balls are in only 1 urn. In this case, 2/4 configurations of black balls will be non-overlaping, so:

P(no overlap|green balls in two urns and black balls in one) =
P(green in two urns) * P(black in one urn) * 1/2 =
18/35 * 4/84 * 1/2 =
36/ 2940

The total conditional probability P(no overlap|green balls in two urns) =
90/2940 + 36/2940 =
126/2940

Last, consider the case where the green balls are distributed in 3 urns, leaving one open urn. In this case, the black balls must all be in the open urn, which is only one possible configuration. Therefore:

P(no overlap|green balls in 3 urns) =
P(green in 3)* P(black in 1) * 1/4=
12/35 * 4/84 * 1/4 = 12/2940.

So, the total probability of configurations with no black and green balls in the same urn =
P(no overlap|green balls in one urn) + P(no overlap| green balls in two urns) + P(no overlap|green balls in three urns)=
108/2940 + 126/2940 + 12/2940 =
246/2940 =
.08367 or around 8.4% of all configurations have no overlap between the green and black balls.