Skip to main content

Posts

Showing posts from January, 2013

The Random-Picker Algorithm

Q: You have a queue of people outside your office door and you want to pick exactly one person at random. However you do not know the length of the queue. You are allowed to accept a person and then reject that person when you see another should you so choose. How do you do it? Fifty Challenging Problems in Probability with Solutions (Dover Books on Mathematics) A: At first look, this seems impossible to solve. How do you randomly pick when you don't know what the denominator is? It could be 5, 10 or 100s. Surprisingly, the following strategy works beautifully. Keep a counter on the number of persons who come in, call this counter \(i\). For every person coming in, pick that user with probability \(\frac{1}{i}\) When the \(\{i + 1\}^{th}\) person comes in, with probability \(\frac{1}{i+1}\) replace the existing person. The above algorithm works by ensuring that the selected person is indeed picked up with probability \(\frac{1}{n}\) where \(n\) is the number of persons in th

Lions Tigers and Bears

Q: You are told that a certain area in a forest has lions, tigers and bears. You tour that area and observe 5 tigers, 2 lions and 1 bear. What is your estimate on the distribution of these animals? Fifty Challenging Problems in Probability with Solutions (Dover Books on Mathematics) A: This is a good example to demonstrate the multinomial distributions, it's application and also introduce the concept of "conjugate priors". Lets deal with them one at a time and then revisit the problem. The Conjugate Prior: This concept is part of Bayesian analysis. Lets assume you have a prior which belongs to a "family" of functions say \( y = f(\theta,x) \). You get some additional information and you update your estimate such that the posterior belongs to the same family of functions. So the prior and posterior differ only in the parameters that go into the function and not in its form and structure. An example of conjugate priors is the Gaussian distribution.

A Game of Pots and Gold

Q: You are in a game with a bankroll of 13 gold coins. The game involves a 13 pots lined up. There is a 96% chance that one of the pots has 22 gold coins in it. You get to inspect a pot by paying 1 gold coin. The game organizer tells you that there is a 90% chance that the very first pot has the gold coins in it. You pay 1 gold coin to inspect the first pot and you find there is no gold in it. Should you continue to play? Fifty Challenging Problems in Probability with Solutions (Dover Books on Mathematics) A: This is good example of a puzzle where at first blush it appears that there is no merit in continuing. It almost gives the impression that "most" of your probability of winning is lost right from the get go as the first pot, which was known to have a 90% chance of having the 13 gold coins does not contain gold. Let us assume that the probability of winning is \(x\) downstream of the first pot (that is pots 2 through 13). Next, lets estimate the probability of not w

The Seven Coins of James Bond

Q: James Bond tells you he has seven coins. What is the probability that he has more than a dollar (US dollar)? The Probability Tutoring Book: An Intuitive Course for Engineers and Scientists A: For starters assume that the coins are equally probable. This simplifies things. The coins could then have values 1c, 5c, 10c and 25c with equal probability. This yields expected value of each coin to be  $$E = \frac{1}{4}\times ( 1 + 5 + 10 + 25) \\ = 10.25c $$ Therefore, the expected value of seven such coins would be \( 7 \times 10.25c = 71.75c \). To proceed we can make a simplifying assumption that the distribution of expected value of a coin follows a normal distribution. Note, this is not entirely accurate, but it is something we can work with. First compute the variance of the values. The variance of a random variable is the square of the standard deviation given as \(\frac{\sum_i (x_i - \mu)^{2}}{4}\). If you plug in the values you get $$ \frac{1}{4}\times{ (1 - 10.25)^{2} +