• Search Blog

## July 26, 2007

### Math: For Programmers and in Everyday Life

Category: Personal development,Software development — by Amit Chaudhary @ 7:07 am

I knew the Math basics needed for choosing algorithms when programming, this is the simple stuff, mostly Big-O notation and comparision of O(N logN), O(N), O(N*N), etc. Two events in late 2006, early 2007 gave Maths more prominence for me.

One was reading the convincing argument by Steve Yegge I consider to be Uberdev.
Steve Yegge’s Math Every Day, Written in November 15th, 2004 when he was at Amazon.com

I just read a book called John von Neumann and the Origins of Modern Computing. Every few years I read a book that causes a discontinuity in my thinking — a step function that’s a lot larger than the little insights that most books or articles produce. For me, this was one of them.

Math is a funny thing; it’s not the way most people think of it — it’s an ever-expanding set of tools for modeling and solving problems. It’s very much driven by practical considerations; if a new problem comes up, and it’s not tractable to existing mathematical methods, then you work to make up new ones.

My new motto is “Math every day.” I’m giving myself one year to master all the math I was supposed to have learned in high school and college: algebra, geometry, trigonometry, limits and conic sections, differential calculus, integral calculus, multivariate calculus, simple differential equations, linear algebra and eigenvectors/eigenvalues, discrete math and logic, probability and statistics. I “knew” it all at one time or another, without really understanding what the heck it was for, so I should be able to put it all together again fairly quickly, if I put my mind to it.

Although I have not yet taken it to his level, I started keeping an open eye and learning approach to any Math I encounter.

Second was Google interviewers asking Math (Probability puzzles among others), See the birthday wager question at Shmula’s Google interview article. I have since realized that Discrete Mathematics is a prerequisite for some fields such as Data Mining and Machine Learning which matter for Internet companies such as Google, MSN, Yahoo & Amazon.

Interestingly, soon I started noticing more math in my day to day life, typical it tends to be Combinatorics (Permutation & Combination) and Probability. Here are a few actual life examples from the last 6-9 months:

• Dilemma of the Garage door repairman

Our Garage door stopped working (would not open or close), so we get the Garage door repairman. He installs a new opener, but forgets the combination. He says their are millions of combinations and he will never get it even if it tried.

He shows it to me and if you look inside the Garage door opener (which one typically uses from their car), there are nine pins with each having two positions. Soon enough, it clicked to me, it maps neatly to a 9-bit integer value. The total possible values is 512 (2^9) which though a lot, is much less than millions.

• A Bet against real estate median price rise

I rarely bet, but earlier in 2007 I took a bet against Seattle area (King County SFH, Single Family Home, to be precise) rising more than a certain percentage (one percent) in year 2007. I am now on track to probably lose this bet.

It seems logical during that time including the fact that real estate sales were falling and so on. So what happened? Primarily, I was just wrong in my understanding of the issues. However, also affecting it was the fact that the weightage changed. Median as you probably know implies half of the quantity is above that number and half are below. In recent months, sales for lower priced cities in King County have been dropped as a percentage of the county. This skews the balance, making it a much higher probability bet, now most cities SFH would now need to drop.

• A Bet against India not winning the Cricket World Cup

Later on, a friend of mine to bet that India (the country where I was born and whose Cricket team I sometime follow) will win the Cricket World Cup. The weightage in this bet was the capability of the team, however the Indian Cricket team unlike, say the Australian is not head and shoulders over the rest. So with a no weightage scenario, this was a one team out of sixteen making it, I was getting 1:1 odds for a probability event of 15/16. I took it. And won. A good resource on making sense of odds: Figuring the Odds, Probability Puzzles.

• How many confirmation numbers can Southwest airlines really give out

I noticed that all Southwest airline tickets are uniquely identified by a confirmation number which has six characters and contains numbers and alphabets. An example is CZ6H55. I was wondering how big is this space or rather how many confirmation numbers can Southwest airlines really give out, considering it is one of bigger domestic airline?

This is a case of permutations (changing positions of same numbers results in different confirmation numbers), each position can have 36 (26 alphabets + 10 digits) values and repetitions are allowed (DDDDDD should be valid.) The formula for this is 36 * 36 *…6 times = approx 2 billion.

The result of math behind finding people with same birthday (See below) still surprises me as does the infinite monkey theorem states that a monkey hitting keys at random on a typewriter keyboard for an infinite amount of time will almost surely type or create a particular chosen text, such as the complete works of William Shakespeare. Interestingly, as the wikipedia entry says. The probability of a monkey typing a given string of text as long as, say, Hamlet is so infinitesimally tiny that, were the experiment conducted, the chance of it actually occurring during a span of time of the order of the age of the universe is minuscule but not zero.

If you are interested in the probability question that Shmula was asked at Google and the response, my take is below:

Question:

you are at a party with a friend and 10 people are present including you and the friend. your friend makes you a wager that for every person you find that has the same birthday as you, you get \$1; for every person he finds that does not have the same birthday as you, he gets \$2. would you accept the wager?

One way to look at it, for me to make money, out of 8 people, 6 or more would need to have birthday on same day as me, and 2 would need to be different.
or it is giving me odds of 2-to-1 (Odds =, if T is total, t1-to-t2, here t1+t2 = T, see dice case below for example)

Using above logical possibility #2
The odds that six people have their birthday on same date as me is
=1 – (364/365 * 364/365 * 364/365 * 364/365 * 364/365 * 364/365 )

=1 – (0.99726027 *0.99726027 *0.99726027 *0.99726027 *0.99726027 *0.99726027 *)

=1-(0.98367382)

=0.01632618

The odds seem to be 1 in 100 that I will make money with the above deal. So, I would not accept the wager if making money on it was my intention.

A variation, the chance that 1 person out of 25 in a party shares his\her birthday with me is (See details below)

~= 0.50

and out of 50, it is almost a surety

~= 0.97

For the probability background for above problem, I would suggest reading: Math Forum, Ask Dr. Math: Probability When to Add, When to Multiply?

And on a lighter note, here is a new way to learn maths, New Math (Tom Lehrer) Animation

• • •

## 1 Comment »

1. Your analysis of the birthday problem:

The odds that six people have their birthday on same date as me is
=1 – (364/365 * 364/365 * 364/365 * 364/365 * 364/365 * 364/365 )

That is the probability that *at least one of six people* have the same birthday as you. If there were 6 other people in the room, and you only needed at least one of those six people to share your birthday, then you would be correct, there is about a 1.6% chance.

For this problem, the probability is much smaller. I solved it by adding the discrete probabilities that there were exactly 8 people who share your birthday plus the same probability for 7 and 6 people. The result is 1/365^8 + 8*364/365^8 + 28*364^2/365^8 = 3712801/315023473396125390625 = about 11.786E-15, which is less than one billionth of one percent.

I definitely wouldn’t take the wager.

Also:
A variation, the chance that 1 person out of 25 in a party shares his\her birthday with me is ~= 0.50

That is the probability that *any two people* at the party share a birthday, not that one of them shares it with *you*.

-Erik

Comment by Erik — September 11, 2007 @ 2:29 am