Skip to main content

Posts

Showing posts from August, 2012

Strings Puzzle

Q. A jar has N strings in it. You randomly pick up two loose ends and tie them up. You continue doing this until there are no more free ends. What is the expected number of loops in the jar?

A. This is another one of those puzzles which gets vastly simplified when you place it in a recursive perspective. A diagram with 3 strings would best explain the scenario. Ref figure below.



If there are 'n' strings, there are 2n loose ends to pick up from. The first loose end can be picked up randomly. While picking the second loose end, there are two possibilities.

It is part of the same string you just picked up ORIt is the loose end of another string. For 1), the probability of this event happening is
while for 2) it is 1 minus the above, giving


This implies that with probability 1/(2n-1), the expected number of strings will be 1 + P(n-1) and with probability (2n-2)/(2n-1) it will be P(n-1). This leads to the recursive formulation of the expected number of loops to be

If you re-arrange …

An Item Collection Puzzle.

Q. You are in a game where you need to pick up envelopes from a large collection. Each envelope has a card with the numbers 1 to 5 printed on them. You win the game if you collect all 5 numbers. How many envelopes on average do you expect to pick?

Introduction to Probability Theory


A. This is a puzzle involving expectations. An expectation is simply the average value of a probability distribution. To put in a simplified terms, the expectation of a variable is the product of the probability of the event occurring times the value from that event summed over all possible events.

If the player picks one card, he is guaranteed at least 1 number. The probability of getting the second number in the second draw is 4/5. Thus, it would take an average of 5/4 envelopes to get the second number. The 3rd number has a probability of 3/5 to be pulled in the 3rd draw and would require 5/3 envelopes to get at. Extending this we get the expected number of envelopes to be


If you are looking to buy some b…

Bacteria Puzzle

Q. A jar of water has a single cell of bacteria. With every passing minute, the bacteria will either die, stay the same or divide into two with probability 1/5, 2/5,2/5 respectively. What is the probability that the family of bacteria will survive forever.


A. This is a good example of a puzzle that is most easily solved by assuming a recursive structure. Assume that the probability to extinction is 'x'. Thus the probability that any one bacteria and its descendants will perish is x. The fact that the probability of descendants surviving forever is the same for all generations is key to understanding this problem. This is shown in the visual below.

Let us take the three possible scenarios one at a time.
Bacteria dies (probability = 1/5)Bacteria stays the same (probability = 2/5)Bacteria divides into two (probability = 2/5)We needn't dig further into case 1). The probability is 1/5. For case 2), the  probability that the bacteria would perish is 2x/5. For case 3), that probabi…

Understanding Bayesian Inference

Understanding Bayesian approaches to estimating probabilities are important. Often people don't get the full import of it and/or fail to see the consequences of not estimating it the right way. Most books that discuss it have confusing terminology to explain something that is fairly simple. Estimating Bayesian probabilities for events are relatively easier to understand, while those involving hypotheses aren't so even though the math involved is the exact same! In this blog, I'll try to explain the concept, but more importantly show the formula that any student can use so that they don't have "think through" the Bayesian logic all the time. However for some problems, it might be better to enumerate out the cases. To develop an intuition for this, you need to keep an eye out for new information that could be coming in and altering our belief in an existing hypothesis.


Here is the structure of the problem you will almost always run into. For simplicity let us …