2
$\begingroup$

I apologize in advance if this is a duplicate, I suspect it must be but I don't know how to search for it.

Imagine you play a game 7 times; each time you add your score. The number of ways to get a particular score (the numerator of the probability fraction) is displayed below:

$$ \begin{array}{cccc} \begin{array}{c|c} \text{Score} & \text{Combos} \\ \hline 1 & 720 \\ 2 & 1080 \\ 3 & 1792 \\ 4 & 3648 \\ 5 & 7176 \\ \hline \\ \end{array} & \begin{array}{c|c} \text{Score} & \text{Combos} \\ \hline 6 & 11136 \\ 7 & 17040 \\ 8 & 26460 \\ 9 & 40104 \\ 10 & 50776 \\ \hline \\ \end{array} & \begin{array}{c|c} \text{Score} & \text{Combos} \\ \hline 11 & 59016 \\ 12 & 60660 \\ 13 & 55800 \\ 14 & 40592 \\ 15 & 24284 \\ \hline \\ \end{array} & \begin{array}{c|c} \text{Score} & \text{Combos} \\ \hline 16 & 10968 \\ 17 & 3328 \\ 18 & 776 \\ 19 & 80 \\ 20 & 4 \\ \hline \text{Total} & 415440 \end{array} \end{array} $$

I know how to compute the $EV$; $EV = 11.091555$.

How would you calculate the probability of getting less than some particular total score $n$? Is the EV enough? I don't need the answer, just the procedure is enough.

Update:

  • The runs are completely independent.
  • I need to calculate the probability for various $50 \leq n \leq 80$
$\endgroup$
  • $\begingroup$ I would run a simulation. $\endgroup$ – André Nicolas May 15 '14 at 16:39
  • $\begingroup$ @AndréNicolas Monte carlo? $\endgroup$ – durron597 May 15 '14 at 16:40
  • 3
    $\begingroup$ Yes, simulate $100000$ plays of $7$ games, and you will have enough information for all practical purposes. In the good old days, one could go have coffee while the simulation ran. Now it is too fast for that. $\endgroup$ – André Nicolas May 15 '14 at 16:50
  • 2
    $\begingroup$ Andre, you can always just run a more involved simulation (more trials, or compute some other intermediate results) if you want a coffee break. $\endgroup$ – Michael Lugo May 15 '14 at 16:59
4
$\begingroup$

We may also use probability generating functions:

$P(x)=\left(4 \, x^{20} + 80 \, x^{19} + 776 \, x^{18} + 3328 \, x^{17} + 10968 \, x^{16} + 24284 \, x^{15} + 40592 \, x^{14} + 55800 \, x^{13} + 60660 \, x^{12} + 59016 \, x^{11} + 50776 \, x^{10} + 40104 \, x^{9} + 26460 \, x^{8} + 17040 \, x^{7} + 11136 \, x^{6} + 7176 \, x^{5} + 3648 \, x^{4} + 1792 \, x^{3} + 1080 \, x^{2} + 720 \, x\right)/415440$

and the probability can be calculated from $P(x)^7$

E.g. for a score less than $n=61$, summing the coefficients of the terms $x^7\ldots x^{60}$ in the above polynomial gives $\displaystyle \frac{844291674672075639073225007734969}{65179080904297424559820836480000000}\approx 0.0129534148527156$

As an aside, the expected value can also be calculated from the p.g.f,

$\displaystyle P'(1)=\frac{1151969}{103860}\approx 11.0915559406894 $

$\endgroup$
2
$\begingroup$

The EV is not enough for less than some particular score, but it can give you a bound (via the Markov inequality, which says that $P[X \geq c] \leq E[X]/c$ (this upper bounds the probability the total score is greater than $n$).

The answer is that the probability when k games are played (in this case, $k=7$) is $P(\text{total score} \leq n) = \sum_{i=0}^n \sum_{x_1+x_2+\ldots+x_k=i, x_i \geq 1, x_i \in \mathbb{Z}} P(\text{game 1 score = } x_1 \cap \text{game 2 score = } x_2 \cap \ldots \cap \text{game k score = } x_k)$. If the runs are independent, then the probability becomes a product, which is still not nice. If $n$ is small though, this approach may be feasible.

The inner sum has $\binom{k-1}{i-1}$ terms, so there are $\sum_{i=0}^n \binom{k-1}{i-i}$ terms in this sum, which is not nice. Simulating it would likely be easier.

$\endgroup$
  • $\begingroup$ Thanks! FYI, I edited my post to answer some of the questions you identify as unanswered here. $\endgroup$ – durron597 May 15 '14 at 16:54
  • $\begingroup$ In this case, I'd suggest Monte Carlo as well. The annoying thing is, even though the runs are independent, $P(\text{game i score} = x_i)$ is a bit annoying to calculate, even when you multiply both sides by $(#\text{ of combos})^k$ so you replace $P$ with " number of combos" on both sides and still the # of combos becomes a product. $\endgroup$ – Batman May 15 '14 at 17:04
1
$\begingroup$

Per the advice in this thread, I ran a simulation with 10,000,000 trials. It took only a few seconds, not enough for coffee. Here are the results:

$$ \begin{array}{cccc} \begin{array}{c|c} \text{Score} & \text{Times} \\ \hline 33 & 1 \\ 35 & 1 \\ 36 & 2 \\ 37 & 2 \\ 38 & 2 \\ 39 & 4 \\ 40 & 13 \\ 41 & 9 \\ 42 & 23 \\ 43 & 53 \\ 44 & 79 \\ 45 & 129 \\ 46 & 199 \\ 47 & 314 \\ 48 & 462 \\ 49 & 791 \\ 50 & 1089 \\ 51 & 1625 \\ 52 & 2459 \\ & \\ \end{array} & \begin{array}{c|c} \text{Score} & \text{Times} \\ \hline 53 & 3687 \\ 54 & 5185 \\ 55 & 7505 \\ 56 & 10323 \\ 57 & 14374 \\ 58 & 19584 \\ 59 & 26890 \\ 60 & 35304 \\ 61 & 46301 \\ 62 & 60692 \\ 63 & 77926 \\ 64 & 98238 \\ 65 & 122342 \\ 66 & 150361 \\ 67 & 182853 \\ 68 & 218069 \\ 69 & 256349 \\ 70 & 298477 \\ 71 & 340846 \\ & \\ \end{array} & \begin{array}{c|c} \text{Score} & \text{Times} \\ \hline 72 & 384231 \\ 73 & 424468 \\ 74 & 462215 \\ 75 & 494474 \\ 76 & 519681 \\ 77 & 537268 \\ 78 & 544470 \\ 79 & 543348 \\ 80 & 529893 \\ 81 & 509777 \\ 82 & 477961 \\ 83 & 440529 \\ 84 & 397553 \\ 85 & 349523 \\ 86 & 301595 \\ 87 & 254746 \\ 88 & 208387 \\ 89 & 168148 \\ 90 & 131310 \\ & \\ \end{array} & \begin{array}{c|c} \text{Score} & \text{Times} \\ \hline 91 & 100616 \\ 92 & 74686 \\ 93 & 53593 \\ 94 & 37876 \\ 95 & 26259 \\ 96 & 17534 \\ 97 & 10996 \\ 98 & 6855 \\ 99 & 4158 \\ 100 & 2487 \\ 101 & 1321 \\ 102 & 724 \\ 103 & 403 \\ 104 & 195 \\ 105 & 93 \\ 106 & 34 \\ 107 & 17 \\ 108 & 9 \\ 109 & 3 \\ 110 & 1 \\ \end{array} \end{array} $$

Here is a link to the code (in Java), if you want to run something similar, although ideone doesn't like how long 10,000,000 takes to run, so I reduced it to 1,000,000 trials.

$\endgroup$
  • $\begingroup$ Your simulation's close to the exact values, e.g. for n=91,92,93 the exact answer's about 0.0100288259961418, 0.00745276572017888, 0.00538935761020590 respectively. $\endgroup$ – gar May 15 '14 at 18:00

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.