I got myself a little puzzle and for some reason I'm totally lost here. Let's say we have a roulette table and you have a right to choose one out of 37 numbers on it (0-36). We have 3 scenarios:

1. Each "round" consists of x number of spins till we get 10 winning numbers (x spins because sometimes we can hit the number which already won) - around 27%
2. Each "round" consists of x number of spins till we get 15 winning numbers - around 41%
3. Each "round" consists of x number of spins till we get 18 winning numbers - around 49%

I have 2 questions and obviously I would just need a formula so that I could manually calculate result for each scenario...
1. How often will we win in EXACTLY 4 out of 6 draws (so in scenario 1, how often will our number be in the pool of 10 winning ones if we play the game 6 times)
2. How often will we win in EXACTLY 3 out of 6 draws

I do have some "formula" done here, but I think it's better just to leave the question here and compare the formula I get here to it.

Thank you in advance!

Unless I am misunderstanding something, by the way the spins are conducted until there are W unique winning numbers in a scenario, each draw is equivalent to a binomial experiment with prob of success equal to W/37.

Binomial probs B(s,n,p) = C(n,s) * (p^s) * [(1-p)^(n-s)];

where B(s,n,p) is the prob of getting exactly s successes out of n independent draws where the prob of success of each draw is p, and C is the choose function.

So in your case, p=W/37, n=6, s=3 or 4, W=10, 15, or 18.

You can calculate these by hand or on many calculators or computer programs that have the Choose function and/or binomial probabilities built-in.

What is the 27%? And can you elaborate on your parenthetical?

Again, can you elaborate on your parenthetical? I'm not following.

1. well, sry if it's not obvious, but what I meant is that we need to have 10 winning numbers out of 37 in total no matter how many spins we need to get there. This would mean 10 spins minimum if we would get different number each time, but if for example 2 spins give us number 4 this automatically means we will need at least 11 spins in total. Please note this doesn't really influence our equation and the only important thing is that we have 10 out of 37 winning numbers which is around 27% of winning numbers for scenario 1 (0,270270270...)
2. for scenario 1 - if we bet on, for example, number 4 in 6 draws where each draw has 10 winning numbers, what is the probability that number 4 will be one of the winning numbers in exactly 4 out of those 6 draws...

This indeed makes sense, the only bad thing is that I needed to use only calculator for CHOOSE function since it seems I'm unable to use the one part of Excel... Will run analysis tomorrow and post results here... Thank you for the help!

Ok then it's what Whosnext said. This is equivalent to 6 raffles, each with 10 prizes. In each raffle there's a 10/37 chance that your name is among those drawn. The raffles are independent of each other, so the distribution is binomial.

Thanks for all the help above, it all actually really makes sense. I do have follow-up question now though:

Would the probability stay the same no matter how much spins we have during the each "draw" or do we only look at the number of winners?

To explain, imagine that in first 4 draws we have exactly 10 spins since each spin got us a number which we didn't have in any of the spins in that draw before and we had somebody betting on that number, but on draw 5 and 6 we hit number 4 both times and nobody had a chip on it so we had to have 11 spins and essentially 11 winning numbers although only 10 winners. When calculating p would we still have 10/37 since there were 10 winners on each draw or would we need to take average number of "hit numbers" so p would be 10.33/37 (4 draws with 10 winning numbers and 2 draws with 11 winning numbers gives us avg of 10.33)?

I would think we need an average but wanted to check...

I think I am following what you are asking.

Think about it this way. Simplify everything down so as to make it crystal clear. Consider the following "twin" cases.

-----

Suppose the roulette wheel is 1-10. You have number 4 and your two buddies have numbers 6 and 8 respectively.

Case 1: The roulette wheel is spun exactly once. Here your prob of winning is clearly 1/10.

Case 2: The roulette wheel is spun until there is one winner. Here your prob of winning is clearly 1/3. (Of course, your prob of winning is higher than 1/10 even though it will likely take more than 10 spins to find a winner. So don't focus upon how many spins are expected to occur.)

So the two "cases" clearly give different win probs.

-----

Case 3: The roulette wheel is spun until there are two unique numbers landed on. Then your chance of winning is clearly 2/10.

Case 4: The roulette wheel is spun until there are exactly two winners. Then your chance of winning is clearly 2/3.

Again, the cases clearly give different win probs.

-----

Now return to a 0-36 roulette wheel with 37 slots. You have number 4 and there are several other people betting on other numbers.

Case 5: The roulette wheel is spun until there are 10 unique numbers landed on. Then your chance of winning is clearly 10/37.

Case 6: The roulette wheel is spun until there are exactly ten winners. Then your chance of winning is clearly 10/B, where B is the number of slots Bet upon.

If prizes are awarded per the rules in Case 5 (i.e., spins continue until 10 unique slots are visited), then you should use 10/37 as your probability p. On the other hand, if prizes are awarded per the rules in Case 6 (i.e., spins continue until 10 unique slots that have chips bet on them are visited), then you should use 10/B as your probability p.

Hope that makes sense.

Sure it does, thx for the detailed explanation. It's quite dummy proof and I really appreciate it!

In the real life situation I need this for I can't unfortunately know how many people other than me is "playing" and the only data I know is the number of spins needed during each draw to reach 10 winners (for scenario 1) so the only thing I can get from it would be the "average probability" where I use the average number of drawn numbers to hit 10 unique winners.

Once again, thx for the detailed explanation

Oh, i see.

I think that means that if you observe on average S spins to achieve the desired W winners, then your probability of winning was S/37 (not W/37).

well not really, I would say it means that if I observe on average S spins to achieve desired W winners when hitting N numbers, then my probability of winning would be N/37, not S/37 or W/37 - with S/37 I would include spins where I not only hit numbers nobody bet on but also the cases when I hit the same number twice which IMO doesn't influence my probability at all (hitting same number twice doesn't take any number from the list or add any winners to the list)

I don't know what your "N" is.

S gives you information on how many numbers are "covered" (have bets placed on them). The ratio W/S tells you what fraction of numbers are covered. So W/B becomes S/37 algrebraically.

For example, we have four people betting on 4,5,18,22 respectively. We have to have 2 winners.

To get there we had to spin 7 times and the numbers were: 4,6,6,7,12,15,22

In this case, number of spins S ws 7, number of W winners was 2 and number of N numbers was 6

So, this way the probability to hit certain number would be N/37 because we don't want to have double 6s in the calculation... This is just my guess but if I got everything right I think this should be accurate

No, it would be 2/4 (or whatever names you've given to those variables), because you'll keep spinning until there are 2 different winners, which means the wheel may as well only have 4 numbers. In fact, once a number is hit, the wheel essentially reduces to having 3 #'s, so the problem is better represented by a pile of 4 cards being drawn from.

Edit: The spins where a non-winning # comes up are irrelevant, so as long as the number of spins is not limited, the actual #spins that end up being needed has no bearing on the probability. Between winning numbers, there's no difference between observing the wheel land on useless numbers vs, say, looking at the weather. When you all picked 4,5,18,22, the fact that the wheel lands on #'s 30, 32, 27 does not change anyone's chances any more than the fact that it rained in Oklahoma.

He is saying that he does not know how many people have placed bets on unique numbers. So he is using the number of spins and number of unique number spins to infer how many bets have been placed. And, finally, that info to infer (calculate) what his ex ante chance of winning the round.

-----

Under the rules that they spin until they achieve the desired number of winners, here is some notation to try to keep things clear:

T = total number of slots [37]

W = total number of winners per round (keep spinning until W winners are achieved)

B = unknown total number of people betting (each person bets on a unique number)

S = ex post total number of spins in round before W winners achieved

N = ex post total number of unique numbers landed on in the S spins

-----

If B is known, then the prob of each person winning a round is clearly W/B.

If B is not known, then you can use information on how many spins it took (or, better, how many unique numbers were landed on) to infer B.

Your best guess for B once you observe S and N is [T/(N/W)] so that your best guess for W/B becomes W/[T/(N/W)] = N/T.

P.S. If you do not know B or N, but you know S, then what is your best guess for B? I am not sure if this is an easy problem or not.

Good question. This sounds like the reverse of the Coupon Collector's problem. Since S is all we know, I think it's our best guess of the mean number of spins required.

So then, E(B) = S / (Bth harmonic #)
which, according to Wolfram, is approximately S / W[S * e^(1443/2500)]
where W[...] is the Lambert W function.

That formula uses the asymptotic approximation of the Nth harmonic number. Without using the approximation, there's no analytical solution because B must be an integer.

I plugged S=7 into Wolfram. With the approximate formula, I get B=3.708.
The numerical solution to the exact formula is B=3.54.

So on average B=3.54, but knowing that N must be an integer, I suppose the best real guess would be B=4, which in turn would imply that the true average spins required is 8.33. (If we instead round down and say B=3, that implies the true average is 5.5.)

I'm not sure if that's the right way to go about it, but maybe.

Ok, now I am getting lost here. We know T for sure, the total number of slots on the roulette wheel. But we also know W here.

Doesn't our best estimate of B, after observing S, depend upon W, the total number of winners? Which we know too.

If T=100 and we observe S=10, then we would have different guesses for B if W=2 or W=10. If W=10 and S=10, then we would presume that B is very large (say 100) since there were no "wasted" spins (every spin was a winner).

On the other hand if W=2 and S=10, then we would presume that B is maybe around 20 [T/(S/W) = 100/(10/2) = 100/5 = 20] since there were so many "wasted" spins (80%).

I realize that T/(S/W) isn't the best guess for B due to the coupon collector aspect here, but it must be something like that.

Note, it is not clear if we seek the "most likely" B or the expected B. I imagine these two may be different, even leaving aside the integer requirement.

I guess it is a Bayes-law application to an aborted coupon collector problem.

Let's go with the first version for now, the most likely B. Then we seek the integer B such that the probability of observing S (given T and W) is highest.

Does that make sense? Is that easy to find?

Sorry, disregard my last post. You're right, W matters. Coupon Collector is the special case where W=B.

I don't think solving for B should be harder than solving for S, but I don't think either formula will be pretty like it is when W=B (at least, pretty when solving for S).

I'll take a crack at it when I get a chance, but I'm also pretty sure Bruce tackled Coupon Collector variants in a few old threads (and maybe one of them is the variant we're dealing with here).

In fact, what I said would be wrong even with W=B, since T doesn't have to equal B. The win probabilities are not related to harmonic numbers.

I still don't expect this to be hard, but not also not quick and easy. I expect to have time to try it on Tuesday.

Thanks for the replies heehaww.

I have fiddled around with some very simple cases just to see how easy it would be to do harder cases or even derive the general formula.

For T=10 and W=2, all the probabilities are fairly easy to derive by hand (meaning deriving a formula by hand). I find that if we observe S=2, then the most likely B is 10 but the expected B is 8. Here's another one: if we observe S=7, then the most likely B is 3 but the expected B is 3.99.

Anyway, I'll try to baby-step up to T=10 & W=3 and see how that goes.

The probability mass function of the number of spins S needed to reach W winners if there are T total slots and B unique bettors (one unique number for each bettor) for the case of W=2 is fairly straightforward to derive.

There is one formula for the case of B=T and one formula for the case B<T.

If B=T, then Prob(S=s | T, W=2, and B=T) = P(B,2)/(T^s) for s>=2 where P(x,y) is the permutation function.

If B<T, then Prob(S=s | T, W=2, and B) is given by:

{Sum[M goes from 0 to s-2] C(s-1,M) * ((T-B)^M)} * P(B,2)/(T^s) for s>=2 and where C(x,y) is the choose (combination) function and P(x,y) is the permutation function as above.

In the next post I will present the formula(s) for the case of W=3 which is very similar.

As promised, the probability mass function of the number of spins S needed to reach W winners if there are T total slots and B unique bettors (one unique number for each bettor) for the case of W=3 is also fairly straightforward to derive.

There is one formula for the case of B=T and one formula for the case B<T.

If B=T, then Prob(S=s | T, W=3, and B=T) = [2^(s-2) - 1] * P(B,3)/(T^s) for s>=3 where P(x,y) is the permutation function.

If B<T, then Prob(S=s | T, W=3, and B) is given by:

{Sum[M goes from 0 to s-3] C(s-1,M) * ((T-B)^M) * [2^(s-2-M) - 1]} * P(B,3)/(T^s) for s>=3 and where C(x,y) is the choose (combination) function and P(x,y) is the permutation function as above.

Unfortunately, these formulas do not easily generalize since, for example, I am looking into the case of W=4 which is more complex.

I had a breakthrough when I dug deeper into the case of W=4. It turns out that these probability mass functions can be written in terms of coefficients called "Stirling numbers of the second kind". Neato.

Here is the probability mass function of the number of spins S needed to reach W winners if there are T total slots and B unique bettors (one unique number for each bettor) for the case of W=4.

There is one formula for the case of B=T and one formula for the case B<T.

If B=T, then Prob(S=s | T, W=4, and B=T) = S(s-1,3) * P(B,4)/(T^s) for s>=4 where S(n,k) is the Stirling number of the second kind (I apologize for using so much S notation but that is the standard usage) and P(x,y) is the permutation function.

If B<T, then Prob(S=s | T, W=4, and B) is given by:

{Sum[M goes from 0 to s-4] C(s-1,M) * ((T-B)^M) * S(s-1-M,3)} * P(B,4)/(T^s) for s>=4 and where C(x,y) is the choose (combination) function, S(n,k) is the Stirling number of the second kind, and P(x,y) is the permutation function as above.

Note that the two earlier formulas (for W=2 and W=3 respectively) can also be written in terms of Stirling numbers since S(n,1) = 1 for all n>=1 and S(n,2) = 2^n - 1 for all n>=2. For those interested, the S(n,3) sequence is 1, 6, 25, 90, 301, 966, 3025, 9330, etc. and corresponds to the probabilities of getting the requisite number of duplicate numbers in our roulette wheel problem.

So I think these formulas can indeed be generalized to any W by simply changing the second number in the expression for the Stirling number, the second number in the permutation expression, and the upper limit of the summation in the obvious way.

I am sure that someone (BruceZ and others) have derived these formulas before, but it is kinda neat to come up with such an interesting formula.

Anyway, to complete the journey, these probability mass functions can be used in Bayes theorem to derive the "most likely" and/or the expected value of B, the number of unique bettors, given that you observe S (and already know T and W). Based upon that information, you can come up with a reasonable guess for your underlying probability of winning any round of the roulette wheel game.

Edit: It turns out that these Stirling numbers are integrally related to the general coupon collector problem via our old friend the principle of inclusion-exclusion.

Nice work.

So then something about this problem is analogous to counting the number of ways to distribute labeled balls into an exact number of indistinguishable boxes, such that no box may be empty but they may vary in number of balls. A relation like this doesn't surprise me, because this type of problem is Multinomial and multinomial coefficients are also related to partitions.

I agree that it's neat and now I'm eager to get a chance to play with this myself.