Probability Puzzles

Posts

The "Bhakshali" Algorithm

This is a write up to describe an algorithm described in an ancient Indian manuscript. Its called the Bhakshali manuscript. The manuscript describes some mathematical assertions, methods and algorithms that has been dated to several thousands years ago. A really cool algorithm described in that manuscript is an approximation for finding the square root of a number. What I liked about this algorithm is that its handy. You could quickly approximate the square root of a real number with just some basic division and addition. This is how the algorithm works: If 'X' is the number you want to find a square root of, find the nearest whole number 'N' that approximates it. So if X = 23.2 then N = 5. Find the difference between X and N*N. Call it D. In this case it works out to -1.8. This should be too tedious to work out either. Now comes the magical part, divide this difference (D) by 2*N. So that's -1.8/10. Again, this shouldn't be that difficult to do in you

The Bacteria Division Puzzle

Q. A jar has a single cell of a bacteria. After every fixed interval of time the bacteria either splits into two with probability 2/5, does nothing with probability 2/5 or dies out with probability 1/5. What is the probability that the bacteria would continue to make a large family tree over an extended period of time? A. The situation can be described by the following visual. Assume that the required probability is 'p'. The term 1 - p would represent the probability that the ecosystem eventually dies out. Each of the above scenarios contributes a quantum of probability towards the ecosystem eventually dying out. Lets start off by represent 1 - p as 'x'. The probability that the bacteria die out is The total of each of the above must add up to the probability that the bacteria eventually die out, which is 'x'. So you can phrase the problem recursively as This simplifies to which is a quadratic equation, yielding a solution as This

The Forgotten Geometric Mean.

Often times a lot of people working with data are trying to create an index of some sort. Something that captures a set of key business metrics. If you are a site (or an app) you want to create some sort of an engagement index, which if trending up implies good things are happening, bad if it is trending down. The creators of such metrics (think analysts) tend to prefer a weighted arithmetic mean of the influencing factors. If the influencing factors are f1,f2, f3 (say) with weights w1, w2, w3 then the index would be computed as However, what does not get factored in are the final consumers of the index (think product managers) and there could be many. They will invariably try to check it with something else they have handy. For example, if clicks on a site went up 20% the index may be up by just 5% (say) or vice-versa. If resources are being allocated based on the movement of such an index, it will invariably lead to contention on what is the right weighting to be given to each f

Colored Cards and Numbers Puzzle

Q: You have a set of thirty six cards. The cards are six in color ( six each) and each color is numbered from 1 to 6. You draw two cards at random. What is probability that they are of a different color and have a different number? A: The first card can be drawn at random. It does not matter what its color or number is. To compute the probability that the second card is different in color and number from the first, it helps to visualize the situation in a simple way as shown below. In the figure above, assume the green dot represents the card that was picked. The marked out cards represent the cards that should not be picked to get a different color and number. Also, the act of picking a card bought down the pool of cards from 36 to 35. The remaining unmarked space represents the available set of cards to pick from. This can be computed easily as This yields an overall probability of If you are interested in learning the art of probability, some of the best book

The Magic of Numba and Python

Python is a great programming language. It's primary merits are readability and the numerous packages that are available online. However, being an interpreted language the speed of execution is always an issue. Here is a simple example of a piece of code written in Python that tries to add two numbers from a grid. #!/usr/bin/python def overlap_pp(x,y): count = 0 for i in range(x): for j in range(y): count += i + j return count for _ in range(1000): q = overlap_pp(500,500) If you run the above script (saved as n.py) on the command line terminal with the time command you should see some numbers like the below time ./n.py real 0m22.379s user 0m22.363s sys 0m0.407s The process running on one processor took about 22 seconds to complete the run. Now lets do something seemingly magical. Lets add a decorator. Decorators are python speak for a mechanism to do wrapper functions. The decorator we are going to add is '@jit'. The code looks l

The James-Stein Estimator

This write up is about an estimator. A statistical estimator, is used when you already have a model in mind, data at hand and want to estimate some parameters needed for the model. For example, you want to predict how many runs a batter would make in a game given recent history \(x_1,x_2,x_3,\ldots\) . If we assume (we are making a choice of a model now) that the scores come from a normal distribution with mean \(\mu\) and standard deviation \(\sigma\) then the probability density function for a given value \(x\) is The likelihood that a series of points \(x_1,x_2,x_3,\ldots\) come from such a distribution can be expressed as Next is basic calculus. Take the logarithm on both sides, set the partial derivative w.r.t. \(\mu\) to zero yields (excluding the algebra) To verify, you also need to check the second derivative's sign to see if its negative to ensure that it is indeed a maxima you have found. So a simple estimator would be to use the average