A bag contains the following 23 letters

A,A,A,A
B,B
C,C
D,D
E,E
F,F
G,G
H,H
I,I
J,J
K

Draw one at a time without replacement. Game ends when all of any one letter are drawn. What is the probability for each letter ending the game?

It seems clear to me ending the game by drawing K will be the most likely outcome. It also seems clear that the odds for B through J will be the same, and greater than the odds of A.

When going to solve this, I see that no more than 13 letters can be drawn. But I am at a loss for how to set this up without enumerating what seems to be a ton of possible outcomes.

P+9P/2+P/4=1

p=1/5.75

Seems obvious, which has me worried.

Not sure you answered the right question. He wants to know the chance the K wins, and the chance one of the pairs wins, and the chance the quads win. It's definitely 3 different values. And I don't think they are simply 1/2 and 1/4 the singleton chance, since the chance of a subsequent match after the first one goes up without replacement.

I'm sure you know that my P is the prob. of K and the pairs are half of that and A is 1/4 of that.

Consider just AA and B. With my method you get 4/6 for B and 2/6 for A, which coincides with what you get with direct enumeration.

Pr(A) = 2/3 * 1/2 = 2/6

Pr(B) = 2/3 * 1/2 + 1/3 = 4/6

Not a proof, but it provides some support for the approach I used.

Let's look at a slightly more complicated case for which it is still fairly easy to enumerate all the cases.

Suppose there are 3 A's, 2 B's, and 1 C.

Then it is fairly easy to calculate that:

P(A) = 54/360

P(B) = 96/360

P(C) = 210/360

P.S. I do not have an elegant way to produce these numbers, even in this fairly easy case.

Non-elegant approach: do a large simulation!

I simulated 100,000 trials of the original problem and here is what I found:

P(A)=1.077%
P(B)=7.717%
P(C)=7.875%
P(D)=7.782%
P(E)=8.007%
P(F)=7.796%
P(G)=7.900%
P(H)=7.835%
P(I)=7.798%
P(J)=7.805%
P(K)=28.408%

I have sloshed through the logic (with a big assist from a former mod of this forum) for the original A-K problem.

How can A be the "winner"? Clearly no K has appeared yet, and 4 A's have appeared, and none of B-J have appeared more than once each. So which "spots" can A be the final draw? Clearly any draw between 4 and 13.

Working through the logic using combinatorics, factorials, etc. (and there are different, equivalent, ways of writing this):

P(A) = Sum (T = 4 to 13) C((T-1),3) * 4! * (2^(T-4)) * (9!/(14-T)!) / ((23!)/(23-T)!)

Evaluating this sum via computer yields

P(A) = 79,302,546,892,800 / 7,124,122,778,572,800

or P(A) = 1.113%

Use similar logic, when does K become the "winner"? K can be the winner on any turn from 1 to 13. The calculations depend upon how many A's have already been drawn (clearly this must be between 0 and 3). Using similar logic with combinatorics, etc., we get:

P(K) = Double Sum (from T = 1 to 13) and (from A = 0 to 3) (4!/(4-A)!) *(2^(T-A-1)) * (9!/(14-(T-A-1))!) / ((23!)/(23-T)!)

(of course, only evaluate the double sum for which the factorials make sense; for example, when T = 1, A cannot be 2, etc.).

Evaluating this double sum via computer yields that

P(K) = 2,009,078,326,886,400 / 7,124,122,778,572,800

or P(K) = 28.201%

A similar exercise can derive the probs for B through J, but it is easier, of course, to simply subtract P(A) + P(K) from one (noting that there are 9 equivalent probs here), so we find

P(B - J) = 559,526,878,310,400 / 7,124,122,778,572,800

or P(B - J) = 7.854%

Fortunately, these analytical results agree with the prior simulation results, so we are quite confident that these are correct.

So it appears there may not be "an elegant way"? I would have thought that for this kind of standard probability problem, which is usually represented as drawing different color marbles without replacement until one color is exhausted, that there would be.

If you love factorials, I think I have the formula for the general problem!!

Let there be L unique letters (in OP L was 11) and let TOTAL be the total number of letters (in OP TOTAL was 23). Let N(J) be the number of the Jth letters (so in OP the N's are 4,2,2,2,2,2,2,2,2,2,1). As above, we will use the index T for the Turn on which the winner is determined.

For simplicity of the formula below, suppose we reorder the letters so that we are interested in finding the probability of the 1st letter.

Then P(1) is a nested sum of L sums:

= Sum of (T from N(1) to TOTAL-(L-1))
Sum of (I(2) from 0 to N(2)-1)
Sum of (I(3) from 0 to N(3)-1)
.
.
.
Sum of (I(L-1) from 0 to N(L-1)-1)

The term that gets summed is a product of three terms (and an indicator term):

Term1 = T!/((N(1)-1)!*(T-N(1)-Sum of (K from 2 to L-1) I(K))! * Prod of (K from 2 to L-1) I(K)!)

Term2 = N(1)!*N(L)! / (N(L)-(T-N(1)-Sum of (K from 2 to L-1) I(K)))! * Prod of (K from 2 to L-1) N(K)!/(N(K)-I(K))!

Term3 = (TOTAL-T)! / TOTAL!

Term = Term1 * Term2 * Term3 * [0 <= T-(N(1)-Sum of (K from 2 to L-1) I(K)) <= N(L)-1]

where the bracket term is 1 if the condition is true and 0 otherwise

So there is a general formula for this type of problem. Whether you call this an "elegant" solution is up to you!

Thank you everybody for your contributions, including the unnamed former mod. Yes, this is the type of solution I was looking for, it's been so long since I've taken that intro to probability course that I was pretty much lost. I spent around a half hour trying to come up with the solution laid out in your prior post, with a similar method, to no avail. So thank you for that, and also your simulation results. At first I thought I overlooked something simple (after statmanhal's post), but felt by my earlier enumeration efforts that P(A) was much less than 1/4 of P(K). I couldn't prove it though so that was bugging me. Thanks again for the insightful post.

Grunch: we just need to find P(k) and P(a), because then we can say P(b) = P(c) = ... = P(j) =
[1 - P(a) - P(k)] / 9

P(k) = P(k first draw) + P(k 2nd draw) + P(game lasts 3 draws & k is 3rd draw) + ... = P_k1 + P_k2 + ... P_k13

P_k1 = P_k2 = 1/23

P_k3 = 1/23 - 9/C(23,2)/21
Or, P_k3 = [C(22,2)-9] / C(23,3) / 3

I'll do the rest another time. By my method there will be 13 lines of work to get P(k), then 10 lines to get P(a). Whether this can be done with less work than I've outlined, I don't know. Maybe someone already did, but I don't want to read the posts yet because they might spoil it for me.

A few more easy ones:

P_k4 = 1/23 - 9/C(23,3)

P_k13 = 2^9 * 4 / C(23,13) / 13

P_k12 =[(2^9 * 6)+9(2^8)4] / C(23,12) / 12