Doctor House, Please Meet Mister Bayes

Let’s assume there’s some deadly disease out there, but there’s a pretty good test for it which is 90% accurate (if a person is sick – the test will claim he’s sick in 90% of the cases, and if a person is healthy – the test will claim he’s healthy in 90% of the cases). Now, assuming you took this 90% accurate test, and got a positive result implying you are sick - what are the odds that you are really sick?

Think of your answer before proceeding.

Most of you are probably thinking about 90%, and obviously, that's wrong (otherwise this post would be pointless). I intentionally left out a crucial piece of data which is that this disease affects 1 in every 10 people. Like many problems such as this, it looks very simple, but since most people never heard of Bayes’ theorem, they will only consider the test’s accuracy, ignoring the prior likelihood of the disease. I could use the formula, but I think using an example is much simpler. Let’s say 100 people take this test. Since the disease affects 10% of the population, 10 are really sick. The accuracy of the test is 90%, so 9 of them will get a positive result (true positives). From the other 90 people which are healthy, 81 will get a correct negative result, but 9 will get a positive result although they’re actually healthy (false positives). So after testing 100 people you end up with 18 people with positive results, but only 9 of them are true positives. 9/18=0.5=50%, so, the final answer is: Assuming you took this 90% accurate test to a disease that affects 10% of the population, and got a positive result implying you are sick – the actual odds that you are really sick are only 50%. Several studies where similar problems were presented to real doctors, demonstrated that only about 15% of them get it right. Isn't that amazing? 85% of the doctors will tell you you've got a pessimistic 90% chance of dying really soon, when actually there's a semi-optimistic 50% chance that there's nothing wrong with you! Now that you know this, will you ever be able to trust your doctor again when probabilities are involved?

~~~
p.s. I think, therefore I am wrong.

Fooling the IRS - Benford’s Law

Sorry for once again posting about a math related issue. I’ll try some biology or physics next time…

Let’s say you think the IRS shouldn’t take so much of your hard earned money. So, you sit around and just fake the numbers. Do you think you can get away with it?

Benford's Law, also called the first-digit law, states that in lists of numbers from many real-life sources of data, the leading digit is 1 almost one third of the time, and larger numbers occur as the leading digit with less and less frequency as they grow in magnitude, to the point that 9 is the first digit less than one time in twenty. This is the distribution of the numbers according to their first digit:
1 - 30.1%
2 - 17.6%
3 - 12.5%
4 - 9.7%
5 - 7.9%
6 - 6.7%
7 - 5.8%
8 - 5.1%
9 - 4.6%
This is based on the observation that real-world measurements are generally distributed logarithmically, thus the logarithm of a set of real-world measurements is generally distributed uniformly. This counter-intuitive result applies to a wide variety of figures, including electricity bills, street addresses, stock prices, population numbers, death rates, lengths of rivers, physical and mathematical constants, and processes described by power laws (which are very common in nature). The result holds regardless of the base in which the numbers are expressed, although the exact proportions of course change.

Real numbers on tax reports follow this pattern, but since this law is very counter-intuitive, people that fake the numbers almost always create different patterns. Many people will create an almost even distribution of first digits, or make up more numbers that start with the digits 4, 5, or 6. These patterns can be easily tested, and the fake report will immediately pop up, suggesting tax fraud. So what do you do when you wanna fake it? You Benford it!

~~~
p.s. They think they proved the Four Color Theorem; I say let them try it on the Middle East.

Fooling Your Math Teacher - Heads or Tails

Let’s say my hypothetical math teacher wanted to show me that the odds for heads or tails (on a fair coin toss) are about 50:50, so he gave me homework to toss a coin for 100 times and write down the result.
Well, I certainly have better things to do than tossing a coin 100 times just to demonstrate a simple probability of 50:50, so I decide to fake it.
I sit around and just randomly write “H” and “T”, making sure that the number of heads is roughly close to the number of tails and hand over my assignment:
H TT H T HH TT HH TT H TTT H T H TT H TT H T HH T HH T HH T H T H TTT H T H TT HHH T HH TT H TT HH TT H T H T H TT HH TT H TTT H TTT H T HH T H T H T HH T H TTT H T H
It may look OK, but my hypothetical math teacher should immediately suspect I didn’t really toss a coin. How can he tell? Well, I ran a simple computer program simulating 1 million sets of a 100 fair coin tosses, and this is what I got:
~54% of the results contained at least 7 consecutive H's or T's.
~81% of the results contained at least 6 consecutive H's or T's.
~99% of the results contained at least 5 consecutive H's or T's.
~99.97% of the results contained at least 4 consecutive H's or T's.
All of them contained at least 3 consecutive H's or T's.
Looking at my fake result, you'll notice that the maximum number of consecutive heads or tails is only three. Although the math teacher cannot be 100% sure, the chances for this result being a fake is 99.97% - I should have added longer consecutive series of H’s or T’s.
Some more interesting coin tossing related issues, and the exact probabilities for having consecutive heads or tails can be found here (thank you Michael Hovdan from the Reservoir Engineering Blog and Tamera Daun from Pentad for the link).

BTW, the image is of an ancient Hebrew coin from Judea, coined at 68 AD during The First Jewish-Roman War. These are ancient letters on the coin, but I can read them: That’s “SHEKEL ISRAEL” (Israeli Shekel) and “SHIN-GIMMEL” (marks the third year of the war) on the left, and “YERUSHALAYIM HAKDOSHA” (holy Jerusalem) on the right.

~~~
p.s. Cannibals don’t like brave men; they prefer chickens.

To Infinity... and Beyond!

The Eternity II puzzle is an edge-matching puzzle invented by Christopher Monckton, and is marketed and copyrighted by TOMY UK Ltd. The prize for the first person who submits a correct solution is $2,000,000.

This puzzle involves placing 256 square pieces into a 16x16 grid, constrained by the requirement to match adjacent edges (see picture). Each puzzle piece has its edges on one side marked with different shape/color combinations, each of which must match precisely with its neighboring side on each adjacent piece when the puzzle is complete. Each piece can be used in 4 orientations, there are 22 shapes/colors (not including the gray edges), and there is a starter piece which must be placed near the center of the board.

The number of possible configurations for the Eternity II puzzle is 1 × 4! × 56! × 195! × 4^195 = ~10^557, much larger than the estimated number of atoms in the observable universe, so even a super-computer running for many years will not find the solution to this problem. OK, so as you probably understand, there is no way to solve this puzzle completely and get those 2 million US dollars, but about a week ago I heard they offer a smaller prize to people who get close. I don’t believe anyone can even get close to the complete solution, but being a smart a*s, I just had to see how close a semi-sophisticated brute-force algorithm can get me, so I went and bought this puzzle. Naturally, I wrote a simple program (see my logo) and ran it on my PC last night. After a few hours of running, and a few millions of checked arrangements, the best score produced by my program was 236 out of the 256 tiles, that's ~92.2%. It may seem like much, but it isn’t.

Stay tuned… :p

~~~
p.s. Anybody else disturbed by the fact that Superman reversed time by rotating the Earth clockwise?

Failing for 130,000 Days Doesn’t Mean You Shouldn’t Try Again

A few decades ago, when I was in school, our math teacher gave us an assignment for homework. After a few days, the teacher came clean. This was what we had to prove:
It is impossible to separate any power higher than the second into two like powers.
You might recognize it in this form:
If an integer n is greater than 2, then the equation
aⁿ + bⁿ = cⁿ
has no solutions in non-zero integers a, b, and c.

In 1637, Pierre de Fermat wrote on the margin of a famous math book he owned, "I have a truly marvelous proof of this proposition which this margin is too narrow to contain." This note eventually became known as Fermat's Last Theorem, probably the biggest most famous mathematical problem ever. It looks so simple and innocent, understandable even to kids, so it is only natural that all the mathematicians tried to prove this simple statement. They all tried. They all failed. For more than three and a half centuries, all the great mathematicians took a shot at this problem to no avail. It seemed like this problem was beyond human capabilities.

Then, one day out of the blue in 1993, an unknown mathematician named Andrew Wiles shocked the world. After working on the Taniyama-Shimura conjecture (the last huge impossible missing piece of the puzzle) alone and in secrecy for 7 years, he completed the proof using modular functions and elliptic curves. He achieved what was thought to be impossible for 358 years, in what is considered by many as the greatest most brilliant mathematical piece ever written. Later, a mistake was found in his proof, but he managed to fix it after another extremely frustrating year of failing. I’m skipping a lot of details, so I must recommend the fascinating book by Simon Singh.

So, the next time people tell you "Drop it, it’s too difficult", you can refer them to this.

~~~
p.s. Why fish don’t talk? ‘Cause they’re busy! (credit goes to my 3.5 year old son)

Beating Asafa - Zeno's Paradox

Meet Asafa Powell, the 100m current record holder. If chased by a lion, he’ll make the first 100 meters in 9.74 seconds so find another partner for that dangerous backpacking trip to Africa...
EDIT: Since this post Usain Bolt has done it in 9.58 seconds.

Meet Maya, my 1.5 year old daughter (I have another 3.5 year old son named Yoav). When she runs, her feet twist inwards and her upper body leans forward in a scary angle, so an observer will probably define her running as a controlled crash.

Now here’s a scenario for you: a race between Asafa and my kid.
Let’s use round numbers.
Powell runs ten meters a second (I hope he won’t accidentally browse to this blog ‘cause he’ll probably kill me for that). My kid controlled-crashes one meter a second. Since my kid is in kindergarten, and Asafa is world famous, he foolishly agrees to grant her a ten meters lead. Ready. Set. Go!

1 second after the gun fires, the amused runner will close the lead, but my kid will manage to advance 1 meter in that time.
Current status: My 1.5 year old kid still has a 1 meter lead over the current record holder.

100 milliseconds later, the smiling Jamaican will pass this meter, but my daughter will manage to advance another 10 centimeters in that time.
Current status: My 1.5 year old kid still has a 10 centimeters lead over the current record holder.

10 milliseconds later, the optimistic sprinter will pass this small distance, but my 1.5 year old will manage to advance another 1 centimeter in that time.
Current status: My 1.5 year old kid still has a 1 centimeter lead over the current record holder.

1 millisecond later, the frustrated athlete will pass this tiny distance, but my cute underdog will manage to advance another 1 millimeter in that time.
Current status: My 1.5 year old kid still has a 1 millimeter lead over the current record holder.

Etc…

Can Asafa Powell ever catch up, or was he acting foolishly by agreeing to grant my daughter this lead?

~~~
p.s. Engraved on my tombstone: "I hope it’s not just 42…"

Why Software Engineers Should Care About the Price of Bananas

It appears that my job security as a software engineer depends on the price of bananas.

Since my yearly performance review at my company is just around the corner, I made some quick calculations to see how much I’m needed. An IBM research conducted a few years ago, claims that the average software engineer writes about 10 lines of functional code each day. Assuming an average line consists of about 40 characters, my addition to the company’s source code is around 400 characters a day.

I made some pretty weird (and noisy) simulations at home (I swear to God I made monkey voices while typing), and my best estimation is that an average chimpanzee hitting a keyboard at random can generate around 300 characters a minute - that’s 18,000 characters an hour. Monkeys sleep for 10 hours a day, and I think apes writing software should be allowed for at least one hour lunch break and one hour of Seinfeld; so that leaves us with 12 hours of actual chimp work, and a total of 216,000 characters a day for one monkey – already 540 times more productive than me. Since most of the chimp’s code will probably fail the unit/integration tests or won’t even compile, we’re going to need a lot of monkeys to cover all the possibilities. Since the number of characters allowed in C++/Java/C# is around 93 (I’m not going to let my monkeys write Visual Basic – even apes deserve some compassion), that gives us 93^400 possibilities needed to be tested daily and a total of (93^400)/(540) = ~4.6*10^784 chimps required. Assuming monkeys work 7 days a week and humans only 4 (holidays, vacations, sick days, etc…) we are left with ~2.6*10^784 apes needed to be added to our company’s R&D. Disregarding some minor issues (like the number of chimps is much bigger than the number of atoms in the universe), let’s see if my company should in fact fire me and hire apes to do my job. A chimpanzee can consume up to 50 bananas a day, that’s 1,500 bananas a month. The current price of 26.04 cents per banana gives us ~$390 per month for one chimp, and a total of $10^787 for all monkeys hired to replace one software engineer. Since an average software engineer (in Israel) earns about $5,000 a month, we can all calm down; it seems like we software engineers are safe for now.

Sefi/Moti/Alon – Please read my conclusion before my performance review.

My conclusion: As long as the price of bananas is still above 1/(1.27*10^784) cents per banana, it’s not financially wise for my company to fire me and replace me with chimpanzees.

~~~
p.s. When the Americans will reach Mars, what would they build first - a space station or a Starbucks?

The Vertigo and the Lion - Intuition Can Be Hazardous to Your Health

Sometimes, when a pilot flies at night with no visual reference, he gets disoriented, and his senses and intuition can cause him to think the instruments aboard his plane are wrong. He can be on a straight and level flight, but feel like he’s turning or even flying upside down. This dangerous phenomenon is called Vertigo. Pilots train for this condition and know that when their intuition disagrees with the instruments – they should trust the instruments.

Now consider this scenario: You are in Africa trying to hide from a lion. There are 3 small bushes with just enough space for one person/animal. You know the lion is waiting for you in one of the bushes (you don’t know which one) and your only hope is to pick a bush to hide in, hoping it’s lion-free. You randomly select bush #1 and start crawling at its direction hoping the lion is not there. Suddenly you see your friend crawling towards the bushes from the other side. He sees you are aiming for bush #1, so he can’t choose that bush even if it’s lion-free (no place for two people). You know he can see the lion from his angle but he can’t show you where it is because he’s afraid of making big sudden moves (or maybe he just thinks a satiated lion will give him a better chance). He aims for bush #3 (he’s sure it’s lion-free because he can see the lion from his angle), reaches it and hides there safely. So you are left with bush #1 and bush #2, one of them hides the lion.

Now, should you:
a. Stay with your original choice of bush #1.
b. Change your choice to bush #2.
c. It doesn’t matter – both bushes got the same probability for containing a hungry lion.
Please make your choice before reading on.

This was an example of how our intuition sucks. If you chose c - you are wrong, but take comfort in knowing you belong to the majority. If you chose b - you deserve to be eaten by a lion, please close your browser and book a flight to Congo. If you chose a - you are correct (this scenario is my weird inverted version of the Monty Hall problem). As you might have guessed, this problem is counter-intuitive so most people get it wrong.

While I can understand how evolution didn’t bother to equip us with intuition capable of avoiding Vertigo while night flying a high altitude super sonic metal machine, it seems like nothing short of a miracle that Homo sapiens has managed to get out of Africa in one piece with our fucked-up lion spotting intuition.

~~~
p.s. If a tree falls in a forest and no one’s around, should you blame the Jews?