The Trimph of (Almost) Certain Uncertainty

You’ve probably heard of Nate Silver. Maybe? If you are in the category of people that don’t know who Nate Silver is, there are 5 possible reasons you haven’t heard of him (not necessarily sorted in order of ridiculousness): you don’t use twitter; if you do, you probably didn’t check out your twitter trends days leading to the 2012 presidential election (or even during the election); you don’t read news that much; all the people on twitter that you follow either don’t care about the election that much or don’t read news that much; you aren’t a Republican pundit.

I’d call myself a news addict. I love reading news whenever I need to take a break. It’s a good way to get out of the flow of work but still learn stuff. But I didn’t know who Nate Silver was until few weeks before the election – specifically during Hurricane Sandy. During Sandy, I didn’t expect to see any thing that’s not related to the Superstorm trending on twitter. But there was Nate Silver’s. Maybe he’s the director of FEMA, I contemplated. So I researched him a little and found lots of information about him, mostly criticisms (at that moment).

I learned about the past successes of Nate Silver in almost accurately predicting the performances of baseball players in Major League, his perfect forecast of the outcome of the 2008 Presidential election. Nate, apparently, uses complex statistical models to predict elections. His models, I think, are mostly hinged on calculating weighted averages of polls appropriately. This, surprising, is a non-trivial task because of the volatility of election polls and the disparity between different election polls. You can’t give the same weight to all polls. Factors like method of polling, polling demographics, party affiliation, accuracy of past polls, and other factors must be considered. For example, during the election, some polls like Gallup and Rasmusseen stood out of all the others. Their results predicted that Romney will win the Presidential election by a comfortable margin. So determining the amount to weight the polls coming in can be hard sometimes. But Nate Silver is on top of his game. He correctly predicted the winner of 49 of the 50 states in the 2008 presidential election. This won him much fame and acclaim. Consequently, he was named one of the World’s 100 Most influential people by Time magazine. Wikipedia has some information on Nate Silver and his accomplishments. Also, Nate’s book, The Signal and the Noise, was published in September 2012.

But all the fuss about Nate Silver during Hurricane Sandy wasn’t because everyone loves and agrees with him. It was because Nate Silver was being heavily criticized for the apparent bias in his prediction models. Some notable political pundits (mostly republicans), including Karl Rove, criticized Nate Silver for trying to help Obama win the election (via the “Mehrabian Polling Snowball Effect”, I guess). On the eve of the election, Nate Silver said there was a >90% of Obama winning the election. Some Republicans called it “gobblygook.” Dean Chambers dismissed Nate Silver as a “thin and effeminate man with a soft-sounding voice” who skews polls in favor of Democrats. Nate, of course, disagreed (in fact, laughed it off). He knew he was going to have the last laugh.

And he’s the one laughing now. He correctly predicted the winner of all 50 states and the District of Colombia (for the Presidential election). What a boss! His profile as a renowned statistician has never been higher. His profile as a celebrity is equally high. Twitter is now commandeered by a ‘Drunk Nate Silver’ (@nateDRUNKsilver). And, apparently, Nate Silver’s a witch (or wizard, rather).

Yes, he predicted almost accurately the results of both the 2008 and 2012 Presidential elections. Yes, he seems to have a skill to identify and
differentiate the “Signal from the Noise”  (that’s Nate Silver’s book– at the time of writing, it’s the #2 Best Selling book on Amazon). But does this
mean that the result of his predictions made him stand out. I certainly don’t think so. Last Febraury, The Signal predicted that Obama would win
reelection. They predicted the outcomes of the Presidential election in 50 out of 51 states accurately. Why? Because the question of who’s going to win a Presidential election in a particular state is a 0-1 question. No one’s talking about these folks even though their predictions were almost accurate. Why? The more the hype/controversy about your prediction accuracy/magic, the more the hype about your prediction models, and consequently the more popular you are.
That’s why Nate’s popular right now: there’s too much hype about the accuracy of his predictions. 

Solution to Problem 3: Gotta Max Profits

Another way of the stating the problem is: determine the maximum value subarray from the array of “crude” stock price changes. This is reducible to the maximum value subarray problem (oh yeah!).

There are three known ways (specific to my knowledge thus far) of solving this problem:

  • brute-force:  list all n(n-1)/2 (“n choose 2”) possible subarrays and determine which subarrray has the maximum value. O(n^2) running time.
  • divide-and-conquer: there’s a divide and conquer algorithm that runs in O(nlogn) time. It’s kind of cool but not as fast as we’d want it to be.
  • dynamic programming: this solution runs in O(n) time. What would we do without dynamic programming?

Below is the solution (using dynamic programming) to the maxSub array problem in python:

Recurrence relation for maxSub array problem

Given a sequence of n real numbers A(1) \ldots A(n), determine a contiguous subsequence A(i) \ldots A(j) for which the sum of elements in the subsequence is maximized.

For any i and j where 1 <= i <= j <= n
M(j) = Maximum sum over all windows ending at j.

M(j) = max \{ M(j-1) + A[j], A[j] \}. So either we extend the optimal window ending at j or start a fresh window with A[j].

Chao!

Problem 3: Gotta Max Profits

I’m a determined and ferocious trader on wall street. I only care about maximizing profits. An adaptive manipulator, I’m always the first person to react to (or rather to help my company adapt to) changes in the rules of the wall street money game. Yesterday, some rules pertaining to profits displays (on the floor of the main market) got changed.

Hitherto, maximum profits made by my company were displayed on the floor in a simple and intuitive way. So the only thing we needed to do to keep track of our max profits was to pipe the displayed maximum profits to our wall street data repository. But starting today, no maximum profits will be displayed. Only “crude” stock changes will be displayed. For example, the stock changes for the day (collected each hour) might look like this: [-2, 11, -4, 13, -5, 2].

Now I have to make some algorithm to compute the maximum profits I made during the day. For example, the maximum profit (from the data set above) is 20 over the subarray [11,-4,13].

Can you help construct an algorithm to solve this problem? I’m actually a good trader I promise.