Skip to main content

Posts

Showing posts from July, 2013

Stirling Numbers of the Second Kind: a Puzzle



Q: An urn contains 20 uniquely identifiable balls. How many draws with replacement needs to be done before you are \(95\%\) sure that you have seen all of them?
A Book on Statistical Inference

A: A benign looking question, but its closed form solution is fairly complex and quite unlike a typical counting puzzle. First lets learn a useful tool: Stirling numbers of the second kind.  It is a complete name and they all go together. It takes in two arguments say \((k,n)\). This is represented as \(S(k,n)\) or also as \({k\brace n }\). It represents the number of subsets of a set of size \(k\) which has a size of \(n\). For example, if a set is given as \({a,b,c}\) then the number of sets of size 2 is \(\{\{a,b\},\{b,c\},\{a,c\}\}\). So we phrase this as
$$
S(3,2) = 3
$$
The generic expression for \(S(k,n)\) is given by
$$
S(k,n) = \frac{1}{n!}\sum_{i=0}^{n}(-1)^{i}{{n}\choose{i}}(n-i)^{n}
$$

The present problem is similar to starting with \(k\) balls, dropping then in…

The Blank and Regular Die Puzzle

Q:You have two dice. One of them is a regular one numbered from 1 to 6. The other one is blank on all sides. How do you number the blank one with two distinct numbers such that when you roll both dice, the sum of the number that shows up is almost evenly distributed?

A Book on Statistical Inference

A: If you assume that the blank dice was a regular one, then it is easy to see why the distribution of the sum would look like a triangular wave. There are more combinations of numbers between 1 and 6 that sum to 6 than there are to 2 and 12. For example, {1+5, 2+4, 3+3} all add up to 6 whereas only {1+1} add up to 2 and {6,6} add up to 12 respectively. Interestingly, if you insert the numbers 1 and 2 on three faces each you will get a fairly even distribution of the numbers. A comprehensive case by case enumeration is shown below.


First RollTotal @ Second Roll = 1Total @ Second Roll = 2123234345456567678
Notice, the distribution of numbers 3 through 7 is exactly two whereas 2 and 8 would oc…

Finding the Faulty Coin




Q: You have a large number of coins out of which some small fraction \(p\) are faulty ones. The faulty ones have slightly different weight (maybe more or less) and for some reason the error-free-test to weigh the coins is expensive and you want to minimize the number of tests done. So you embark on weighing them in bulk lots. What is the optimal lot size so that you minimize the number of weighs per coin.

Probability Theory: The Logic of Science
A: Lets assume we went with a lot size of \(x\). If we can compute the expected number of weighs per coin needed for a lot size of \(x\) then this strategy must apply to the entire set of coins. So we need not know the entire lot size.

Next, let us try and estimate the expected number of weighs needed. There are two scenarios.
You weigh the entire lot and you find no discrepancy in the weightYou weigh the entire lot and you find a discrepancy in the weight.Next we note the following
The probability that any one coin is faul…

Train Stations and Biases

Q: A single train shuttles in the north south direction on a single track. There are 12 stations on the track numbered in ascending order from the north to south. Every week, on a randomly chosen day, you observe the train on the 7th station. Over time you observe that you are more likely to observe the train coming from the north than the south. Why?

Fifty Challenging Problems in Probability with Solutions (Dover Books on Mathematics)

A: To start off, the probability that the train could be in any given station at any given time is the same for all stations. This implies that it is more likely that the train is in stations 1 through 6 rather than 8 to 12. Given this, it is easy to see that the probability of observing the train coming in from the north side is \(\frac{6}{6+5} \approx 54\%\)

Probability Theory: The Logic of Science




BookNotes/CommentsFifty Challenging Problems in Probability with Solutions (Dover Books on Mathematics)This book is a great compilation that covers quite a bi…

Cracking Numbers in Envelopes

Q: You are shown two envelopes with numbers written inside them. The numbers are chosen uniformly randomly from the range of 1 to a 100. You are allowed to open one envelope and look at the number inside following which you need to guess if the number in the other envelope is bigger or smaller of the two. You win if your guess is correct. What should your strategy be to have a greater than 50% win probability?

The Probability Tutoring Book: An Intuitive Course for Engineers and Scientists (And Everone Else!)

A: This puzzle is similar to the two envelopes paradox. At first pass, it appears that it is impossible to do better than 50% in win probability. But surprisingly, it is possible to do better. What is even more surprising is that it is an amazingly simple solution! All you need to do is to pick a function that is monotonically increasing in the domain 1 to 100. For example, let \(X\) be the number in the envelope you have opened. Let us make a function which takes in the number \(X…