These are some of my favorite acronyms. I like them not only because they are funny but also because they sometimes contain a kernel of truth. I’ll be adding to this list over time.

• ISAF = I suck at fighting, I saw Americans fighting
• job = just over broke
• army = ain’t ready for Marines yet

Post your favorite acronyms below.

My birthday according to the Gregorian calendar is September 23, 1988. But the Gregorian calendar seems a bit passé. So this year I will celebrate my birthday according to the Chinese calendar.

To calculate your Chinese calendar birthday go to Baidu’s calendar converter; go to the year, month, and day of your birth; hover over that day and note the 农历 month (月) and day (曰). Mine is the 8th month and 13th day. Now go to this year and hover over dates in a similar range until you see the same month and day. This year, my lunar birthday is September 10, 2011 instead of September 23 and next year it’ll be September 28.

1. There is a single position to fill.
2. There are (n) candidates for the position, and the value of (n) is known.
3. The candidates, if seen altogether, can be ranked from best to worst unambiguously.
4. The candidates are interviewed sequentially in random order, with each order being equally likely.
5. Immediately after an interview, the interviewed candidate is either accepted or rejected, and the decision is irrevocable.
6. The decision to accept or reject a candidate can be based only on the relative ranks of the candidates interviewed so far.
7. The objective is to select the best candidate with the highest possible probability.

The optimal strategy is to reject a certain number of candidates. Call the number of rejected candidates (k-1), where (k) is the first candidate that won’t be automatically rejected, ie that you’ll actually consider. We will refer to this let (k−1) go by strategy as strategy (k). Let (M) be the best candidate among these (k-1). Then choose the first subsequent candidate that’s better than (M).

So if we’re given (n), what (k) should we pick to give us the highest probability of picking the best candidate? What is this probability? What happens when (n) goes to infinity?

Let (p_{n}(k)) be the probability of choosing the best candidate with (n) candidates using strategy (k).

Case (bf{n = 3})

We list the 6 permutations of ({1, 2, 3}). 1 is the best, 3 the worst.

• 1, 2, 3
• 1, 3, 2
• 2, 1, 3
• 2, 3, 1
• 3, 1, 2
• 3, 2, 1

Possible values for (k) range from 1 to 3. If (k=1), we always pick the first candidate. If (k=3), we always pick the last. If (k=2), we always reject the first candidate and pick the first subsequent candidate that’s better than the first. So if the first candidate was 2, we end up picking 1. If the first is 3, we end up picking 1 or 2 depending on which one we see first. If the first candidate is 1, we never find a better candidate and end up picking the last one. Tragic.

Now we list (p_{n}(k)) for each value of (k):

k

(bf{p_{n}(k)})

1

1/3

2

½

3

1/3

(k=2) is optimal.

Case (bf{n = 4})

There are 24 permutations of ({1, 2, 3, 4}). 1 is the best, 4 the worst.

k

(bf{p_{n}(k)})

1

6/24

2

11/24

3

10/24

4

6/24

(k=2) is optimal.

Case (bf{n = 5})

There are 120 permutations of ({1, 2, 3, 4, 5}).

k

(bf{p_{n}(k)})

1

24/120

2

50/120

3

52/120

4

42/120

5

24/120

(k=3) is optimal.

The general case
For n candidates, let (X_{n}) denote the number or arrival order of the best candidate, and let (S_{n, k}) denote the event of success (that we pick (X_{n})) for strategy (k). All orderings/permutations of the candidates are equally likely so (X_{n}) is uniformly distributed on ({1, 2, …, n}).

There are two ways we can fail:

1. the best candidate is among the first (k-1)
2. the best candidate is not among the first (k-1) but is preceded by a candidate with a higher score than any in the first (k-1)

Since we can only pick one candidate from (k) to (n) and these events are exclusive, the probability of picking the best candidate is the sum of the probabilities that the one we picked is indeed the best.

So what’s probability that we succeed by picking a particular candidate? It’s the probability that this candidate is the best multiplied by the probability that we’ll pick him. This second part is very important. It can be rephrased as the probability that the best candidate before him was in the first (k-1). He has to be the best and no one before him can be better than the ones we automatically rejected. Since (X_{n}) is uniformly distributed on ({1, 2, …, n}), the probability that any particular candidate is the best is (1/n).

We calculate the probability of succeeding with candidate (k). The probability that he’s the best candidate is (1/n). The probability that the best candidate before him is in the first (k-1) is 1. So the probability of succeeding with candidate (k) is (1/n cdot 1 = 1/n).

We calculate the probability of succeeding with candidate (k 1). The probability that he’s the best candidate is (1/n). The probability that the best candidate before him is in the first k-1 is (frac{k-1}{k}). So the probability of succeeding with candidate k is (1/n cdot frac{k-1}{k} = frac{k-1}{nk}).

We calculate the probability of succeeding with candidate (k 2). The probability that he’s the best candidate is (1/n). The probability that the best candidate before him is in the first (k-1) is (frac{k-1}{k 1}). So the probability of succeeding with candidate (k) is (1/n cdot frac{k-1}{k 1} = frac{k-1}{n(k 1)}).

…

We calculate the probability of succeeding with the last candidate. The probability that he’s the best candidate is (1/n). The probability that the best candidate before him is in the first (k-1) is (frac{k-1}{n-1}). So the probability of succeeding with candidate (k) is (1/n cdot frac{k-1}{k 1} = frac{k-1}{n(n-1)}).

We sum up these probabilities.

begin{align}
p_{n}(k) &= mathbb{P}(S_{n,k}) = frac{1}{n} frac{k-1}{nk} frac{k-1}{n(k 1)} ldots frac{k-1}{n(n-1)}\
&= frac{k-1}{n} sum_{j=k}^n frac{1}{j-1}
end{align}

So what’s the optimal strategy for (n=100)?

The maximum for (y) or (p_{100}(x)) is about (x=38) with (p_{100}(38) approx 0.37104). So given 100 candidates, we should reject the first 37.

Using Drake’s Equation to estimate eligible individuals
The Drake equation is used to estimate the number of detectable extraterrestrial civilizations that might exist in the Milky Way.

[
N = R* cdot f_{p} cdot n_{e} cdot f_{l} cdot f_{i} cdot f_{c} cdot L
]

(N) = the number of civilizations in our galaxy with which communication might be possible
(R*) = the average rate of star formation per year in our galaxy
(f{p}) = the fraction of those stars that have planets
(n{e}) = the average number of planets that can potentially support life per star that has planets
(f{l}) = the fraction of the above that actually go on to develop life at some point
(f{i}) = the fraction of the above that actually go on to develop intelligent life
(f_{c}) = the fraction of civilizations that develop a technology that releases detectable signs of their existence into space
(L) = the length of time for which such civilizations release detectable signals into space

New York City population 2010: 8,175,133
percentage women: 52.62%
20-26 years old: 10.8%
bachelor’s degree: 15.8% http://www.city-data.com/city/New-York-New-York.html

http://newyork.areaconnect.com/statistics.htm

For quite a while now I’ve logged onto Facebook only to close the tab five minutes later feeling unsatisfied. But until recently I couldn’t put my finger on why I consistently had an unpleasant experience. I slowly began to realize that one of the primary reasons was the Law of Internet Entropy.

The Law of Internet Entropy states, as my friend friend once told me, “Websites eventually become Craigslist.” There are many examples of online communities and websites losing their niche and eventually catering to broad interests. It takes energy to maintain a focused service and well-defined community.

Stanford has a great library of resources for learning basic data structures like linked lists and binary trees. The implementations are in C. Pointers are also covered.

A Tutorial on Pointers and Arrays in C

Learning new things requires effort. After a long day at work, I just want to knock back some beers and watch Jersey Shore. But I found some simple steps to learn without feeling like it’s forced. I will be adding to this list over time.

• Every time I’m about to watch Youtube videos of cats, I watch a video lecture from MIT’s Open Course Ware instead.

I was writing C code the other day in my favorite Mac OS X text editor Coda. But I noticed Coda lacked C and C syntax highlighting. Then I found this helpful post on how to add them in 6 simple steps.

1. SubEthaEdit version 2.2
2. Unzip the download, right click, select “Show Package Contents”
3. Go to Contents > Resources > Modes, and copy the appropriate .mode files
4. Right click on Coda and select “Show Package Contents”
5. Go to Contents > Resources > Modes, and paste the mode files
6. Check it works when you restart Coda

A month ago I wrote about how to scrape data from Pfizer’s doctor payments records. Pfizer lost a $2.3 billion lawsuit that alleged it had illegally marketed four of its drugs “with the intent to defraud or mislead” by promoting them for non-approved uses. Pfizer is one of eight drug companies that have begun publicly publishing this data.

So why scrape if it’s already public?

My friend Jonny is a time traveler from the Roaring Twenties. Today he taught me how to write a party invitation if I ever found myself in the Jazz Age.

You are invited…

Listen up you swell flyboys and Jane’s!

It’s an old-fashioned speak-easy, so bring your bootleg and giggle water. We’re looking for the finest dolls…you know a choice bit of calico but none of those dumb Doras. Don’t forget to be on the lookout for squirrels, we don’t need the law getting an earful of the fun.

I’ve got to scram for now, but this carousing is sure to be a cat’s meow.

Get ups: Fellas – A flat cap or fedora. Dolls – Cloche hat and bobbed hair

Address: The Gin Mill, or as some other fellas style it, 200 Oak Avenue Apt. 12, New York City

Time: Past sunset but ahead of the small hours, or as you flappers say, 10:30 PM