Am trying to write a program which gives each user in a raffle contest their odds so far at winning.
The rules of the game are simple:
A predefined number of tickets are sold for example 1000 each user can at most buy 50 tickets and a user can only win once in the game after that all his tickets become invalid or pulled out and a new draw begins giving the other users a better chance of winning. The game will have 10 winners only.
With the data collected from the software I would then know how many tickets were sold, the users that bought them and the amount of tickets that each user has. Now I just need a formula or pseudocode that would give each user their statistic probability of winning based on the data acquired, so that it be can used before and after each draw in the game to show each user their odds so far.
I have looked at similar questions asked here, but no one seems to want to address the part that if a person wins the rest of their tickets become invalid. Am not good with probability or understand those fancy notations, so I don't understand is such a thing possible to calculate per user.
Thanks for the help
Update
Testing my understanding of joriki second method: lets say 10 tickets were sold to 4 users each bought A: 1, B: 2, C: 4, D: 3 and there will be 3 prizes given to users. I calculated the total probability of being drawn for each user to be
A = $\frac{1}{10} + \frac{2}{10}*\frac{1}{8}*\frac{1}{6} + \frac{4}{10}*\frac{1}{6}*\frac{1}{2} + \frac{3}{10}*\frac{1}{7}*\frac{1}{4}$ = 0.1482
B = $\frac{1}{10}*\frac{2}{9}*\frac{2}{8} + \frac{2}{10} + \frac{4}{10}*\frac{2}{6}*\frac{2}{2} + \frac{3}{10}*\frac{1}{7}*\frac{1}{4}$ = 0.3817
C= $\frac{1}{10}*\frac{4}{9}*\frac{4}{8} + \frac{2}{10}*\frac{4}{8}*\frac{4}{6} + \frac{4}{10} + \frac{3}{10}*\frac{4}{7}*\frac{4}{4}$ = 0.6603
D= $\frac{1}{10}*\frac{3}{9}*\frac{3}{8} + \frac{2}{10}*\frac{3}{8}*\frac{3}{6} + \frac{4}{10}*\frac{3}{6}*\frac{3}{2} + \frac{3}{10}$ = 0.6500
Their total sum is 1.8403 and not 3 ? also is this considered the total probability of being drawn for the 3 draws or just for the first round of the game with the tickets becoming invalid
$\endgroup$ 43 Answers
$\begingroup$Let $ x_i $ be the number of tickets bought be each of the m people. Suppose n tickets are sold.
Person i has probability $P_{i,1} = x_i/n$ of being the first winner.
Person i has probability $P_{i,2}= (\sum_{j \neq i} P_{j,1}\frac{x_i}{n-x_j})=(\sum_{j \neq i} \frac{x_j}{n}\frac{x_i}{n-x_j}) $ of being the second winner.
$$P_{i,3}=(\sum_{j_p \neq i} \frac{x_{j_1}}{n}\frac{x_{j_2}}{n-x_{j_1}}\frac{x_i}{n-x_{j_1}-x_{j_2}}).$$
For i to be the third winner, you are multiplying the probabilities that i did not win the first 2 times. For each other person, $j_1$ you compute the chance that they were the first winner (already done in part 1,$\frac{x_{j_1}}{n}$ ), then you compute the probability that a second person, $j_2$, won in the second round, given $j_1$ won in the first ($\frac{x_{j_2}}{n-x_{j_1}}$). Finally you multiply by the chance that i wins in the third round, given $j_1$ won in the first and $j_2$ won in the second.
So $$P_{i,k}=(\sum_{j_p \neq i}\prod_{l=1}^{k-1}\bigg[\frac{ x_{j_l}}{n-\sum_{t=1}^{l-1}x_{j_t}}\bigg]\frac{x_i}{n-\sum_{t=1}^{k-1}x_{j_t}})$$
So for person i you must add together these probabilities from 1 to 10 (for 10 winners).
To break this down, you go over each case, multiplying the probabilities that all combinations of previous people won the first round and for each combination you multiply by the chance that person i wins this time, given that particular combination of people won . You add up all theses probabilities, and as I mentioned before multiply by the chance that person i was not selected before.
This formula can be written in a more intuitive way:
P(i wins)=$ \sum_{k=1}^{10} P_{i,k}$
$$P_{i,k}=(\text{probability i loses all prior draws}) \times \sum_{\text{all combinations of k-1 winners from all people except i}} P(\text{i wins kth round} | j_1,j_2,...,j_{k-1} \text{won the first k-1 rounds} ) \times P(j_1,j_2,...,j_{k-1} \text{won the first k-1 rounds}))$$
Let's do an example with 4 people, who bought 1,2,3 and 4 tickets respectively. 3 winners will be drawn.
$P_{i,1}=i/10$ (since person i bought i of the ten tickets).
$P_{1,1}=1/10=.1$
$P_{1,2}=(2/10)(1/8)+(3/10)*(1/7)+(4/10)*(1/6)=.1345$ (probability each other person won round 1 times the probability person 1 wins round 2 given the other person won round 1)
$P_{1,3}=(2/10)[(3/8)(1/5)+(4/8)(1/4)]+(3/10)[(2/7)(1/5)+(4/7)(1/3)]+(4/10)[(2/6)(1/4)+(3/6)(1/3)].2143$
So the probability that person 1 is one of the 3 winners is .1+.1345+.2143=.4488.
Alternatively, it may be easier to compute the probability of each scenario:
Let $W_{a,b,c}$ mean that the winners were, in order a, then b, then c.
So $P(W_{1,2,3})=(1/10)(2/9)(3/7)$.
For a game with m players, and k winners, in order to compute P(player 1 wins), using this method you compute every combination of $P(W_{j_1,j_2,\ldots j_k})$ that contains player 1, and add together those probabilities to find the probability player 1 wins. This seems easier than the method I proposed earlier. The number of computations this takes is: for $P(W_{j_1,j_2,\ldots j_k})$ takes 2k multiplications and n(n+1)/2 additions, and you must add together ${m \choose k-1}$ of them.
In general to compute solve the problem this way,
$P(W_{j_1,j_2,\ldots j_k})=\frac{x_{j_1}}{n}\frac{x_{j_2}}{n-x_{j_1}}\frac{x_{j_3}}{n-x_{j_1}-x_{j_2}}\cdots\frac{x_{j_k}}{n-\sum_{t=1}^{k-1}x_{j_t}}$
P(player i wins) = $\sum P(W_{j_1,j_2,\ldots j_k})$, where at least 1 of the $j_l=i$
$\endgroup$ 2 $\begingroup$I don't think you'll find a closed formula for this. If you're OK with only specifying the odds up to a couple of decimal places, the easiest way to do this would be to simulate the draw a couple of billion times and use the resulting relative frequencies. If you want the exact probabilities instead, you can keep track of all possibilities of who already won and work through one draw at a time. For instance, if $A$, $B$ and $C$ bought $1$, $2$ and $3$ tickets, respectively, and $2$ prizes are being drawn, in the first step $A$ would be drawn with probability $\frac16$, $B$ with probability $\frac26=\frac13$ and $C$ with probability $\frac36=\frac12$. Then in the second step, if $A$ was drawn in the first step, there would be $5$ tickets left, and $B$ would be drawn with probability $\frac25$ and $C$ with probability $\frac35$, and so on. The total probability of being drawn would be $\frac16+\frac26\cdot\frac14+\frac36\cdot\frac13=\frac5{12}$ for $A$, $\frac16\cdot\frac25+\frac26+\frac36\cdot\frac23=\frac{11}{15}$ for $B$ and $\frac16\cdot\frac35+\frac26\cdot\frac34+\frac36=\frac{51}{60}$ for $C$. For debugging your code, you can check to see that they add up to $2$ as they should.
$\endgroup$ 1 $\begingroup$Let $N_i$ be the number of tickets that the $i$-th player bought. Then the total number of possible draws of $m$ tickets is the coefficient of $x^m$ in the polynomial$$ P(x)=\prod_i\left(1-N_i x\right); $$the number of possible draws where the $j$-th player doesn't win is the coefficient of $x^m$ in$$ Q_j(x)=\frac{P(x)}{1-N_j x}=\prod_{i\neq j}\left(1-N_i x\right); $$and the winning probability for the $j$-th player is $1$ minus the ratio of the two coefficients. Because you only need to keep coefficients out to the $m$-th power of $x$ during the calculation, you can compute the exact winning probabilities for all players in time proportional to the number of players and the square of the number of tickets to be drawn.
To demonstrate this (generating function) method for OP's example, where players A,B,C,D buy $1,2,4,3$ tickets respectively:$$ \begin{eqnarray} P(x)&=&(1-x)(1-2x)(1-4x)(1-3x) \\ &=&1 - 10x + 35x^2 - 50x^3 + 24 x^4; \\ Q_A(x)&=&\frac{P(x)}{1-x}=1-9x+26x^2-24x^3; \\ Q_B(x)&=&\frac{P(x)}{1-2x}=1-8x+19x^2-12x^3; \\ Q_C(x)&=&\frac{P(x)}{1-4x}=1-6x+11x^2-6x^3; \\ Q_D(x)&=&\frac{P(x)}{1-3x}=1-7x+14x^2-8x^3. \end{eqnarray} $$What's nice is that these polynomials encode the probabilities of winning for every possible number of tickets. If one ticket is drawn, the probabilities come from the coefficients of $x^1$:$$ p_A = 1-(-9)/(-10) = 1/10, p_B = 1-(-8)/(-10)=1/5, \\p_C=1-(-6)/(-10)=2/5, p_D=1-(-7)/(-10)=3/10, $$which are obviously correct and sum to $1$. If two tickets are drawn, the probabilities come from the coefficients of $x^2$:$$ p_A = 1-26/35=9/35, p_B=1-19/35=16/35, \\p_C=1-11/35=24/35, p_D=1-14/35=3/5; $$these sum to $2$, as they should. Finally from the coefficients of $x^3$, we find the probabilities of winning when three tickets are drawn:$$ p_A=1-(-24)/(-50)=13/25, p_B=1-(-12)/(-50)=19/25, \\p_C=1-(-6)/(-50)=22/25, p_D=1-(-8)/(-50)=21/25, $$which sum to $3$. (And from the coefficients of $x^4$, when four tickets are drawn, each player wins with probability $1-0/24=1$.)
In an actual application, where the number of players was much larger than the number of tickets to be drawn, each polynomial multiplication would be truncated after the $x^m$ term.
$\endgroup$
