Thread: Urn (ith event is white)

This is from a practice exam where I know the answer, but can't seem to prove it for all cases.

Problem: Suppose you have an urn filled with M objects, W are white. What is the probability that if you select n objects without replacement the ith will be white.

My thoughts: If you do the expansion out for 2 objects, you see that the probability of the second choice being white works out to W/M, as though the first choice didn't matter.

I can't seem to come up with an argument either using conditional probability or independence that would explain that all choices from the urn from the 1st to the ith-1 don't matter. However since we're picking without replacement, they seem like they should matter when we make our ith pick?

Originally Posted by drowned

This is from a practice exam where I know the answer, but can't seem to prove it for all cases.

Problem: Suppose you have an urn filled with M objects, W are white. What is the probability that if you select n objects without replacement the ith will be white.

My thoughts: If you do the expansion out for 2 objects, you see that the probability of the second choice being white works out to W/M, as though the first choice didn't matter.

I can't seem to come up with an argument either using conditional probability or independence that would explain that all choices from the urn from the 1st to the ith-1 don't matter. However since we're picking without replacement, they seem like they should matter when we make our ith pick?

I'm afraid my argument is a bit involved, and maybe someone else can post a simpler explanation.

Without loss of generality, let the non-white objects be labeled as black. So we have a multiset (hopefully there's no confusion that I re-use the letter W):

S = {W,...,W,B,...,B}

For example, if M = 7 and W = 4 then we have

S = {W, W, W, W, B, B, B}

Just say we pick them all out, without replacement. Then any particular order is given by a permutation of S. You could think in terms of 7-tuples or strings; for example, one possible permutation is

(W, W, B, B, W, B, W) (tuple representation)
WWBBWBW (string representation)

Now I claim that

1) The probability that the ith index is W in the above example is the same as the probability that the ith index is W if we had only picked n elements, instead of all of them.

2) The probability that the ith index is W in the above example is independent of i (that is, the same no matter what i is).

I won't give formal proofs, but more hand-wavy explanations

1) This is true because the probability of an event is not dependent on events that happen afterwards.

2) This is true because there is nothing special to distinguish any index from any other index. So consider permutations of the set {1,2,3,4,5}. It is intuitively clear that the number 1 is equally likely to appear in any index in the range {1...5} for a randomly chosen permutation. If we found that 1 is more likely to appear in the 2nd position compared with the 4th, we would naturally suspect we had made an error in counting.

There's probably a much simpler explanation, and the lack of formal proof I offered may leave some unconvinced, nevertheless I believe it to be valid reasoning.

(One final note: We are assuming that i <= n. Obviously if i > n then the probability could either be considered 0, or undefined since the event is not in the sample space.)

Thanks for the response. Yes, what I'm looking for is kinda-sorta a formal proof for your 1) statement.

I think I'm almost there (with what you've added to the table). If we have 7 objects and 4 of which are white there are (7 C 4) = 35 ways to arrange the 4 whites inside of a total of 7 objects. Now we want to "lock" the last object we choose as a white so there is 6 objects we want to permutate but 3 whites left so (6 C 3) = 20 ways to arrange the 3 whites. And 20 / 35 = 4 / 7 = (W/M)

I think I might be able to solve this out for M objects and W whites (M C W) / (M-1 C W-1) by using the native formal for combination and simplifying, but I'm getting the vibe there's an easier way. I'll do it out the combinations way right now since I can't sleep until I get this problem (even though it's extra credit )

Edit: Yes, (M choose W) / (M-1 choose W-1) = M / W after simplifying. The only problem is that this proof assumes we sample every single object, so it goes back to needing a proof of 1).

Edit Edit: I think I got a quasi proof of 1) while going to the bathroom If we have a bag of a million marbles with 500 whites and the rest blacks, then it doesn't matter whether we sample 1, 20, or 10,000 marbles because the chance of getting x% of whites is the same....I can't think of a formal way to say that if we take a cross section of an evenly distributed bag then the cross section will have the same mix ratio as the full bag.

Originally Posted by drowned

Edit Edit: I think I got a quasi proof of 1) while going to the bathroom If we have a bag of a million marbles with 500 whites and the rest blacks, then it doesn't matter whether we sample 1, 20, or 10,000 marbles because the chance of getting x% of whites is the same....I can't think of a formal way to say that if we take a cross section of an evenly distributed bag then the cross section will have the same mix ratio as the full bag.

This would have to be phrased carefully to avoid a false proposition, because we are dealing with a discrete space. So for example, if we are considering the trial of choosing one marble, obviously it's impossible to get 50% white for a given trial, but if we pick two marbles then it is possible. I think we would use expected value to make things precise. (That is, if we define a trial as choosing x objects, 0 < x <= M, and we define random variable X as (the number of whites) divided by x, then the expected value E(X) is independent of x.) But would we then have to prove that this problem is, in fact, equivalent to statement 1)?

I would work on formalisation but it's getting late here and I think I'd rather sleep on it. Maybe when morning comes, either you will have solved your own problem or someone else will have written a proof.

I ended up saying "if we sample the whole M we get W/M by simplification". The next part of the problem asks "What's the probability that the ith event in our sample n is white given we have X white in the sample" so I had to intuitively rely on the idea that if our method works for he whole sample M then it should work for the subset n.

It's not how I would like it, but there comes a point where you can't spend 6 hours working on 1 extra credit problem when 6 more are looming. I've spent a solid hour googling to see if anyone else has ever tried to do a problem like this and it seems no...most urn problems are hypergeometric or are solved using the tree method...and the tree method is for 5 year olds

Originally Posted by drowned

I ended up saying "if we sample the whole M we get W/M by simplification". The next part of the problem asks "What's the probability that the ith event in our sample n is white given we have X white in the sample" so I had to intuitively rely on the idea that if our method works for he whole sample M then it should work for the subset n.

I don't think an intuitive leap is actually necessary in this case. We are given that there are n objects and that X of them are white. So this is the exact same problem as the original except that we no longer need to prove 1) because we chose all of the elements. So we should get probability X/n by 2).

Originally Posted by drowned

It's not how I would like it, but there comes a point where you can't spend 6 hours working on 1 extra credit problem when 6 more are looming. I've spent a solid hour googling to see if anyone else has ever tried to do a problem like this and it seems no...most urn problems are hypergeometric or are solved using the tree method...and the tree method is for 5 year olds

I hear you. :-) For something that seems intuitively true, sometimes the formalisations come easily to me, other times elusive, this is one of the latter.