Archive for February, 2012

February 29, 2012

Partition Function

February 28, 2012

5 = 5
5 = 4 + 1
5 = 3 + 2
5 = 3 + 1 + 1
5 = 2 + 2 + 1
5 = 2 + 1 + 1 + 1
5 = 1 + 1 + 1 + 1 + 1

There are 7 ways to split up five things. Seven different ways you could divide up 5 balls, 5 dolls, 5 wrapped-up candies; seven microstate subsets of a 5-molecule gas.

How many ways are there to divide up 4 things? 8 things? 20,000 things? 198^198 things? Even if you had a few days to write a computer program that would brute-force count these things, how would you do it?

I would try to come up with a way to “break one off” from the largest number and count the “leaves” off each branch, somehow trying to remember to go back and “break off two” — and make sure I haven’t forgotten any other contingencies. It wouldn’t be pretty (although perhaps it would be prettier in a functional language).

Here are the first few answers. I don’t see an obvious pattern

  • 1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565, 5604, 6842, 8349, 10143, 12310, 14883, 17977, 21637, 26015, 31185, 37338, 44583, 53174, 63261, 75175, 89134
     
 

The answers to this line of questions—which answers are given by the partition function — come up in weird places en route to the answer to some other question. For example, the partition function comes up in thermodynamics. WTF? Don’t ask me, I didn’t make up the universe, or logic. The partition function also shows its face when you try to reason out measures of statistical validity. That at least makes sense because these partitions are combinatoric in character.

But back to the question—how would you figure out NumPartitions(1), NumPartitions(2), NumPartitions(3), … and so on? Is there a formula for it? Or do you just have to find 20,000 stones and start breaking them up into groups (or simulate such on the computer) to find out NumPartitions(20,000)?

Herbert Wilf explains here

that there is a better way to express the outcomes of the Partition Function. (Much better than my program idea.) First you have to know that you can encode sequences as polynomials. Second, recognise that the sequence / polynomial coefficients represent a function from ℕ→ℕ (How many ways to divide up 1? p(1) How many ways to divide up 8? p(8). Etc.). It’s called Euler’s generating function. Using the sequence polynomial trick, you can say “The entire sequence of answers to p(n) for n=1 thru can be written ∑p(n •x^n.” (Because the polynomial encodes the sequence.)

Third, here is the answer:

Essentially, if you “multiply” together the sequences [0,1,2,3,4,5,...] , [0,2,4,6,8,...], [0,4,8,12,16,...] , and so on, you get the appropriate sequence of outputs that answers the partition question.

Wow. First of all, whoever figured this out should be crowned king of innovation for 100 years. Second of all, why is Nature so weird? I mean, this result seems way too simple to be true. Third of all, given what I said about polynomials as sequences, now we’ve established a way to factor a certain sequence (the partition sequence) into products of sequences. I wonder where else you could go with that—either analogies, or tweaking-the-pattern a little bit, or applications of this exact idea to other fields where you wouldn’t normally think to yourself “Here I have a polynomial.”

So. From candies to statistics to number theory to thermodynamics to algebraic rings to who knows how to describe what we have seen here. Such a simple question to ask, with a complicated answer, but somebody has figured out how to make it easy after all. All I can say is, I’m not making this stuff up.

Where do theories come from?

February 27, 2012

While science rightly uses empirical evidence (facts) as the ultimate arbiter of truth, those who experiment and analyse field data usually only credit or discredit ideas / frameworks that some theorist has previously invented.

Science: We finally figured out that you could separate fact from superstition by a completely radical method: observation. You can try things, measure them, and see how they work! Bitches.

Tagline. Science: We finally figured out that you could separate fact from superstition by a completely radical method: observation. You can try things, measure them, and see how they work!

Hence the name “theory-killers” for experimental physicists.

 

Where do these theories come from, though? My own experience and my observations of others lead me to believe that an economic theorist’s deep creative centre is informed, flavoured, shaped, and sullied by her own personal experiences, biases, stereotypes, and assumptions about what’s normal. If you talk to people who have deeply integrated into their psyche concepts like “opportunity cost”, “rationality”, “search”, “strategy”, “information”, “evolution”, “optimisation”, and so on, and you disagree with this statement, please tell me.

(For example: a professor of game theory told me that he cannot fathom the motivations of a suicide bomber. He can’t fathom them, so he can’t model them, so we have no theory to predict and curtail their bombing behaviour.

Example 2: Do you think Daniel Ellsberg started running psychological experiments at random until he stumbled upon his famous “Ellsberg Paradox”? No, he had the idea in his head that these two kinds of “uniform distribution” should be different—perhaps getting the idea from Keynes or Frank Knight—and then tested the idea.)

Since there’s a “lone genius” limit on novel* economic theories, a finite upper bound follows on how much fact-checking can improve a theory’s soul. Although one can certainly benefit from pulling on threads, reading monographs, looking at data tables and so on, ultimately I believe deep insights come from the same brain process that generates the fallacy of lack-of-imagination (argumentum ad ignorantiam). Just as people form judgments by the “Does this fit with what can I imagine” test, so too—says I—do economic theories rise from the same murky pit. Personal experiences where we’ve taken in reams of high-dimensional streaming data (like at work) feed this imaginative capacity, such that we can run and assess counterfactual dramas in our heads (sort of like a Monte Carlo). “What if the vendor had said this to my boss? Nah, she wouldn’t have reacted that way. Not like her.” There are some biologists who say that our brains have an especial capability to think through such human dramas. (And in writing that sentence I used the same often fallacious imaginative faculty.) The imaginative faculty is abused by cheap stereotypes—

Ideas can be checked against experiences and personal symbols much more easily than against a tome of facts. Since theoretical creativity proceeds in inspirational flashes and needs to run verificational checks at the speed of imagination, only the checks that can be done very quickly influence the creative process.

* Of course most theories derive from the joining of ideas from the existing literature. But those aren’t “novel” ideas.

It’s my conviction, therefore, that theoretical economists would come up with better theories if they spent more time in “the real world” and less time thinking about isomorphisms.

 

The problem is more acute in economics than in physics, because economic theories are much harder to kill (so many alternative explanations / dismissals one can retreat to) — which shifts some of the burden of correctness to the theorists. If you know that

  1. a compelling idea (like “Those who spend other people’s money will be wasteful”) will be hard to falsify;
  2. it will spread memetically through influential minds;
  3. it’s important to get this right, or else the former USSR and Latin American countries (𝓞 1 billion people) will be screwed over by your idea

then you would be quite reasonable in polishing & perfecting a theory—working to cleanse yourself of biases and myopia, asking yourself if what you’re writing is really quite true, what are the underlying assumptions, and so on.

The problem is also more important for economic theorists to address because those who theorise about the human mind have, erm, direct access to the thing they’re theorising about.

The difficulty of killing an economic theory has been discussed much elsewhere:

and if you read the things I read, you’ve probably had similar thoughts as:

  • “Really? It took this long for ‘neoindustrial’ ideas like ‘The economics of serfdom differ from the economics of a modern web programmer’ to become acceptable?” And neo-industrial uses a totally neoclassical approach but just in a meta context—rational response to the incentives that come with a social framework, or perhaps game theory rationally optimising evolution rather than individuals.
  • “Really? People think you can just use a probability distribution to model a person’s or a firm’s thought-process?”
  • “Really? We just shrug off counterevidence to the theories by saying they’re only models?”
  • “Really? Real numbers and Lagrangians are underlying all of this?”
  • “Really? It’s so controversial that utility is derived from relative and not absolute wealth?”

and many others. Point being, if you are educated on this stuff, then I’m sure you can see how the Slutzsky decomposition is a compelling advance in “research technology”, but can’t carry over as-is to the ultimate subject of interest, which is human behaviour and feelings.

 

Am I just carping? A bit, but I also can propose something like a solution. If those who give out grants for economic research could be convinced that

  • business experience
  • time spent in poor countries
  • experience in a variety of economic roles outside of academia

were important indicators of future relevancy and correctness of research—along with knowledge of a body of literature, knowledge of mathematical/statistical/experimental methods, consulting/political experience, and/or a Ph.D.—then up-and-coming economists would have the incentive to spend time in “the real world” and find out, in a personal way, what the people they theorise about go through.

February 27, 2012

February 27, 2012

[I]n the late 1920’s and early 1930’s…. There were lots of deep thoughts [in economics], but a lack of quantitative results. … It is usually not of very great practical or even scientific interest to know whether the [causal] influence [of some factor] is positive or negative, if one does not know anything about the strength.

But much worse is the situation when an [outcome] is determined by many different factors at the same time, some factors working in one direction, others in the opposite directions. One could write long papers about so-called tendencies explaining how this … might work…. But what is the … total net effect of all the factors? This question cannot be answered without measures of … strength….

Trygve Haavelmo

Bank of Sweden pseudo-Dynamite Prize Laureate 1989, for work in econometrics

February 27, 2012

Let Go by jj

February 26, 2012

The Newtonian view of a smooth background space which acts as a container in which the events in the universe take place is giving way to the view of Leibnitz (sic) in which the contents of the universe themselves give rise to space.

Burra G. Sidharth

February 26, 2012

I don’t want to deal with myself. I don’t want to exist. I just want to think.

Slavoj Žižek

February 26, 2012

Robin Pecknold – False Knight on the Road

February 26, 2012

False Knight on the Road sung by Robin Pecknold