Parking lots, self-interest, and risk

The section of the parking lot where I park at work is bounded on one side by a fence and on another side by a concrete wall. At the area where the fence and this wall come together at a 90 degree angle, there is a small opening that funnels everyone through a pedestrian gate--and you have to walk through this gate to get to the building. It is also important to note that the lots are very large, and do often fill up. So good parking spaces are coveted. Arriving late can mean a long walk.

While I typically arrive at work within the same 10-15 minute window, I have sometimes arrived as much as an hour or so later and often take interest in the parking patterns of people arriving for work (yes, really I do; sad isn't it!).

As you might expect, the earliest arrivals tend to park as close to the gate as possible, and then the lot fills in a rough, semi-circular arc from the fence to the wall. This would seem to support the notion that people's self-interest is walking as short a distance as possible to get into the building.

But there are exceptions to this rule.

Some people park farther off into the lot (or even the next lot), seemingly at random. I have heard some people express the notion that they purposely park further off specifically to walk further, for reasons of exercise. Ok, that makes sense, but it probably doesn't explain everyone who parks futher against their self-interest. Maybe people park further away, but closer to the parking lot exit anticipating an easier exit?

Between parking lots there are a small number of "street" style parking spaces. These spots fill up well in advance of the sweeping arc of arriving cars. Perhaps the notion of street parking feels safer? Perhaps this has to do with reducing risk (see next paragraph).

The most curious to me is the driver who parks close to, but not in, the next available spot. I suspect this entails a very quick calculation of risk. Let me explain. The process of parking involves a number of risks: fundamentally, you could hit someone else, or they could hit you (or both). Parking in a spot with no one on either side is the lowest risk for you (at least immediately), because there is virtually no way that you're going to hit someone else, either while parking or while opening your doors. On the other hand, parking in the next available spot encounters some risk: the chance of hitting the car next to you while parking or opening your door seems more likely. Lastly, squeezing into a spot with cars on both sides would appear to be the most risky from your standpoint, as you could hit more than one car.

So from the view of the driver, parking close to, but not in, the next available spot is a crude calculation that maximizes self-interest while minimizing the risk of hitting another vehicle. But wait, there's something missing here, and we've already touched on it. The risk is not only that you could hit someone else, but also that they could hit you. So let's return to our three scenarios, in reverse. Squeezing into a spot with cars on both sides would appear to be the most risky in terms of you hitting someone else, but the chances of those cars hitting you is nil because they're already parked. Parking in the next available spot is less risky to you as a driver but you're also passing a similar amount of risk to the next (future) driver who decides to park next to you. Finally, parking in a spot with no one on either side means that you're accepting virtually all of the risk that other drivers (who will eventually park on both sides of you) might hit you.

Let's simplify as much as possible and divide risk into two parts: the risk of you hitting someone else, and the risk of someone else hitting you. Furthermore, let's assume that on average, both of these are equally likely. This ignores the fact that drivers are probably, out of self-interest, more concerned about protecting their car than damaging another (even though in an accident both are probably going to occur).

If you are (more or less) of average driving and parking ability, it would make sense to take as much of the risk yourself, leaving nothing to the chance of some random, average driver. In this case, finding a spot with someone already on both sides is best. Next next would be to park in the next available spot, as you take perhaps half of the risk yourself and leave the remainder to the random, average driver. Lastly, parking in a spot with no one on either side seems to be the safest for yourself, but hands all of the risk off to both drivers who will inevitably park on either side of you. In your self-interest, to me this seems the worst option, yet it occurs quite a bit. Perhaps this is just an early morning decision based upon some notion of "out of sight, out of mind"?

Going back to the street-style spaces. If you were able to drive into one of these spaces rather than parallel park, you would have a curb on one side and the aisle of the parking lot on the other, so maybe this is the least risky of all of the options. Yet because they are further away, you're still sacrificing self-interest for lower risk.

I fully recognize that people do not drive into a parking lot with a head full of math, calculating risk to decide where to park; but I suspect people do have some preconceived notions about why they park where they do, and some of these notions may include some concepts of self-interest and risk.

Why do we itch?

This is a pretty fascinating (if sometimes graphic) article about why we itch and why we scratch.

Things that fascinate me

In Tom Clancy's book Red Rabbit, he speculates that the CIA might have altered the plumbing at the Blair House (the guest house for state visitors to Washington, D.C.) so that they could collect urine samples of foreign leaders for medical examination and exploitation. Obviously the book is a work of fiction, but Clancy's books have a tendency to be based on well-researched factual information.

Other than having had the job of organizing the collection of urine samples, I have no idea about the chemistry of its testing, nor if it could be collected and accurately analyzed in such a manner as described above. Still, it is a fascinating concept of spy tradecraft.

Solving simple substitution ciphers

An unintended tongue-twister, for sure!

A substitution cipher is perhaps the simplest form of cryptography: one letter is substituted for another. You may see these in newspapers or quiz books, sometimes called cryptograms.

I encrypted one of my recent posts and for the sake of space will only reprint the first paragraph here:

ZHTT XFSFH IZHTHG LZ FUH XHOITG USKV DWFU S NWA GHVHTXWMH ZKSE, SX GST OITTIC ZWOBHG IVV S FCIE XYWFU ZSXX FUSF DSX FWZZHG NE HG RIUTXIT. UIDHMHC, FUH TWFFSTE KWITX DHCH LTSNKH FI OSZWFSKWPH IT FUH FLCTIMHC STG BHMWT BHKKE YWXXHG S 42 ESCG VWHKG AISK.

(For the sake of this example, we can ignore numbers and punctuation as they are not encrypted.)

One of the strongest attacks against a substitution cipher is known as frequency analysis. This concept relies on the fact that some letters are used more often than others. Our assumptions here are two-fold: first, that the message is in English (otherwise our frequency rules wouldn't make any sense) and second, that we have enough cipher text to apply to the rules (how much is enough is a question for later). Theoretically, the more cipher text we have the closer it should approach the frequency rules. The post that I encrypted has 2,145 characters so let's see how it fares against our frequency analysis attack.

Using Microsoft Word, I used the 'Find and Replace' feature for each letter of the alphabet and replaced it with itself: the result is that Word tells me how many times the letter replaced itself, and thus, how many times it found that letter in the post. Here are the most frequent letters as they appear:

H: 255 times
F: 239 times
S: 181 times
T: 159 times
I: 156 times
...
R: 2 times

Frequency analysis tells us how often each letter of the English language appears:

E: 12.7%
T: 9.1%
A: 8.2%
O: 7.5%
I: 7.0%
...
Z: 0.1%

Let's begin by examining the cipher text and replacing the three most appearing letters with the respective frequency counterparts: H=e, F=t, and S=a (this also is slightly complicated by the fact that we also need to take the still cipher text E, T, and A and replace them with H, F and S to avoid further confusion):

ZeFF Xtate IZeFeG LZ tUe XeOIFG UaKV DWtU a NWS GeVeFXWMe ZKaH, aX GaF OIFFIC ZWOBeG IVV a tCIH XYWtU ZaXX tUat DaX tWZZeG NH eG RIUFXIF. UIDeMeC, tUe FWttaFH KWIFX DeCe LFaNKe tI OaZWtaKWPe IF tUe tLCFIMeC aFG BeMWF BeKKH YWXXeG a 42 HaCG VWeKG SIaK.

As you can see, there are three instances were S replaced with a is a single word: meaning "a" is probably correct. We also see "tUe" several times which is probably "the" meaning our other two corrections are probably also correct. It also gives us a clue that U is "h". What else can we solve? We see "aX" which likely means X=s since we've already used our "t" (so X=s and U=h, which are conveniently the 7th and 8th most frequent letters):

ZeFF state IZeFeG LZ the seOIFG haKV DWth a NWX GeVeFsWMe ZKaU, as GaF OIFFIC ZWOBeG IVV a tCIU sYWth Zass that Das tWZZeG NU eG RIhFsIF. hIDeMeC, the FWttaFU KWIFs DeCe LFaNKe tI OaZWtaKWPe IF the tLCFIMeC aFG BeMWF BeKKU YWsseG a 42 UaCG VWeKG XIaK.

Still a bit murky but we're starting to see some words emerge that make sense: state, the, a, that.

Fast-forward. It turns out that frequency analysis on this text is not perfect, but close: the sequence ETAOINSHRDLC are the twelve most frequent letters (in order) and make up over 80% of all letters. In my post, the most frequent were ETANOISHRLDU. Together you can see how close this becomes:

ETAOINSHRDLC
ETANOISHRLDU

Here is our final solution:

penn state opened up the second half with a big defensive play, as dan connor picked off a troy smith pass that was tipped by ed johnson. however, the nittany lions were unable to capitalize on the turnover and kevin kelly missed a 42 yard field goal.

As you can see, frequency analysis is an important tool in attacking a substitution cipher. We were able to take the cipher text and begin to exploit it.

But why the shortcomings? Perhaps we didn't use enough text. Perhaps my writing style is "different" enough that I use some letters in different frequencies. Also, the content is important: I use the letter "n" more frequently because of the words Penn, Connor, Nittany, Lions, which are used multiple times (in fact, "n" is the only letter in the 12-letter sequence that is off by more than one position). Also, the use of proper names is likely to throw off someone trying to solve a cryptogram. So perhaps a better source text would provide slightly better results.

The learning point of this post is that given such a problem, you have a good place to start. We can begin with frequency analysis and begin to uncover the meaning the cipher text. Further exploitation occurs by applying common sense when appropriate: the most common three letter words are the, and, but, for, and are (two of which I even used in this sentence). The most common two letter words are it, is, of, in, and to.

Have further questions about this post or about cryptography in general? Feel free to post a comment.

Things that fascinate me: the birthday paradox

I'm not much of a mathematician but this is a good one for you: How many people need to be in a room such that the probability of two of those people having the same birthday is greater than 50%?

This moderately famous math problem is known as the birthday paradox, even though it isn't technically a paradox. As Wikipedia puts it, "it is described as a paradox because mathematical truth contradicts naive intuition," in other words, the number is much smaller than people believe.

Before you read on, take a guess. How many people need to be in a room such that the probability of two of those people having the same birthday is greater than 50%? The answer is as follows.

Assumptions: we remove February 29th from the problem (sorry leapers); birthdays are spread equally among the remaining 365 days (apparently they are not, but I haven't found data to back this up, yet).

The problem is more easily asked in the opposite direction: what is the probability that no two people will share the same birthday?

364/365 = 0.997, or 0.3% chance that of two people they will share the same birthday.

For three people:

(364/365) x (363/365) = 0.992 (0.8%)

For three people:

(364/365) x (363/365) x (362/365) = 0.983 (1.7%)

And so on. As you can see, as more people are added to the room, the probability that no two of them share the same birthday decreases, and conversely, the probability that two of them will have the same birthday increases in turn.

Warning: answer follows!

It turns out that for 23 people in the room, the result is 0.493, or conversely, a 50.7% chance that two people in a room of 23 people will share the same birthday.

How close were you to the actual answer?

Things that fascinate me

How a statistical formula helped to win WWII

Reposted from the Guardian:

Here is a story about mathematical deduction that I love, mainly because it is said to be true, and because it had an impact (albeit small) on the outcome of the second world war. It is the story of how a simple statistical formula successfully estimated the number of tanks the enemy was producing, at a time when this could not be directly observed by the allied spy network.

By 1941-42, the allies knew that US and even British tanks had been technically superior to German Panzer tanks in combat, but they were worried about the capabilities of the new marks IV and V. More troubling, they had really very little idea of how many tanks the enemy was capable of producing in a year. Without this information, they were unsure whether any invasion of the continent on the western front could succeed.

One solution was to ask intelligence to guess the number by secretly observing the output of German factories, or by trying to count tanks on the battlefield. Both the British and the Americans tried this, but they found that the estimates returned by intelligence were contradictory and unreliable. Therefore they asked statistical intelligence to see whether the accuracy of the estimates could be improved.

The statisticians had one key piece of information, which was the serial numbers on captured mark V tanks. The statisticians believed that the Germans, being Germans, had logically numbered their tanks in the order in which they were produced. And this deduction turned out to be right. It was enough to enable them to make an estimate of the total number of tanks that had been produced up to any given moment.

The basic idea was that the highest serial number among the captured tanks could be used to calculate the overall total. The German tanks were numbered as follows: 1, 2, 3 ... N, where N was the desired total number of tanks produced. Imagine that they had captured five tanks, with serial numbers 20, 31, 43, 78 and 92. They now had a sample of five, with a maximum serial number of 92. Call the sample size S and the maximum serial number M. After some experimentation with other series, the statisticians reckoned that a good estimator of the number of tanks would probably be provided by the simple equation (M-1)(S+1)/S. In the example given, this translates to (92-1)(5+1)/5, which is equal to 109.2. Therefore the estimate of tanks produced at that time would be 109

By using this formula, statisticians reportedly estimated that the Germans produced 246 tanks per month between June 1940 and September 1942. At that time, standard intelligence estimates had believed the number was far, far higher, at around 1,400. After the war, the allies captured German production records, showing that the true number of tanks produced in those three years was 245 per month, almost exactly what the statisticians had calculated, and less than one fifth of what standard intelligence had thought likely.

Emboldened, the allies attacked the western front in 1944 and overcame the Panzers on their way to Berlin. And so it was that statisticians won the war - in their own estimation, at any rate.

More things that fascinate me

It's time for another edition of: Things that fascinate me.

Today's item is Steganography, defined as

the art and science of writing hidden messages in such a way that no one apart from the intended recipient knows of the existence of the message; this is in contrast to cryptography, where the existence of the message itself is not disguised, but the content is obscured.

If you read the Wikipedia article, you'll see that steganography isn't new. However, computers have made it more intriguing; hiding messages in images, MP3 files, etc.

On February 5th, 2001, USA Today announced that

[l]ately, al-Qaeda operatives have been sending hundreds of encrypted messages that have been hidden in files on digital photographs on the auction site eBay.com.

They provided no sources to prove this assertion, but it was nonetheless picked up and repeated by many news organizations. No evidence has ever shown this to have actually occurred.

Still, the concept itself is fascinating. Here's a small example. The two JCCS-1 logos below appear to be the same, but the second one has a hidden message.

The second image contains a small text file that says "Congratulations!" for figuring out the images are actually different. Lunch time is over; back to work!

Things that fascinate me

In the course of my reading I often push the limits of my knowledge and try to read things that are on the periphery of my interests. It is during these times that I often find things that absolutely fascinate me. Perhaps these things are less fascinating to those who study them every day.

One of the reasons I read so much is because I consider reading to be one part of a lifelong learning process. Just because you're out of school or college shouldn't mean that you stop learning. And even better yet, you ought to find something that you're curious about, but perhaps don't know much about.

That was the case several years ago when I picked up several books on the evolution/creation debate. One of those books was Darwin's Black Box: The Biochemical Challenge to Evolution by Michael Behe. Professor Behe is a biochemist at Lehigh University in Pennsylvania.

One of the subjects of Behe's book is the idea of systems that are "irreducibly complex." In other words, a system such that, if you removed any piece of that system, it would fail to work. For example, the common mouse trap. If you removed the spring, it wouldn't work. If you removed the wooden base, it wouldn't work. And so on.

Behe's example of an irreducibly complex system is that of blood coagulation or sometimes referred to as the blood clotting cascade:

Behe's basic argument is that if any of these steps are missing, the entire process would fail to work, and the blood would fail to clot. This would certainly lead to death. A good example of this is Hemophilia A, which is a Factor VIII deficiency. This deficiency is just one step of the entire process, yet is potentially fatal to those who have it.

Finding this system irreducibly complex, the larger argument is that it could not possibly have "evolved" and thus is an example of intelligent design or creation.

I don't presume to present Behe's argument as scientific fact; there are many in the scientific community who would argue for or against his work. Either way, the process itself is fascinating, as is the idea of irreducibly complex systems.