« Posts under General

## Simplified III: The Goat Problem

“The solution often turns out more beautiful than the puzzle.”
— Richard Dawkins

The goat problem, or Monty Hall problem, named after the host of the game show “Let’s Make a Deal” confuses the heck out of people. Here’s the original formulation from Marilyn vos Savant:

Suppose you’re on a game show, and you’re given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door, say No. 1, and the host, who knows what’s behind the doors, opens another door, say No. 3, which has a goat. He then says to you, “Do you want to pick door No. 2?” Is it to your advantage to switch your choice?

As counter-intuitive as it might seem, the correct answer is — yes, it is!

Everyone (unless they knew this problem already) including software developers and physicists that I confronted with this answer, shook their heads in disbelieve. They are, however, in good company. According to this Wikipedia article:

Many readers of vos Savant’s column refused to believe switching is beneficial despite her explanation. After the problem appeared in “Parade”, approximately 10,000 readers, including nearly 1,000 with PhDs, wrote to the magazine, most of them claiming vos Savant was wrong (Tierney 1991). Even when given explanations, simulations, and formal mathematical proofs, many people still do not accept that switching is the best strategy (vos Savant 1991a). Paul Erdős, one of the most prolific mathematicians in history, remained unconvinced until he was shown a computer simulation demonstrating vos Savant’s predicted result (Vazsonyi 1999).

Fascinating, isn’t it? The problem (or rather the solution) is so hard to grasp, yet it’s so easy to follow this simplified™ explanation:

– If you initially picked a goat and you switch, you’ll win.
– If you initially picked a car and you switch, you’ll lose.
– It’s twice as likely that you initially picked a goat.
– Thus, it’s twice as likely to win when you switch!

Still not convinced? I wrote a little simulation in Python. Here’s the result after one million experiments:

The first number is the total number of experiments. The second number is the percentage of games won when the contestant stayed, while the third number shows the percentage of games won when the contestant switched.

## Simplified II: The Weasel That Teaches Evolution

“Weaseling out of things is important to learn. It’s what separates us from the animals… except the weasel.”
— Matt Groening

It’s Towel Day again! What a great opportunity to reflect upon Life, the Universe, and Everything. In this installment of the “Simplified” series, I want to tackle nothing less than Darwin’s theory of evolution. Why? Because I seriously believe that the world would be a better place if people finally understood it.

One common misconception, for example, is that some falsely believe that evolution occurs in a linear fashion, from single-celled organisms to homo sapiens. Such individuals, like the taxi driver that I mentioned in a previous post, think that they can smash the theory of evolution by posing this cunning question:

“If we humans are really decedents of animals like apes and dogs, why are there still apes and dogs around?”

Just in case this reasoning sounds conclusive to you as well: In reality, there is no single line of evolution, it’s rather a tree with many, many branches. On these branches, the universe performs experiments and decides which species survive, through natural selection. Consequently, humans did not evolve from apes, they are rather cousins whose common ancestor was neither ape nor human.

Another fallacy is Fred Hoyle’s famous Boeing 747 analogy. Hoyle was a brilliant scientist, no doubt, yet he refused to accept that complex life-forms can emerge by chance:

“A junkyard contains all the bits and pieces of a Boeing-747, dismembered and in disarray. A whirlwind happens to blow through the yard. What is the chance that after its passage a fully assembled 747, ready to fly, will be found standing there?”

A variant of this argument is the infinite monkey theorem: a monkey typing random letters at a typewriter will never be able to produce Shakespeare’s works.

In 1986, evolutionary biologist Richard Dawkins set out to dispel such misunderstandings by implementing a computer program that works—in Dawkins’ own words—like this:

“It […] begins by choosing a random sequence of 28 letters, […] it duplicates it repeatedly, but with a certain chance of random error – ‘mutation’ – in the copying. The computer examines the mutant nonsense phrases, the ‘progeny’ of the original phrase, and chooses the one which, however slightly, most resembles the target phrase, METHINKS IT IS LIKE A WEASEL.”

Here’s a more detailed explanation of his weasel program: it starts with a string of 28 random letters. Next, it creates N offspring strings by copying the original 28 random letters N times. When being copied, the chance of a letter being changed into another (random) letter is P. Now that we have a set of N new strings, we compare each string letter by letter against “METHINKS IT IS LIKE A WEASEL” (a quote from Shakespeare’s Hamlet, by the way) and pick the one with the most character matches (the highest match score). This one is deemed the “fittest” and kept as the survivor of the first generation; the other N-1 strings are discarded. We repeat the whole process by creating again N offspring from the survivor, then pick a new survivor and so on until the survivor finally matches “METHINKS IT IS LIKE A WEASEL”.

Let’s choose N to be 100 (one hundred offspring per generation) and P to be 5%, as in Dawkins original experiment. How many generations would it take until we finally reach “METHINKS IT IS LIKE A WEASEL”? Just guess a number, I’ll wait here…

Answer: about 50 generations! To me, this number was so ridiculously small that I decided to implement the weasel program myself. Please check it out here. Through command-line parameters, you can change the values of N and P, as well as the target phrase. Toying around with this program is so eye-opening, you suddenly realize that evolution is possible, that complexity can emerge by mutation and survival of the fittest.

Interestingly, if you set P to a high value (say 20%), you are likely to never arrive at the target phrase. A high value of P simulates an early universe, or any environment with a high natural radioactivity level. In one experiment where I set P to 20%, it took 800 generations, while a P value of 1% reached the target phrase after only 90 generations.

I also played with much longer target phrases with a length of more than 150 letters. What I’ve found is that the longer the phrase gets, the more detrimental a high mutation probability becomes. If you think about it, that’s not surprising, as the likelihood that already matching letters are replaced again with non-matching letters increases. Conclusion: the evolution of complex life-forms requires an environment that provides the right mutation probability—neither too low, nor too high. But while a low mutation probability can always be compensated by time (evolution will just progress slower), a high mutation probability stifles evolution entirely.

Anyway, while the weasel program is a blatant simplification of real life, I think it’s a great tool for demonstrating that random variation combined with non-random cumulative selection can produce complex structures. This is what evolution is all about; not monkeys hacking away at keyboards and winds blowing through airplane junkyards.

Share and Enjoy!

## Simplified I: Idiot Tax

“If you can’t explain it to a six-year-old, you don’t understand it yourself”
— Albert Einstein

The opening quote is attributed to Albert Einstein, even though it’s unlikely that he used these exact words. Nevertheless, the idea behind it has always resonated with me: If you explain something in easy words the person at the receiving end can immediately grasp it and is enlightened forever. But reducing a topic to its essence and explaining it from the vantage point of somebody else is even well worth the time for the one at the giving end: As always, the teacher learns the most.

I recently held an embedded programming workshop for kids and what I took home is this: if you pick the right examples and metaphors, even 12-year-olds can understand topics like pulse-width modulation. With this post, however, I want to address adults; specifically, I want to talk about something that has puzzled me for quite some time: why do people, even highly educated people, take part in lotteries?

A common knee-jerk reply is that everyone wants to get rich quick, without earning it. But that’s not the answer I am looking for. Let me refine my question: why do people play lotteries even though they know that the odds of winning are infinitesimally small?

Let’s take the German lottery system as an example. In order to become a millionaire, you have to get six numbers right, out of a total of 49. According to their official website, the odds to get these six numbers right are 1 to 15.537.573, or roughly 1 to 15 million.

Even though our gut feeling tells us that this is quite unlikely, we completely underestimate how unlikely it really is. Why? My guess is that it’s because we hear about figures that are in the millions every day. This guy is a millionaire, and that one even a billionaire. Government spends millions here and billions there. Still, we are nothing more than remotely acquainted with large numbers; we constantly fail to truly and fully comprehend them.

Let’s use an approach that has helped me quite a lot and treat big numbers like distances. What the human species has done for thousands of years is walk, so we naturally have a good grasp on distances. Let’s pretend we have a distance of 15 million centimeters.

15 million centimeters divided by 100 gives us 150 thousand meters, which equals 150 kilometers. People are especially good at understanding kilometers. 150 kilometers means roughly a two-hour car ride on a regular country road. That’s quite a distance, isn’t it?

Further, imagine a single M&M chocolate piece. It’s diameter is roughly one centimeter, give or take. Put one M&M after another, on a single straight line that is 150 kilometers long and you get what the number 15 million looks like. Somewhere along that line, there is that one special M&M where they printed a “\$” sign on the back, instead of the usual “m”. So you drive along this 150 kilometer line with your car, stop at some random point and flip a single M&M of your choice, hoping to see a “\$” sign on it’s back.

Now, how much money would you invest in such a bet? I don’t know about you, but I wouldn’t even invest a single cent. While it’s not impossible to win, it’s very, very improbable. Any money would surely be gone.

This is why the enlightened call lotteries “idiot tax”. It’s the tax that people—out of greed and ignorance—pay voluntarily.

## Oops, They Did It Again!

“There are no secrets that time does not reveal.”
— Jean Racine

In an act of unprecedented arrogance, Apple once again dictated to their users what they believe is good for them — this is yet another example of how they take away their users’ freedom.

Yesterday, they finally admitted what measurements by various users had suggested earlier: one year ago Apple introduced a feature that deliberately slows down the performance of older iPhone models in order to “deliver the best experience to their customers”.

This is, of course, total BS. It’s obvious that the real motive was to boost sales of their new products. Why? Because they kept it secret. Period.

If they really had the best of their customers in mind, they would have announced such a drastic step in good time. Further, they would have given their users a choice (something totally alien to them) by presenting a simple opt-in dialog:

Dear loyal customer, we’ve discovered that the capacity of your phone’s battery has become low. We strongly suggest that you either a) buy one of our latest models, b) replace your battery (which will cost you many \$\$\$, because you can’t do it yourself), or reduce the CPU performance which will DELIVER THE BEST EXPERIENCE to you. What do you want us to deliver to you?

1. Our latest iPhone model
2. A replacement battery
3. The best experience

Some time ago, I wrote a post which details why I don’t buy iThings and this recent incident just adds to the list. However, I’m enough of a realist to doubt that it will reduce the total number of iThings under this year’s Christmas trees.

## The Right to Choose

Shame on me! For the first time in a decade, I forgot to celebrate Towel Day. The fact that my towel proved so incredibly useful a couple of days earlier makes me feel even guiltier.

Douglas Adams is admired by most of his fans because he was not just tremendously funny, but also a shrewd freethinker who loved to show people how limited and simple-minded their views and beliefs are (anyone remember the Total Perspective Vortex?). But actually, he himself had his eyes opened one day by another person: in an interview with BBC, Douglas Adams disclosed that one of the most influential, eye-opening books he had read was “The Blind Watchmaker” by Richard Dawkins.

In his book, Richard Dawkins demonstrates that by Darwin’s Theory of Evolution and natural selection enormous complexity can arise out of even the simplest building blocks and that there really is no need for a Creator. Douglas Adams and Richard Dawkins were so like-minded that it’s no wonder they later became close friends.

At the end of one of his talks, Richard Dawkins presents a slide titled “The Illogic of Default”, which demonstrates the ill-reasoning of many Creationists:

1. We have theory A and theory B
2. Theory A is supported by loads of evidence
3. Theory B is supported by no evidence at all
4. I can’t understand how theory A explains X
5. Therefore theory B must be right

This exactly describes what happend to me one day when a muslim taxi driver tried to “prove” to me that there indeed must be a god. “See”, he said, “the theory of evolution just can’t be right. If we humans are really decedents of animals like apes and dogs, why are there still apes and dogs around?”.

I refrained from arguing with my taxi driver, even though it was obvious that he didn’t understand the Theory of Evolution at all. How could I resist the temptation?

I absolutely admire Richard Dawkins for his wit and I recommend that you watch all of his Youtube talks and videos, but there is a problem with atheists like him: sometimes, they are just as annoying as followers of any other conviction when they try to foist their views on others. Even if we know that Creationist’s arguments are utterly wrong from a logical and scientific point of view, it doesn’t help: it’s a documented fact that a significant part of humankind has a strong desire for spirituality. And, as we all know, whenever strong desires are involved, appealing to logic doesn’t work: drug addicts do know that drugs ultimately kill them but they nevertheless don’t quit.

Likewise, deep in their hearts, many believers in god assume that there is no god, at least not one like the one that is depicted in the holy scriptures, but they need a god for their mental well-being, anyway. Trying to prove to them that there is no Creator is a) futile and b) hurts them — not physically but emotionally. This is why I didn’t argue with the taxi driver. I strive to follow the Golden Rule, which — incidentally — also appears in many holy scriptures: always treat others the way you want to be treated.

So why I and many other people prefer to have their eyes opened, others don’t. Everybody should be free to choose the color of the pill they take.

## Working the Bash Shell Like a Pro

“People drive cars with steering wheels and gas pedals. Does that mean you don’t need wrenches?”
— Rob Pike

I’ve always preferred command-line interfaces (CLI) over GUIs. If I use GUIs at all then it’s mostly for browsing the web. Luckily, there is a plugin for my web browser that allows me to do most of my surfing using vi keystrokes. Yes, I try to avoid the mouse as much as I can.

I believe that most people who prefer GUIs either are bad at typing or haven’t taken the time to learn to use a CLI in an idiomatic way. With this post, I want to share some Bash CLI idioms that can significantly improve your efficiency. I don’t aim for a complete list — I rather present a compilation of the most frequently “not-known” techniques that I’ve encountered when I observed people working with Bash.

THE BASICS

First of all, make sure that you have enabled the command-line editing mode that suits you best. You are much more productive when your favorite shortcuts are available:

Often, we need to do something that we’ve already done before. You can easily re-execute the previous command with this shortcut:

Courtesy of this operator, forgetting to put ‘sudo’ in front of a command is not a big deal:

If you want to re-execute “one of the previous commands” instead of the last one, you could use the following abbreviations:

However, I don’t find these history expansions particularly useful. Often, going through the history by pressing ‘Arrow Up’ is equally fast.

The real game changer, however, is CTRL-R. Press CTRL-R and start typing any characters from one of your previous commands. This will start a backwards search through your command-line history and present you with the most recent command containing the characters you typed (or continue to type). Pressing CTRL-R again will find the next most recent command and so on. If you only partly need what you typed in the past, no problem — you can always edit the command-line that CTRL-R found before executing it.

MORE FUN WITH WORD DESIGNATORS

If you want to rename a file, please don’t do it like this:

Even with TAB completion, this requires too much typing. Why not reuse the path of the first argument?

‘!#’ is a shortcut for “the command-line typed so far” ‘:1’ selects the first argument and ‘:h’ strips off the last component (ie. “oldfile”).

In some cases, you don’t want to rename the file entirely but only change the extension. This can be achieved in a similar fashion:

You guessed it: ‘:r’ removes the file extension.

What if you did a mistake and wanted to undo this change? Again, that’s quite easy if you know the trick:

Which translates to “do another move but swap the arguments from the previous command”.

Sometimes, my fingers get ahead of me and I type ‘vm’ instead of ‘mv’:

Of course, you can always edit the last command be pressing ‘Arrow Up’ and change ‘vm’ to ‘mv’, but the following is much easier to type:

‘!*’ is a placeholder for “all arguments of the previous command”.

The word designator that I use the most — by far — is ‘!\$’; it expands to the last argument of the last command:

Many times, people gratuitously reach for the mouse to copy the output of a previous command in order to use it as an argument for another command. Why not use ‘\$()’ to capture command output?

SOME EXTERNAL HELP

If I was asked to name my favorite standard command-line tool, no doubt I would pick ‘xargs‘. Even though it is largely useless by itself, it’s the superglue that allowes you to build powerful command-lines. It takes the output of a command and uses it as arguments for another one.

Here’s an example that uses ‘xargs’ to build a tar archive containing all the C files that contain C++ comments:

In rare cases, when I have to do work that involves complicated selection/filtering, I reach out for TUI (usually ncurses-based) applications like ‘tig‘, ‘vifm‘, or ‘mc‘ that run in the shell and can be fully operated by the keyboard. Nevertheless, I first try to get by with the simpler ‘menucmd‘ tool. Here’s an example that builds a menu from all shell script files found in a directory. If the user selects an item, the specified action (‘cp -t /tmp’) is executed on it.

There you go. Even if this bag of tricks is not complete I hope it will serve you well. As always, in order to use a tool efficiently, you have to invest in learning how to use it idiomatically*. But this investment pays nice dividends in the medium-to-long term.

*) What’s the idiomatic way for vi users to underline a headline? 1. Yank the headline (‘yy’). 2. Paste the yanked headline under the exiting headline (‘p’). 3. Select the second headline (‘V’). 4. Replace every character in selected line with an underscore (‘r-‘) — that’s only six keystrokes! Awesome!