8
$\begingroup$

Suppose I am entered into a contest, with the following rules:

  • Every person may get up to 6 entries
  • All the entries will be pooled, and 25% of the entries will be selected to be winners, with a maximum of 25.
  • Each person can only win once, regardless of the number of their entries. If someone's name gets drawn again, it is discarded and a new name drawn.
  • I know how many entries I have (the maximum, 6)
  • I know how many total entries there are, broken down by type of entry
  • I do not know how many of the entries are repeat entries by the same person.

The count of entries by type is as follows:

Type 1: 42 Type 2: 72 Type 3: 119 Type 4: 217 Type 5: 156 Type 6: 178

Is it possible to estimate my odds of winning in this situation? I'm a bit confused by the fact that I can't predict how the early winners will effect my chances, since I don't know how many entries each winner will remove from the pool.

I'm interested in the solution given the data set, but I'm also interested in the proper procedure/algorithm for calculating it.

$\endgroup$
  • $\begingroup$ What do the "types" signify? $\endgroup$ – Macro Jun 1 '12 at 18:23
  • $\begingroup$ @Marco The different types of tickets you can earn. So you can earn lottery ticket types 1 through 6, and 42 people won ticket type 1 $\endgroup$ – Rachel Jun 1 '12 at 18:24
  • $\begingroup$ I have trouble following the sequence of posts because they run from bottom to top. But given the time to the right of the posters name I think i have figured it out. So would someone please tell me if I have this straight. I think whuber's answer can't be right because of the ambiguity between entries and entrants. Rachel's strategy to get worst case and best case scenarios is right but she made a math error by adding percentages when they can be based on different denominators. So if we fix that error we have the right bounds on the solution. $\endgroup$ – Michael R. Chernick Jun 1 '12 at 20:54
  • $\begingroup$ I thought it was odd for Rachel to refer to the best case scenario as the one that gave the highest winning percentage and the worst case the one that gave the lowest. Winning is good right? The last point that i would like clarified: Cardinal states that in this case case 25% of the entrants exceeds 25, so there will only be 25 winners. He gets this by knowing that at least 178 people are entered and of course once the number of entrants exceeds 100 the winner totals is cut off at 25 based on the rules. $\endgroup$ – Michael R. Chernick Jun 1 '12 at 21:06
  • $\begingroup$ @cardinal how did you come up with the number 178? I added all the entries by types to get a total of 784. In the worst case for me as a player everyone got 6 entries and 784/6 = 130.7. So I conclude that there must be at least 130 entrances. This still means the cutoff of 25 applies, but how did you arrive at the higher number? $\endgroup$ – Michael R. Chernick Jun 1 '12 at 21:09
6
$\begingroup$

The possible chances lie between 17.7% and 18.7%.

The worst case occurs when everybody but you has exactly one entry in the lottery: this is a configuration consistent with the data (although unlikely!).

Let's count the number of possibilities in which you do not win. This is the number of ways of drawing $25$ tickets out of the $784-6$ remaining tickets, given by the Binomial coefficient $\binom{784-6}{25}$. (It's a huge number). The total number of possibilities--all of them equally likely in a fair drawing--is $\binom{784}{25}$. The ratio simplifies to $(784-25)\cdots(784-30) / [(784)\cdots(784-5)]$, which is about 82.22772%: your chances of not winning. Your chances of winning in this situation therefore equal 1 - 82.22772% = 17.7228%.

The best case occurs when there are as few individuals involved in the lottery as possible and as many as possible have $6$, and then $5$, etc, tickets. Given that the "gem" counts are $(42, 72, 119, 156, 178, 217)$ (in ascending order), this implies

  • At most $42 = a_6$ people can have $6$ entries each.

  • At most $72-42=30 = a_5$ people can have $5$ entries each.

    ...

  • At most $178-156=22 = a_2$ people can have $2$ entries each.

  • $217-178=39 = a_1$ people have $1$ entry each.

Let $p(\mathbf{a}, l, j)$ designate the chance of winning when you hold $j$ (between $1$ and $6$) tickets in a lottery with data $\mathbf{a}=(a_1,a_2,\ldots,a_6)$ and $l=25$ draws. The total number of tickets therefore equals $1 a_1 + 2 a_2 + \cdots + 6 a_6 = n$. Consider the next draw. There are seven possibilities:

  1. One of your tickets is drawn; you win. The chance of this equals $j/n$.

  2. Somebody else's tickets are drawn. The chance of this equals $(n-j)/n$. If they hold $i$ of them, then all $i$ tickets are removed from the lottery. If $l \ge 1$, drawing continues with the new data: $l$ has been decreased by $1$ and $a_i$ has been decreased by $1$ as well. The chance that some person with $i$ tickets in the lottery is chosen, given that yours are not, equals $ia_i/(n-j)$. This gives six disjoint possibilities for $i=1,2,\ldots,6$.

We add these chances because they partition all outcomes with no overlap.

The calculation continues recursively down this probability tree until all the leaves at $l=0$ are reached. It's a lot of computation (about $25^6$ = 244 million calculations), but it only takes a few minutes (or less, depending on the platform). I obtain 18.6475% chances of winning in this case.

Here's the Mathematica code I used. (It is written to parallel the preceding analysis; it could be made a little more efficient through some algebraic reductions and tests for when $a_i$ is reduced to $0$.) Here, the argument a does not count the $j$ tickets you hold: it gives the distribution of counts of tickets everyone else holds.

p[a_, l_Integer, j_Integer] /; l >= 1 := p[a, l, j] = Module[{k = Length[a], n},
    n = Range[k] . a + j;
    j/n + (n - j)/n ParallelSum[
       i a[[i]] / (n - j) p[a - UnitVector[k, i], l - 1, j], {i, 1, k}]
    ];
p[a_, 0, j_Integer] := 0;
(* The data *)
a = Reverse[Differences[Prepend[Sort[{42, 72, 119, 217, 156, 178}], 0]]];
j = 6; l = 25;
(* The solution *)
p[a - UnitVector[Length[a],j], l, j] // N

As a reality check, let us compare these answers to two naive approximations (neither of which is quite correct):

  1. 25 draws with 6 tickets in play should give you around 6*25 out of 784 chances of winning. This is 19.1%.

  2. Each time your chance of not winning is about (784-6)/784. Raise this to the 25th power to find your chance of not winning in the lottery. Subtracting it from 1 gives 17.5%.

It looks like we're in the right ballpark.

$\endgroup$
  • 1
    $\begingroup$ I like this problem because it provides a real example of two kinds of uncertainty: probabilistic uncertainty in the lottery and lack of knowledge about the true distribution of ticket ownership within the lottery. I have effectively treated the latter uncertainty using interval analysis, which simply attempts to bound the possibilities as tightly as possible. Others might go ahead and adopt some prior distribution to describe this epistemic uncertainty, but I can conceive of no valid way to justify any such prior given the information at hand. $\endgroup$ – whuber Jun 1 '12 at 21:21
  • $\begingroup$ But you are assuming that no one can have 2 or more of any particular type ticket ("gem"). As far as I can see this is not specified in the OPs (agent86s) description of the problem. $\endgroup$ – Michael R. Chernick Jun 1 '12 at 21:53
  • $\begingroup$ @Michael You're right, it's not perfectly clear in the game rules, although it is strongly implied that nobody collects more than one of each type of gem. Vide rule 1 in the original question: "every person may get up to 6 entries." $\endgroup$ – whuber Jun 1 '12 at 21:55
  • 1
    $\begingroup$ As far as I am aware (and has been demonstrated during the contest), the assumption from the given information is correct - no one person can have more than 6 entries, one of each "type." $\endgroup$ – agent86 Jun 1 '12 at 21:57
  • 1
    $\begingroup$ Thank you so much for taking the time to answer this! I've been thinking of this problem since yesterday, and woke up this morning determined to figure out this if it killed me, and I'm happy to see a great explanation already posted so now I don't have to :) $\endgroup$ – Rachel Jun 2 '12 at 16:45
1
$\begingroup$

If I did the math right, you have between 19.43% and 21.15% chance of winning a prize

The 19.43% is the best-case scenario, where every entrant has 6 tickets

The 21.15% is the worst-case scenario, where every entrant has 1 ticket except you

Both scenarios are extremely unlikely, so your actual odds of winning probably fall somewhere in between, however a roughly 1/5 chance at winning seems like a fairly solid number to go by

The details on how those numbers were obtained can be found in this Google spreadsheet, however to summarize how they were obtained:

  1. Start with Total # of Entries (784) and Your Entries (6)
  2. Get chance at winning (6 / 784 = 0.77%)
  3. Subtract 6 for best-case, or 1 for worst-case from TotalEntries
  4. Get chance of winning (6/778 for best case 6/783 for worst case)
  5. Repeat steps 3-4 until you have 25 percentages
  6. Add the 25 percentages together to find out your overall chance at winnning something

Here's an alternative way to get the approximate percentage that is simpler, but is not as accurate since you are not removing duplicate entries every time you draw a winner.

6 (your tickets) / 784 total tickets = 0.00765
0.00765 chance to win * 25 prizes = 19.14 % chance to win

EDIT: I'm fairly sure I'm missing something in my math and that you cannot simply add percentages like this (or multiply percent chance to win by # of prizes), although I think I'm close

Whobar's comment gives a 17.4% chance of winning, although I still need to figure out the formula he gave and make sure it's accurate for the contest. Perhaps a weekend project :)

$\endgroup$
  • $\begingroup$ I'll just point out that this assumes that you have 6 gems. $\endgroup$ – murgatroid99 Jun 1 '12 at 18:20
  • $\begingroup$ @murgatroid99 Yes, the question stated I know how many entries I have (the maximum, 6) :) I can make the spreadsheet editable by anyone who wants to figure out their odds of winning $\endgroup$ – Rachel Jun 1 '12 at 18:21
  • 2
    $\begingroup$ I think these figures are in the right ballpark generally, but are off by a couple percent. It's difficult to tell since a description of the calculation you've done hasn't been provided in the post itself. $\endgroup$ – cardinal Jun 1 '12 at 18:51
  • 1
    $\begingroup$ From your description, it appears the discrepancy likely arises from the fact that you haven't incorporated the probability of getting to the $k$th step before getting chosen. For example, in the worst case scenario, the probability of being selected at the third draw is $(778\cdot 777\cdot 6)/(784 \cdot 783 \cdot 782)$. $\endgroup$ – cardinal Jun 1 '12 at 19:18
  • 2
    $\begingroup$ Rachel, $1-\frac{\binom{n-6}{25}}{\binom{n}{25}}$ gives the chance that a person with $6$ tickets among $n$ will have at least one of them chosen when 25 are drawn. (It is based on counting how many ways that person's tickets could not be drawn, dividing by the total number of possible draws, and subtracting that ratio from $1$.) For $n=784$ the value is 17.7%. I don't know whether this is how the lottery is intended to be run, though. $\endgroup$ – whuber Jun 1 '12 at 19:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.