What to do when a probability problem becomes unwieldy to check via simulation?

114 Views Asked by At

I am assuming that some probability problems cannot be solved easily since there may be a lot of cases to handle and it would make miscounting likely. However, some problems do not simulate well on a computer because of the huge number of possible outcomes. For example, in a standard $52$ card deck, if we choose $26$ cards, there are almost $500$ trillion card combinations and if we add in $2$ joker cards and choose $27$ instead, the # of card combinations = almost $2$ quadrillion (which is interestingly almost $4$ times as many as $52 \choose 26$).

So my question is if you come across a difficult counting problem, even if you "sweat it out" by hand, how do you check the answer if simulation would take way too much time? For example, using a $54$ card deck (containing $2$ jokers), how many $27$ card hands contain $1$ or more jokers, at least two $7$ card flushes, at least one $10$ card straight, and exactly one set of quads (such as K,K,K,K)? You don't have to actually compute the answer as I am just trying to come up with a difficult to simulate counting problem. I didn't spend much time coming up with this example so I don't really know how hard it is to solve but I would think with the huge number of possible outcomes it might be a "bear" to count correctly.

Note that a joker can count as any "missing" card we need to make a "winner". For example, if all the conditions above are met except there is no quad (K,K,K,K for example) but we have a triple (K,K,K for example), the joker can be used to satisfy that missing K thus making a "winner" combo.

What makes this problem seem very difficult to me is that there could be 2 jokers and either one could satisfy any missing requirement and even count for multiple missing requirements at the same time. For example, if we only get $1$ joker but have $2$ requirements unmet and it just so happens that joker can fulfill both since we can make the joker any card we want that is not already in the hand. An example would be we are missing a 4th King and that same King also completes the 2nd flush.

Assume the $54$ card deck is well shuffled and each card is equally likely to be drawn from it for any $27$ card draw.

Note that the flushes can be longer than $7$ and the straight can be longer than $10$ as long as those minimum requirements are met. Also a straight flush of length $10$+ would satisfy both requirements for a flush of length $7$ and a straight of length $10$.

Even if someone came up with an answer to this problem, how would it be checked for accuracy?

1

There are 1 best solutions below

0
On

There are a number of advanced methods for dealing with excessive variance in simulation output. In your case, you are going to get a lot of hands that do not satisfy your criteria, hence it will take a lot of simulations to get the correct ratio of successes to failures. Two techniques come to mind to address this...neither of which are "plug and chug" type cookbook procedures...you'll still have to think!

They are Importance Sampling and Stratified Sampling. Both of these techniques essentially bias the simulation towards the region of the sample space most likely to generate "hits". Then, the results are de-biased to get the estimate. The tricky part is determining how to bias your simulation to achieve a reduction in sampling variance.