Posts

Showing posts with the label Probability

Mathematics of SET game

Source: Sent to me by Pritish Kamath ( http://www.mit.edu/~pritish/ ) Problem: Have you ever played "SET"? You have to play it. http://www.setgame.com/learn_play http://www.setgame.com/sites/default/files/Tutorials/tutorial/SetTutorial.swf Even if you have not played the game, the game can be stated in a more abstract way as follows: There are 12 points presented in  F 3 4  and the first person to observe a "line" amongst the 12 given points gets a score. Then the 3 points forming the line are removed, and 3 random fresh points are added. Problem 1: How many points in  F 3 4  are needed to be sure that there exists a line among them? Problem 2: Given 12 random points in  F 3 4 , what is the probability that there exists a line among them? Disclaimer: We have not solved the problem yet. It can be very difficult or very easy. Update (22/12/14): It turns out to be a very very difficult problem. Paper: http://www.math.rutgers.edu/~maclag...

Social Network Friendship Paradox

Problem / Observation: The friendship paradox is the phenomenon first observed by the sociologist Scott L. Feld in 1991 that most people have fewer friends than their friends have, on average. Prove it mathematically. Update (23 Oct 2014): Solution:  Posted by Mike Earnest and Taz in comments!

Picking K elements randomly

Problem 1: Consider the problem of picking K elements randomly from N elements. Suggest an algorithm. What is the time and space complexity of your algorithm? Problem 2: Now consider that the stream is infinitely long (i.e. N is unknown). Now how do we pick K elements randomly. Update (24 June 2014): Solution: Posted by Himanshu (Prob 1), PlacementIITB2014 (Prob2) and Sid (Prob1 and Prob2) in comments! Thanks claimtoken-52ac74fbddf1e

Two Coin Tossing Puzzle - Expected Number of Tosses

Source: Mailed to me by Vashist Avadhanula (PhD Student at Columbia Business School, EE IITB 2013 Alumnus) Problem: Consider a case where you flip two fair coins at once (sample space is HH, HT, TH & TT) you repeat this experiment many times and note down the outputs as a sequence. What is the expected number of flips (one flip includes tossing of two coins) to arrive at the sequence HHTHHTT.

Probability Puzzle: Expected Number of Expression Evaluations

Source: Asked for a data scientist position at a technology startup in financial services sector in London Problem: Given python code to calculate maximum in an array of integers x def find_max(x):          max_num = x[0]          for i in x[1:]:         if i > max_num:             max_num = i   << Expected number of times this expression  was evaluated     return max_num Calculate the expected number of times the expression max_num = i was evaluated, given that array x was taken from a uniform random distribution.

100 sided die probability problem

Source: Jane Street Capital Interview (Quantnet) Problem: You are given a 100 sided die. After you roll once, you can choose to either get paid the dollar amount of that roll OR pay one dollar for one more roll. What is the expected value of the game? (There is no limit on the number of rolls.) Update (22 June 2014): Solution posted by me, Felix, JDGM, Sebastian, Fu Shi and Dumb Phoenix in comments!

World Series Puzzle

Source: Discussion with Ashwin Rao ( http://zlemma.com , Ex-MD Morgan Stanley) and Gaurav Kumar (Credit Suisse IB, Ex-MS, GS, IITB CSE 2006, Booth 2012) Problem: Suppose teams A and B play in the world series of up to 7 games in which the first team to win 4 games wins the series and then no more games are played. Suppose that you want to bet on each individual game in such a way that when the series ends you will be ahead by exactly 100ドル if your team wins the series, or behind by exactly 100ドル if your team loses the series, no matter how many games it takes. How much would you bet on the first game? Update (22 June 2014): Solution posted by Alex, JDGM, Arnab in comments!

Probability Puzzle: Guess Position of Card

Source: Counter-intuitive Conundrums Problem: Someone hands you a deck of cards which you thoroughly shuffle. Next, you start to deal them, face-up, counting the cards as you go. “One, Two, Three …” The aim is to predict what the count will be when you encounter the second black Ace in the deck. If you had to select one position before you started to deal, what number would you select that maximizes your chance of guessing the location of the second black Ace?

Coin Puzzle: Predict the Other's Coin

Source: Puzzle collection by Raphael Reischuk Problem: Assume the following 3-player game consisting of several rounds. Players A and B build a team, they have one fair coin each, and may initially talk to each other. Before starting the first round, however, no more communication between them is allowed until the end of the game. (Imagine they are separated in different places without any communication infrastructure.) A round of the game consists of the following steps:  (1) the team gives one dollar to player C.  (2) Both A and B toss their coins independently.  (3) Both A and B try to predict the other's coin by telling the guess to C. (No communication: A does not know the outcome of B's coin toss, and vice versa, nor the guess).  (4) If C verifies that both A and B guess the other's coin correctly, then C has to give 3 dollars back to the team.  Should C play this game? Previously Asked Coin Puzzles: Coin Balancing Coins Puzzle...

Pizza Distribution Puzzle

Source:  xkcd wiki Problem: The king of the universe has decided to play a game. To start, he selects 1 person. He then flips two fair coins - if they both come up heads, the person gets a free pizza and the game is over. For any other result, he sends the person home and selects 2 new people, where he does the same 2-coin flip to decide if they each get a pizza. If they don’t, he picks 4 people at random, then 8, and so on, doubling each round. If you are selected but don’t win, you can’t be selected again – and you can assume the population is extremely large so there’s no chance of running out of contestants. You are sitting at home when you get a call – you have been selected to play the game. What is the chance that you will get a free pizza? You don't know which round number it is, but if you ask, the king will tell you. Does it matter? Disclaimer: Very easy problem! Update (31 January 2013): Title changed to "Pizza Distribution Puzzle" from "...

Quick Probability Questions for Interviews

1) If cor(a,b)=0.5 and cor(a,c)=0.0, what is the range for cor(b,c) 2) A deck of pokers. Three choices: A: 26 black, 26 Red; B: 13 black, 13 Red; C: random 26 card from the deck. Take the first two cards, if same color, the win 1,ドル otherwise lose 1ドル. Which deck is best for you if you are playing? Why? 3) What is the probability of a random generator generating 10 consecutive numbers in ascending order (assume it is a perfect random generator) Update (24/12/2012): Solution posted by AH in comments! Solution explained in detail by me. Thanks

Geometry Puzzle: Center of Square in Circle

Source: Asked to me by a lot of people from IIT Bombay on email and posted by a few on " Post a Question " page. Problem: What is the probability that two uniform random points (to be precise: i.i.d. with respect to Lebesgue measure) in the square are such that center of the square lies in the circle formed by taking the points as diameter. Edit: Problem wording made more mathematical. Update: (24/12/2012) Correct solutions by Barun Kumar Kejriwal, Akhil Kumar, Aastha Airan, Arpit Goyal and Yashoteja in comments! Thanks a ton.

IQ Measurement Puzzle - Statistics Problem

Source: 40 Puzzles and Problems in Probability and Mathematical Statistics (Interesting book by Wolfgang Schwarz) Inspiration: This problem demonstrates clearly the shortcomings of out grading system through exams Problem: Peter has an IQ of 90 whereas the IQ of Paula is 110. However, due to unsystematic biological or psychological day-to-day variation that is unrelated to the IQ per se, any single measurement of either IQ is distorted by an independent additive measurement error that has a zero-mean normal distribution with some variance. For example, if Paula’s IQ were measured repeatedly, the outcomes would be normally distributed with a mean of 110 (her “true” IQ) and some standard deviation. Suppose that either Peter or Paula is selected at random (p = 0.5), and his/her IQ is measured. You do not know who was selected, but you are told that the result of this first measurement is 105. Now the same person —whose identity is unknown to you — is measured a secon...

Brownian Motion in Circles Puzzle

Source: http://www.stanford.edu/~gowthamr/puzzles.html Problem: Suppose the starting point of a particle undergoing Brownian motion in 2 dimensions is chosen uniformly at random on an imaginary circle C_1. Suppose there is a solid circle C_2 completely inside C_1, not necessarily concentric. Show that the particle hits the boundary of C_2 with uniform distribution. Book: I strongly recommend the book by Steven Shreve for understanding Brownian Motion and its applications in Financial Modelling (Its expensive! Flipkart Link: Stochastic Calculus for Finance II ) Update (4th Feb 2013): Solution posted by me in comments!

IBM Ponder This July 2012 - Colouring Balls

Source: IBM Ponder This July 2012 Problem very similar to   CSE Blog: Painting Coloured Balls  ( Link:  http://pratikpoddarcse.blogspot.in/2010/10/painting-coloured-balls.html  ) Problem: Alice and Bob are playing two games: they start simultaneously and the first one to win his game is the winner. Alice is given an urn with N balls, colored in N different colors and in every second she randomly picks two balls, colors the first ball in the color of the second ball and returns both to the urn. Her game is over once all the balls in the urn have the same color. Bob is given an urn with M balls, all colorless, and in every second he picks a random ball, color it, and puts it back to the urn. Bob's game is over once all his balls are colored. Our question is: what are the possible values of M for which (on average) Bob is expected to lose for N=80 and win for N=81?  We ask for possible Ms for which the expected time of Bob's game is smaller than Alice's...

Crossing the Road

Source: Quantnet Interview Questions Problem: If a car passes at the crosswalk on average every 10 seconds and you need 20 seconds to pass the road, how long does it take you on average to cross the road? Note that since the problem is not very well specified, make reasonable assumptions to solve it. It would be fun if before solving mathematically, you try and guess a time estimate. :-) Update (3rd January 2011): Solution posted by Santosh Ananthakrishnan (EE Final Year DD Student IIT Bombay) and Animesh Saxena (Manager at Karvy Private Wealth) in comments!

Sphagetti Breakfast

Source: Very standard problem in Quant interviews (Taken from quantnet, xkcd forums) Problem: A bowl of spaghetti contains n strands. Thor picks two ends at random and joins them together. He does this until no ends remain. What is the a) expected number of spaghetti loops in the bowl? b) expected average length of the loops? (in strands) c) expected number of k -hoops? ( a k -hoop is a loop made from k strands)

Distinct numbers in a sample draw

Source: Asked to me by Chinmay Chouhan, Junior Undergraduate, CSE IITB Problem: Given the set of numbers from 1 to n : { 1, 2, 3 .. n } We draw n numbers randomly (with uniform distribution) from this set (with replacement). What is the expected number of distinct values that we would draw? Update (Oct 30, 2011): Solution posted by Yashoteja Prabhu (RA at Microsoft Research, IITB CSE 2011 Alumnus), Garvit Juniwal (IITB CSE Senior Undergraduate), Dinesh Krithivasan (IITM Alumnus, Phd University of Michigan, Senior Qualcomm Engineer), Nikhil Garg (IITD CSE Senior Undergraduate) and Avinash in comments!

Increasing Sequence in Dice

Source: A book on probability puzzles Problem: Suppose we play a game with a die where we roll and sum our rolls as long as we keep rolling larger values. For instance, we might roll a sequence like 1-3-4 and then roll a 2, so our sum would be 8. If we roll a 6 first, then we’re through and our sum is 6. Three questions about this game: (a) What is the expected value of the sum? (b) What is the expected value of the number of rolls? (c) If the game is played with an n-sided die, what happens to the expected number of rolls as n approaches infinity? Update (Aug 31, 2011) Solution posted by Gaurav Sinha (chera, IITK 1996 Graduate, Indian Revenue Service) and Siva in comments!