Skip to main content

Value of Pi - Estimation using Dice


Source: Asked to a friend at Goldman Sachs Quant Interview

Problem:
Estimate the value of pi using a dice

Update: (21 June 2014)
Solution posted by Tushar Makkar, 'My first amateur attempt', Satadip, Gaurav Bajaj and me (Pratik) in comments. Thanks




Comments

  1. Imagine we have a dice and we have to throw in a circle embedded in a 4*4 square. This circle touches the boundaries of this square. Let’s say out if N trials number of times this dice falls on circle is C and number of times this dice falls on square is N.
    So the ratio of C/N will represent the ratio of area of circle to the area of square which is [PI*(R*R) ] /(4*4).
    (C/N)=(PI*4/16)
    [ C/N=PI/4 ] => PI=4*C/N
    At this point, we will perform the simulation using N=3000. So, the trick is number of times the dice falls on square is equal to number of trials performed. The range of x and y will vary from -2 and 2.
    And the condition which is used in simulation to check whether the dice falls inside the circle or not is IF(sqrt(x^2+y^2) <2) then assign cell’s value is 1 and if the condition fails, assign cell’s value as 0 . In the end we can use find out numbers of cells containing 1 to find C/N ratio.
    Using both the equations we can find approximate value of PI . These kind of problem solving methods are known as Monte Carlo simulation techniques .

    ReplyDelete
  2. consider a circle inscribed in a square , the probability of a random point from the square also in the circle is pi/4
    Now how do we actually pick up a point randomly , this is where the dice will help
    break the square into 6 by 6 blocks , 2 rolls of dice will give us co-ordinate of the box
    now if we stop the experiment here give the center of the square as the random point else apply the same experiment to this smaller box .
    choosing any of the 36 smaller boxes is equally likely so if we do enough trials we can be sure to pick a random point with every point being equally likely.
    This solution was by my friend Sankeerth(EE , IITB class of 2009)

    ReplyDelete
  3. I found this link: http://www.monkshouts.org/value-of-pi-using-monte-carlo-simulation/
    The die is meant to mislead you. You can simply throw any object randomly in a square and estimate the probability that it lands inside an embedded circle. If the square is of side 2 and the circle of radius 1, then the probability is pi/4.

    ReplyDelete
    Replies
    1. Gowtham, Nope. Its not a trick question. Please check the answer. Interesting aha moment. :-)

      Delete
    2. How is this method specific to a dice. Any other object would suffice, No?

      Delete
  4. use monte carlo simulations.... take a square [-3, 3] x [-3, 3] and check a pair of die-rolls(dey give the co-ordinates of point) a large no of times.

    ReplyDelete
  5. Here's a little bit neat method.
    Throw a die six times. Let the values be a, b, c, d, e, f.
    Define a event X if {(a-1)/6 + (b-1)/36 + (c-1)/216}^2 + {(d-1)/6 + (e-1)/36 + (f-1)/216}^2 <1 and event Y is the otherwise.
    Calculate {the number of event X} / {(the number of X)+(the number of Y)}
    This will converges approximately pi.

    ReplyDelete
  6. A more accurate solution:
    divide the square in 6x6 blocks and each square again into 6x6 sub-squares as shown in the image below
    http://postimg.org/image/xiizzkp2p/
    Throw the dice:
    1. if the dice points to the square such that it lies in the centre 4x4 square add one to Pi_count variable
    2. if the dice points to the 20 squares on the perimeter, throw dice one more time and if the dice points to subsquare which is filled with blue add one to Pi_count.

    Value of Pi = Pi_count/Num_of_iteration*4

    The precision improved 6 times with 1.55 times increase in no of dice throws.

    ReplyDelete
  7. 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=in+out such pairs, and so accumulating a total of n tallies, we have
    π ~ 4*in/(in+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 π/4, and so a uniformly selected point in the square will lie in that region with probability π/4.

    ReplyDelete
    Replies
    1. sir do we need to know algorithmic techniques before solving your puzzles....i have jst passed out class 12th

      Delete
  8. Suppose you have 3 die (A, B, C):

    Calculate expected value of: {the actual number on die A or 1} (choose 1 if sum of numbers on B + C = 5)

    ReplyDelete

Post a Comment

Popular posts from this blog

Asking a girl out

This is not a puzzle. So, for those of you who follow this puzzle blog, please bear with me for just one post. Interesting Math in this article though :P

Most of my friends already read an article that I wrote more than an year back - "Speak Up"


Here, inspired by the movie, The Beautiful Mind, I give a mathematical analysis of asking a girl out. Nice time it is. Feb 10. No plans for Feb 14 and I am sure this article makes me look even more geekier and all the more reason for me to believe that I will be alone, yet again. But what the hell, lets do it!

Note: This is not an independent analysis. There are many "mathematics sites" which does "similar" analysis.

@Consultants, correct me if I am wrong in my estimates. :P

Why is there a need to be selective?

From the age of 15, I guess there are approximately 3,600 girls I have liked (On average days, I don't see new girls. But going outside, I like about 30 girls. Saying that I go out once every week right …

Consecutive Heads

Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tossing another fair coin, until he get 3 consecutive heads, define Y to be the number of the tosses for this process.

1) Calculate P{X>Y}
2) What's the expected value of X
3) What's the expected value of Y

This is probably the hardest puzzle I have ever put on my blog. Hence, I will post its solution in the post directly rather than on comment.

Solution:
1)
(Solved by me finally after 13 months :))

Make a state diagram. Let the state be (a,b) where a is the number of consecutive heads streak "A" is on currently and b is the number of consecutive heads streak "B" is on currently.

So, (0,3) (1,3) are final accepted states and (2,0) (2,1) (2,2) (2,3) are failure states. If you get tails, your contribution to the state reaches to "0"

f(State) = P(X>Y | "State" configuration initially)

f(0,0) = 1/4[f(…

Fraction Brainteaser

Source:
Sent to me by Gaurav Sinha

Problem:
Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20 out of 28 Geometry questions. In total, Siddhant scores 25 out of 34. 

Vaibhav writes another Maths test and correctly answers 20 out of 25 Arithmetic questions and 6 out of 9 Geometry questions. in total, Vaibhav scores 26 out of 34.

Note that
a) Vaibhav scores more than Siddhant
b) Siddhant score better than Vaibhav in both individual topics - 5/6 > 20/25 and 20/28 > 6/9

How is it possible?