15
$\begingroup$

I have been asked in a Quant interview to estimate the value of $\pi$ using dice. I don't know even how to start with. Any help would be appreciated.

Thanks.

$\endgroup$
5
  • 7
    $\begingroup$ Arrange 100 dice in a circle, find how many dice are needed to make a line from the center to the edge, then divide 100 by $2$ times this number. $\endgroup$ Apr 6, 2014 at 19:18
  • $\begingroup$ That sounds like an awesome problem! $\endgroup$
    – user132181
    Apr 6, 2014 at 19:19
  • $\begingroup$ On a more serious note, you could probably roll enough dice in trials to simulate a randomc variable whose distribution is approximately normal, then use something like the Gaussian integral. $\endgroup$ Apr 6, 2014 at 19:26
  • 1
    $\begingroup$ Well... you could use a round dice... :-) $\endgroup$
    – Lucian
    Apr 6, 2014 at 19:57
  • $\begingroup$ Related problem: Buffon's needle problem. Note: It does not involve dice, but it is related. $\endgroup$
    – glebovg
    Apr 6, 2014 at 21:24

6 Answers 6

16
$\begingroup$

Each die roll generates $2.58$ bits of entropy, and a sequence of die rolls can generate a uniformly distributed random real number in $[0,1]$ to any desired degree of precision. (For example, consider the die rolls to be a sequence of base-6 digits, where a roll of 6 represents a 0 digit.)

Generate two such random numbers, $x$ and $y$, appending digits to each until there are enough digits in both numbers to establish with certainty whether $x^2+y^2 < 1$ or $x^2+y^2>1$. (Equality occurs with probability $0$ and can be disregarded.) If $x^2+y^2<1$, add a tally to the "in" column; otherwise add a tally to the "out" column.

After generating a $n = \mbox{in}+\mbox{out}$ such pairs, and so accumulating a total of $n$ tallies, we have $$\pi\approx 4\frac{\mbox{in}}{\mbox{in}+\mbox{out}}.$$

The idea here is that $x$ and $y$ determine a random point in the square $[0,1]^2$ that is uniformly distributed. The area of the quarter-circular region $x^2+y^2<1$ is $\frac\pi4$, and so a uniformly selected point in the square will lie in that region with probability $\frac\pi4$.

$\endgroup$
5
  • $\begingroup$ Do we need to use cubic die? Icosahedrons (with 2 faces labelled with the same number) would be much easier without having to change bases. $\endgroup$
    – A. Napster
    Apr 7, 2014 at 0:13
  • $\begingroup$ The question says dice. When not qualified, that almost always means standard cubical dice. $\endgroup$
    – MJD
    Apr 7, 2014 at 0:16
  • $\begingroup$ Also, you don't have to change bases. There are at least two ways to avoid this. You can do the arithmetic entirely in base 6 since $x^2+y^2<1$ is just as clear in base 6 as in base 10. Or you can represent $x$ and $y$ as rational numbers; a die roll of $k$ adds $\frac {k-1}{6^i}$ to the rational number. $\endgroup$
    – MJD
    Apr 7, 2014 at 12:59
  • 1
    $\begingroup$ Alternatively you could roll the dice in pairs to generate decimal digits: Doubles don't count and are rerolled. A roll of 1–2, 1–3, or 1–4 is the digit 0. A roll of 1–5, 1–6, or 2–1 is the digit 1. A roll of 2–3, 2–4, or 2–5 is the digit 2. And so on up to digit 9, which is a roll of 6–3, 6–4, or 6–5. $\endgroup$
    – MJD
    Apr 7, 2014 at 13:02
  • 2
    $\begingroup$ Further questions that may be interesting: How many dice rolls does this method take to get to the value of $\pi$ with a certain precision and confidence? And is this optimal? $\endgroup$ Apr 8, 2014 at 1:38
3
$\begingroup$

Let $N$ be the number of dice thrown randomly over a square of area $R\times R$. The largest circle inscribed has area $\pi R^2/4$. Let $N=R\times R$. The number of darts that fall inside the circle is the area of the circle: $N_{in}=\pi R^2/4$, i.e., $$\pi=\dfrac{4N_{in}}{N}$$ Edit What I did seems almost in parallel to http://www.cs.cornell.edu/courses/cs100j/2004sp/Notes/h0506.pdf, and hence I will cite it here as a reference.

$\endgroup$
3
  • $\begingroup$ Just to be clear, you are proposing to physically throw the dice onto a square of area $R^2$ and count how many lie inside the circle? $\endgroup$
    – MJD
    Apr 6, 2014 at 19:28
  • 7
    $\begingroup$ Dice = darts? $ $ $\endgroup$
    – Did
    Apr 6, 2014 at 19:28
  • $\begingroup$ @Sanath: Main aim is to use some property of dice like probability of any face showing up is 6 or sth like that. In the solution you provided, it doesn't matter if it's a die or some dart. Hope you understood my point. $\endgroup$ Jun 3, 2014 at 14:39
3
$\begingroup$

Suppose the die is a 1-inch cube. Draw a bunch of parallel lines spaced 1-inch apart. When you roll a die onto this field of lines, it will always cross one line (although it's not "impossible" to land right between two lines, there's $0$ chance that it will.) Sometimes, the die will cross two lines.

You can compute the theoretical likelihood that it will cross two lines, and it involves $\pi$. Then you can roll the die and get an empirical probability. Set the two things equal, solve for $\pi$, and you have an approximation.

This is a lot like the famous needle problem, where you view a face-diagonal of the die as the needle.

To calculate the theoretical probability, we only care about where the center of mass of the die lands along a line orthogonal to the lines we sketched, and the angle that the face-diagonal make with the drawn lines. In the epression below, the "$2$" and "$8$" exploit symmetry to make the integral easier to write. The probability is $$\frac{2\cdot\int_{y={1-\sqrt{2}/2}}^{y=1/2}8\cdot\int_{\theta=\arcsin\left(\frac{1-y}{\sqrt{2}/2}\right)}^{\theta=\pi/2}\,d\theta\,dy}{\int_{y=0}^{y=1}\int_{\theta=0}^{\theta=2\pi}\,d\theta\,dy}$$ which simplifies to

$$\frac{4}{\pi}-1$$

So eventually, after enough die tosses, $0.2732...$ of them will have crossed two lines. Adding $1$ to this, dividing by $4$, and inverting will give an estimate of $\pi$.

If you want to know how many tosses it will take until you can be reasonably sure that you will have $\pi$ correct to three digits, that's about the same as getting the empirical probability to have an error less than $0.001$. Assuming we do not know a decimal for $\frac{4}{\pi}-1$, we would assume the worst case: that this is $0.5$. In that case, to have an error of under $0.001$ with $95\%$ certainty, we would solve $$0.001=1.96\sqrt{\frac{0.5\cdot0.5}{n}}$$ and you'd need over $960{,}000$ tosses. I'd be surprised if any of the dice-based methods for approximating $\pi$ are markedly faster than this.

$\endgroup$
3
  • 1
    $\begingroup$ I think these answers involving physically throwing the dice (and hoping you perform the process "randomly" enough) are not the intended direction — for instance, they can be done with any physical object (say an unmarked cube); they don't use the property of the dice (which is that it's a device to generate a random number by rolling it and seeing what face comes up). $\endgroup$ Apr 8, 2014 at 1:35
  • $\begingroup$ @ShreevatsaR Maybe. I would think that, seeing as how this was a job interview question, maybe there is no specific answer the interviewer is looking for. Maybe it's more about seeing if someone can come up with some answer, and the ideal candidate can come up with several. $\endgroup$
    – 2'5 9'2
    Apr 8, 2014 at 7:21
  • $\begingroup$ @alex.jordan: Even though I agree with what you have said regarding interview, interviewer is basically expecting answer on the grounds of what Shreevatsa R has said. It was a Probability round interview. $\endgroup$ Jun 3, 2014 at 14:41
1
$\begingroup$

You can do it using simple geometry like someone said. Take a square of sides R and cut it into smaller equalsized squares, preferably the size of the dice. So it's advisable that R is a multiple of the length of a side of the dice. Then stick the squares randomly in a circle on radius R, without any overlapping. When you throw the dice in the circle, count the number of times at least half of the die falls in a square. Now the total number of throws divided by the number of throws landing on a square should give you pi.

$\endgroup$
0
$\begingroup$

Surface area of a sphere = $4\pi r^2$. Surface area of a die = $24r^2$. Therefore $\pi = 6$.

Or: Volume of a sphere = $\frac43 \pi r^3$. Volume of a die = $8r^3$. Therefore $\pi=6$.

Looks watertight to me.

$\endgroup$
0
$\begingroup$

The problem with dice is that they do not represent a uniform distribution in the unit square. The image below illustrates the problem. Yellow dots are interior to the circle of radius 6. Red dots are exterior to the circle.

enter image description here

Rolls of two dice that correspond to the interior of the square represent the four square region surrounding the point. However, rolls on the left and upper edges overweight the probability of that sample, as it counts area outside the square being used to estimate pi. Likewise, dice rolls cannot represent samples along the axes.

To compensate for this, you can select a one of the dice to be in the range of [0, 5] and use the other die to represent [1, 6].

If we assign the [0,5] die to the x-axis, then the samples of that vertical column will be applied to column zero. This balances the samples along the vertical axis.

enter image description here

For the case of two six sided dice, the corresponding monte carlo method will converge to the estimate: 4*(28/36) = 28/9 = 3.1111. Compared to the other methods, this will converge fairly quickly, usually getting two decimal places of precision in about 1000 rolls.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .