The solutions to some gambling problems are difficult to believe either because they’re counterintuitive or because they’re difficult to analyze. In both cases, simulation gives us a comforting answer.
The Monty-Hall Problem is difficult to believe because it goes against psychological biases. Intelligent and knowledgeable people often guess wrongly. Why should an outcome depend on some seemingly irrelevant information we receive? The solution is obvious in one sense: if we act on that information, we double our chances of winning. In another sense, though, the solution defies intuition, and that makes the problem surprising and entertaining.
The double dixie-cup problem is difficult to analyze, as we can see from the online reference, The Coupon Collector's Problem, M. Ferrante, M. Saltalamacchia, 2014. That reference refers, in turn, to D. J. Newman, L. Shepp, The double dixie cup problem, American Mathematical Monthly, 67:58-61, 1960. This problem addresses the question of how many samples we must take to get a complete set of outcomes. To get an actionable answer, we can slog through the mathematics, or we can simulate. In fact, after slogging through the mathematics, the reference seals the deal with a simulation anyway. In this case, the solution is hard to believe because it’s difficult to analyze. Simulation is more comforting than reasoning in this case, at least for me.
The Monty-Hall Problem is difficult to believe because it goes against psychological biases. Intelligent and knowledgeable people often guess wrongly. Why should an outcome depend on some seemingly irrelevant information we receive? The solution is obvious in one sense: if we act on that information, we double our chances of winning. In another sense, though, the solution defies intuition, and that makes the problem surprising and entertaining.
The double dixie-cup problem is difficult to analyze, as we can see from the online reference, The Coupon Collector's Problem, M. Ferrante, M. Saltalamacchia, 2014. That reference refers, in turn, to D. J. Newman, L. Shepp, The double dixie cup problem, American Mathematical Monthly, 67:58-61, 1960. This problem addresses the question of how many samples we must take to get a complete set of outcomes. To get an actionable answer, we can slog through the mathematics, or we can simulate. In fact, after slogging through the mathematics, the reference seals the deal with a simulation anyway. In this case, the solution is hard to believe because it’s difficult to analyze. Simulation is more comforting than reasoning in this case, at least for me.
Warm-up: Monty-Hall Problem
Warm-up: Monty-Hall Problem
You get to choose door 1, 2, or 3. Without loss of generality, assume that the prize, a car, is behind door 1, and goats are behind doors 2 and 3. Monty knows this, but you don’t. Monty is obliged to show you a goat after you tell him your first choice. After Monty shows you a goat, you have the option to stick with your original choice or to switch. Many people will say “stick” or will say that it doesn’t matter whether you switch or stick. But it does matter. You double your chances of winning by switching.
If you choose door 1, Monty will show you door 2 or 3 at random. If you choose 2, Monty shows you . If you choose 3, Monty shows you . If you chose 1 and you switch, then you will choose , that is either 2 or 3 and you lose. If you chose either 2 or 3 and you switch, then, of course, you will choose neither 2 nor 3 and you win. By switching, you avoid your first choice, which happens to be a goat, and you avoid Monty’s choice, which is always a goat. By switching, you win in two of three possible outcomes.
5-2=3
5-3=2
5-Monty
Analyzed like that, it’s obvious that you’re twice as likely to win if you switch. However, this is hard to believe without a simulation. At least it’s hard for me, even though the proof is clear as a bell. So let’s simulate it.
In[]:=
ClearAll[firstChoice,montyChoice,secondChoice];firstChoice[]:=RandomInteger[{1,3}];montyChoice[yourFirst_]:=If[yourFirst===1,RandomInteger[{2,3}],(*else*)5-yourFirst];secondChoice[yourFirst_,montyChoice_,switchQ_]:=If[switchQ,Switch[yourFirst,1,5-montyChoice,2,1,3,1],yourFirst];
In[]:=
ClearAll[round];round[switchQ_]:=With[{f=firstChoice[]},With[{m=montyChoice[f]},secondChoice[f,m,switchQ]]];
Let’s do trials where you switch. times, you get the prize. times, you get goat #2. times, you get goat #3.
300000
200000
50000
50000
In[]:=
Histogram[Table[round[True],{300000}],{0.5,3.5,1}]
Out[]=
Now, you don’t switch. times you get the prize. times you get goat #2. times you get goat #3.
100000
100000
100000
In[]:=
Histogram[Table[round[False],{300000}],{0.5,3.5,1}]
Out[]=
Double-Dixie-Cup Problem
Double-Dixie-Cup Problem
The reference is thorough, covering many generalizations. My problem is a concrete instance. I’d call my instance The Test-Coverage Problem.
For memory training, I generate two-digit numbers from 00 through 99 from a uniform distribution, sampling with replacement. For fun, I get my numbers from rolling a pair of ten-sided gamer’s dice.
I notice that I get many duplicates. For instance, in one run of 72 pairs to memorize, I got five copies of 47. This makes my sequence of 72 numbers easier to remember, but it also leaves many untested numbers. I need to hit every number in at least once to thoroughly exercise my memory system.
[0¨99]
In industrial applications, we often test software or machinery by generating random inputs. Duplicates don’t enhance test coverage. We actually need to roll enough times to be reasonably sure we get every possible input. That raises the question “how many rolls do I need for a better than chance of hitting every outcome in ?” Let’s answer the question with a simulation.
p
[0¨99]
Roll, here, generates random outcomes.
n
In[]:=
ClearAll[roll];roll[n_]:=RandomInteger[{0,99},n];
With 100 rolls, we get many gaps and multiplicates. 100 is obviously the minimum number than has any chance at all of hitting every outcome.
In[]:=
ListPlot[Tally[roll[100]],Filling->Axis]
Out[]=
With rolls, we (typically) don’t get any misses.
1000
In[]:=
ListPlot[Tally[roll[1000]],Filling->Axis]
Out[]=
What is the probability of “no gaps” versus number of rolls? First, let’s detect whether an experiment has no gaps.
In[]:=
ClearAll[noGaps];noGaps[n_]:=Length[Tally[roll[n]]]===100;
In[]:=
noGaps[100]
Out[]=
False
In[]:=
noGaps[1000]
Out[]=
True
Now, given a sequence of rolls, each of size , what fraction have no gaps?
m
n
In[]:=
ClearAll[noGapFraction];noGapFraction[m_,n_]:=Module[{noGapCount=0,i},For[i=1,i<=m,i++,If[noGaps[n],noGapCount++]];N[noGapCount/m]];
In trials of 100 rolls, we (almost) never get a no-gap trial.
100000
In[]:=
noGapFraction[100000,100]
Out[]=
0.
In trials of 500 rolls, a little more than half of them have no gaps.
100000
In[]:=
noGapFraction[100000,500]
Out[]=
0.50709
Plot the no-gap fraction versus the number of rolls in trials of . This is a little slow, but tolerable. At a trial-size of , it’s painfully slow, but not more informative.
100000
1000000
I think this is a pretty good answer. To have a better than 50% chance of getting at least one no-gap run, we need about 500 rolls in a trial. To have a better than 90% chance, we need around 700 rolls. Incidentally, this curve is very pretty and most certainly has an analytical form, if we could find it.
In[]:=
ListLinePlot[Table[{m,noGapFraction[100000,m]},{m,100,1000,50}],Frame->True,GridLines->Automatic,FrameLabel->{{"No-gap Fraction",""},{"Number of Rolls","No-Gap Fraction in 100000 Trials vs. Number of Rolls per Trial"}}]
Out[]=
Validation
Validation
It’s interesting to validate the simulation against the reference. An anonymous person pointed me to the integral on page 23 in Section 5.
telling us the expected number of rolls (the “time”) before we get a no-gap set is about 519, consistent with our simulation that predicts a better than even chance of a no-gap set after about 500 rolls.
CITE THIS NOTEBOOK
CITE THIS NOTEBOOK
Monte Carlo gambling and test coverage
by Brian Beckman
Wolfram Community, STAFF PICKS, February 7, 2025
https://community.wolfram.com/groups/-/m/t/3382384
by Brian Beckman
Wolfram Community, STAFF PICKS, February 7, 2025
https://community.wolfram.com/groups/-/m/t/3382384