6
$\begingroup$

Let's say I'm simulating the result of a tournament where 4 teams play each other, for a total 6 games. They get, say, 1 point for winning and 0 points for loosing.

I want to get a sense of the end distribution. For example, the probability that team B finishes at least third.

The sample space is finite and is a list of possible wins and losses for each team, or alternatively, the sequence of results of each game. (The sample space can also be taken to be the points for each team, if that makes things easier)

I assume games are independent and construct a matrix of probabilities of outcomes between teams (e.g. team A wins with probability 70% over team B). I then use these probabilities to draw (probabilistically) from each game, which ends up giving me a draw from the end distribution (the final results).

As the $n$ in the number of draws goes up, I hope that I can approximate the true distribution (and answer questions such as "what's the probability that team C has more than $X$ points").

Three questions

  1. Is this a Monte Carlo simulation / a naive way of drawing from a distribution?

  2. What is the relevant convergence concept that tells me that as the number of draws goes to infinity, my draws converge in (say) distribution to the true distribution?

  3. What are the assumptions needed for convergence? What in this setup would make this simulation not converge?

As always, thanks for your time!

$\endgroup$
  • $\begingroup$ Rather than use a simulation, why not solve the problem directly? $\endgroup$ – whuber Aug 31 '17 at 19:59
  • $\begingroup$ @whuber the sample space of my problem is really huge, I don't think it's feasible in computing terms $\endgroup$ – cd98 Sep 5 '17 at 16:52
  • 1
    $\begingroup$ Evidently, then, your problem is not about four teams playing six games. What is it really about? $\endgroup$ – whuber Sep 5 '17 at 16:55
4
+25
$\begingroup$
  1. Is this a Monte Carlo simulation / a naive way of drawing from a distribution?

    Yes, this is a Monte Carlo simulation. There's nothing wrong with this tactic.

  2. What is the relevant convergence concept that tells me that as the number of draws goes to infinity, my draws converge in (say) distribution to the true distribution?

    You're looking for the Law of Large Numbers, which says that for any individual event $E_i$ and its probability $p_i$, the estimator $\hat p_i \equiv x_i/n_i$ converges to the true value ($x_i$=number of trials where $E_i$ occurs, $n_i$ = number of trials total).

    The variance of your estimator is $p_i (1-p_i) / n$. A few more useful convergence results:

    • The Central Limit Theorem says your estimator is asymptotically Gaussian with that variance. (Since the variance goes to 0, it's more precise to say that $\sqrt n\hat p_i$ has a limiting distribution that is Gaussian with variance $p_i (1-p_i)$.)
    • The Continuous Mapping Theorem says you can plug your estimate $\hat p_i$ into the variance expression above (in place of $p_i$) and it will converge to the correct variance.
    • Slutsky's Theorem says that you can combine those two results to calculate asymptotic 95% confidence intervals for your estimates as $\hat p_i \pm 1.96*\hat\sigma_n$, where $\hat \sigma_n = \sqrt{\hat p_i (1-\hat p_i) / n}$.
  3. What are the assumptions needed for convergence? What in this setup would make this simulation not converge?

    These convergence results are only approximations: in real life, we don't have infinite samples. This might become a practical problem for you if you have rare events (e.g. if the probability team A wins the tournament is 0.00000001). After 100k runs, your estimate will be zero and your confidence interval will have zero width. This is a huge relative error.

    When you're working with binary data, these results are guaranteed to apply. If you were dealing with quantitative variables, it would be possible to run into situations where the asymptotic results "kick in" slowly or not at all.

Here's a scaffold for how to do the calculations exactly. You have teams A, B, C, D and six games $G_1 ... G_6$. Each game is binary, so you have only 64 possible outcomes. Let $E_j, q_j$ be the event and probability that game $G_j$ goes to the team earlier in the alphabet. The games are independent, so the probability of a particular outcome $E_1 \land E_2 \land \lnot E_3 \dots $ is just the product $q_1q_2(1-q_3)\dots$ et cetera. For a bigger event such as "A wins the tournament", compute a dataframe with one row for every possible tournament outcome. You can use eight columns: one each for the outcomes of the six games, one for the probability, and one for "Did Team A win? (0 if no, 1 if yes)." Then take a dot product of the last two columns (equivalently, sum up the probabilities of the potential tournaments where A wins).

$\endgroup$
  • $\begingroup$ Thanks for your answer. If I understand you correctly, the convergence happens event by event? I thought there would be some convergence in distribution idea. Since the random variable here is discrete, I guess approximating by Event is the same as converging to the full probability distribution, right? (If you can add a reference for this, I'll accept your question) I thought about calculating things exactly, but the sample space was so huge that it wasn't possible. $\endgroup$ – cd98 Sep 5 '17 at 16:51
  • $\begingroup$ Yes, that's correct: it happens event by event, and if you specify any reasonable idea of total error, it will converge because of the pointwise (event-wise) convergence of the estimates. Theoretically, it helps that your state space is finite. My reference of choice is to the multivariate law of large numbers: stat.umn.edu/geyer/5101/notes/n2.pdf $\endgroup$ – eric_kernfeld Sep 8 '17 at 17:54

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.