jlm-blog
~jlm

19-Aug-2010

Finger Multiplication

Filed under: math — jlm @ 12:39

“Finger multiplication” is an old trick for using the bottom-left (easier to memorize) quadrant of the times table to do multiplication in the top-right quadrant. It’s easy to work out why it works, but unsatisfying, but I found rederiving the technique gave more insight.

How might we do this? To go from one quadrant to the other, we subtract from 10, or generally from the base b: (b-x)(b-y) = b²-bx-by+xy
Well, there’s our xy term, to get it alone we want to subtract off b²-bx-by = b(b-x-y), which we can do by adding -b(b-x-y) = b(x+y-b). The factor of b is trivial to deal with, just use place value, so that leaves us with x+y-b. That’s easy enough to calculate on its own, but we can distribute the -b half to each number as (x-b/2)+(y-b/2). We have the numbers b-x and x-b/2 to do arithmetic on, these sum to b/2, the number of fingers on a hand, so if you hold up x-b/2 (x-5 for us pentadactyl folk) fingers on a hand, then the down fingers number b-x. And that’s how you do finger multiplication, hold up x-5 on one hand, y-5 on the other, put the sum of the up fingers in the tens place and the product of the down fingers in the units place et voilà.

Now that we’ve reverse engineered it for the existing use case, can we come up with something like it for others? How about the case where only one term is > 5 ?
We want to move this from the top-left to the bottom-left of the times table, so x∙(b-y) = bx-xy. So, put the smaller number in the tens place, and subtract off the product of it and the “down fingers” from the large number. 3×7? 7 has 3 down fingers, so 30-9 = 21. 4×8? 8 has 2 down fingers, so 40-8 = 32.

18-Aug-2010

Simpson’s paradox

Filed under: math — jlm @ 08:56

I’ve never seen Simpson’s paradox explained by showing the distributions, which I found to be very helpful in understanding what’s going on. So, take a look at these two distributions I made from calls to random():
Simpson's distribution
The cyan distribution has a larger mean than the magenta one, but anyone worth their salt should recognize them as mixtures of unimodal distributions (indeed, that’s how I made them) and look for a binary factor to separate the subpopulations. Upon separating them, in both cases the magentas’ means are higher than the cyans’, Simpson’s paradox.

15-Aug-2010

P vs. NP

Filed under: humor, math — jlm @ 14:37

So, Vinay Deolalikar has a purported proof that P ≠ NP here. But there must be some error, because I just came up with this simple proof that P = NP !
(If you think “joke proof” sounds like an oxymoron, you can stop reading here.)

Let W(m) ➙ s be a member of NP.
Let X(m; n) ➙ s be the first n symbols of W(m). X is obviously in NP.
So, X has a verifier V(m; n; s) in P.
We can find the first symbol t1 of an output of W(m) by trying V(m; 1; c1), V(m; 1; c2), … for all the symbols ci in the alphabet.
We can find the second symbol t2 by trying V(m; 2; t1c1), V(m; 2; t1c2), etc.
And so on for all the symbols t3, t4, … in the output of W(m).
Finding each symbol takes c calls to V, where c is the alphabet size, a constant. Each call of V takes polynomial time, so we can calculate each individual symbol in polynomial time.
The length of the output of W(m) is necessarily polynomial in ∥m∥, so we have a polynomial number of symbols, each calculable in polynomial time, so we can calculate the entirety of W(m) in polynomial time, so W ∈ P.
P=NP. QED

30-Jul-2010

UK recognition of the Haudenosaunee state

Filed under: politics — jlm @ 14:26

Did you read about the recent dispute about Britain refusing to admit athletes from the Nationals into the UK to play in the world lacrosse championship? (NY Times)

The Nationals represent Haudenosaunee, the Iroquois Confederation, and travel on Haudenosaunee passports, which Britain refused to recognize, saying it didn’t recognize them as a country, that land being divided between the US and Canada, while the nationalistic Nationals refuse to travel under those passports, especially with the historical mistreatment of Native Americans by those governments.

Well, this seems like a normal enough snafu, you can’t expect other countries to go along with the US and Canada’s fiction that these tribes are separate nations. We have treaties with them, after all, and other countries don’t. But then it occured to me, Canada has treaties with the Iroquois, but Canada hasn’t been independent from the UK for all that long, surely the treaties must predate Canadian independence and so it was Britain treating with Haudenosaunee as if it was indeed a state — and lo, the Treaty of Fort Stanwix was between Britain and Haudenosaunee, a few years before even the American Revolution, and I doubt it’s the only treaty between them.

Interesting wrinkle, or just a bit of trivia?

29-Jun-2010

Misuse of conditional probability

Filed under: math — jlm @ 13:27

When explaining conditional probability, the “two child” puzzle is often brought in, which is too bad because it’s a terrible example. Case in point, this recent blog post by Keith Devlin.

I tell you I have two children and that (at least) one of them is a boy, and ask you what you think is the probability that I have two boys.

(In a model where children’s sexes are independent and equiprobable,) he applies conditional probability to calculate the probability of them being the same sex at 1/3, in contrast to the “wrong” “intuitive” answer of 1/2. Let’s run with this 1/3 answer for a bit. The same analysis will show that if he tells us that one is a girl, the probability that the other is a girl is 1/3. He’s going to tell us either that he has a boy kid or he has a girl kid, and in both cases the probability of both children being the same sex is 1/3, so the unconditional probability of his children being same sex is 1/3, which is crazy. Where’d we go wrong?

The problem in the analysis is that him telling us he has a boy is not the same as conditioning the probability space on him having a boy. If you like calculating conditional probabilities, the proper condition to apply when he tells us he has a boy isn’t “he has a boy” but “he tells us he has a boy”. For the puzzle, we can assume he’ll be honest, so if he has two boys he’ll say he has a boy, and for two girls he’ll say he has a girl. The interesting case is if his children are mixed. Maybe he’ll say “boy” and “girl” half the time each in that case — but then, the probability of two boys turns out to be the intuitive 1/2 after all. Maybe he’ll always say “boy” then — this gives 1/3 for the quoted puzzle, as it “should”, but having the boy always trump the girl is unappealing and it’d give a 100% chance for two girls if he says he has a girl.

More importantly though, conditional probability is just trotted out there, with no consideration if it’s appropriate to the model. Is it appropriate? In the puzzle (“I tell you I have two children and that (at least) one of them is a boy, and ask you what you think is the probability that I have two boys.”) a reasonable model is he picks a kid of his at random and tells us its gender. He’d say he has a boy 50% of the time, and half of that time his other kid will also be a boy, as the kids’ genders are independent. Conditional probability doesn’t enter into this model. What would be the model where conditional probability was appropriate? It’s hard to come up with one which matches the wording of the puzzle, which is why I think using this puzzle for showing how conditional probability works is a mistake.

Keith Devlin’s article goes on to analyze the new “Tuesday birthday” puzzle:

I tell you I have two children, and (at least) one of them is a boy born on a Tuesday. What probability should you assign to the event that I have two boys?

once again blindly trotting out conditional probability. But let us first ask ourselves if it’s appropriate, what the proper model is. The least surprising model IMHO is that he picks one of his kids at random and tells us that child’s day-of-week and gender. In this model, independence between the children again applies and the probability of two boys is 1/2. What model could have conditional probability apply? Conditional probability applies when the other possibilities in the probability space are removed from consideration, so that’d be something like… a majordomo at a large gathering of parents of two children flips a coin to choose a gender (boy) and spins a spinner to select a day of week (Tuesday), sends away all the parents who don’t have a Tuesday-born son, and selects one of the remaining to tell you that they have a Tuesday-born son. The conditional probability of a second son is indeed 13/27, but models where conditional probability applies to the puzzle are farfetched, so applying conditional probability is an error. In this puzzle intuition is correct after all, the proper answer is 1/2.

[Update: Keith Devlin has pre-emptively addressed some of my criticism in his next post, The Problem with Word Problems, by saying that “I tell you X” is word-problem code for “the probability space is conditioned on X”. I still don’t like equating conditioning on “X” with conditioning on “he said X”: As above, if you have “One of my two kids is a boy, therefore the probability of my children being the same sex is 1/3.” then you can’t have “One of my two kids is a girl, therefore the probability of my children being the same sex is 1/3.”. I find the embrace of this asymmetry absurd.]

13-Jun-2010

On Alvin Greene

Filed under: politics — jlm @ 09:09

One of the news stories from Tuesday’s many primary elections which has stayed in the news is about unemployed veteran Alvin Greene trouncing unpopular member of the party machine Vic Rawl in the race for South Carolina’s Democratic nominee for Senate, 59-41.

Greene self-funded, meaning he used his own savings to pay the filing fee: his campaign consisted of calling up his friends and asking them to spread the word to their friends. Now Rawl is asking how Greene, a political nonentity, who didn’t campaign, could have defeated him. (Fox News, New York Times, The Root) Part of the blame for Rawl’s defeat surely goes down to how his own campaign was itself minimal: Charleston City Paper. But from reading these stories, I think there’s something simple which is getting lost: Rawl was unpopular. (From Public Policy Polling[pdf]: “Do you have a favorable or unfavorable opinion of Vic Rawl?” — favorable 5%; unfavorable 14%; not sure 82%)

To defeat someone unpopular, an unknown needs only to run. And with his unfavorable numbers at triple his favorable, Rawl should consider himself lucky to have picked up 41% of the vote! I’ve seen this happen several times with minor local offices, and sometimes even judgeships. The only news here was that it was an up-ticket race: US Senator.

Greene’s opponent come November is incumbent Sen. Jim DeMint, who doesn’t have the millstone of unpopularity around his neck that Rawl did. Greene was able to win round one just for showing up, but in round two he’s up against a goliath.

23-May-2010

RIP Martin Gardner

Filed under: obit — jlm @ 16:18

Passed away yesterday, at 95.

I remember Gardner’s “Mathematical RecreationsGames” well, it was great at showing sides of math not seen in school. I have many of the books collecting those articles, plus others of his like Ah! Gotcha. They had a big impression on me during my formative years — Gardner’s love of mathematics was infectious.

Scientific American has republished a profile of him.

(Edit: Wired had it right, the Scientific American column is indeed “Mathematical Games”. Mathematical Recreations is a book honoring Gardner and the “Mathematical Games” column.)

21-Apr-2010

Death Valley gallery

Filed under: travel — jlm @ 17:02

I put a photo gallery from my Death Valley trip up. (Wishing for a left-handed camera…)

20-Apr-2010

Day in the life post

Filed under: biking, so. cal — jlm @ 13:50

Not my usual day, so perhaps postworthy.

Last night I tried to head out to Hollywood, but my car wouldn’t start. Didn’t even do the “rrr-rrr” thing, and I verified I hadn’t left the lights on. So much for hitting the nightlife, spent the evening online instead. This morning was my annual physical, including a cholesterol test, so I was fasting that evening/this morning. I didn’t sleep well, woke up at 5 o’clock, had trouble getting back to bed and my alarm woke me. (Usually I have no problem sleeping and I wake on my own before the alarm.) The physical went fine, weight stable, no alarm bells, the doctor gave me cream for my athlete’s foot and probiotics for my GI. Get home, call Gabriel Towing, they refer me to Hillcrest Towing, who say they’ll be there in 15 minutes, and 15 minutes later they’re there. Amazing, I’m impressed, I’ve never had a tow come promptly before. Go to Subway for a lunch to break my fast (any “healthiness” of their sandwiches likely lost by me opting for the drink & cookies, ’cause I’m hungry). Bike around southern Pasadena, a light rain starts, I get twisted around by the twisty streets around Oak Grove and Oak Knoll. It’s a lot harder to navigate under low cloud cover, can’t see shadows or the mountains. Go home, wet, and the dealer says the non-hybrid-system engine battery bricked, looks like I’m out around $200 for repairs and towing.

18-Apr-2010

Economic musings

Filed under: econ, philosophy — jlm @ 20:05

There’s been noise and worry about deflation lately. The fear deflation sparks has always seemed strange to me, with the industry I know best — electronics — being both very energetic and highly deflationary. I’m familiar with the theory of how a deflationary spiral saps economic growth, with Japan’s economy being the prime example.

But looking closer at Japan’s economy: It was “stagnant”, by which economists mean its production was steady, and that steady production was actually quite high. If it weren’t economics, meeting an objective well and steadily would be considered very good, but the norm for economics is growth, so steady first-world level production is considered a failure. (Coming out of a deep recession, a steady production level doesn’t sound that bad after all.)

How much production do we want? Is this even the right question? I’m remembering Dijkstra’s complaint that programmers were proud of how large a program they had written, when instead they should have been ashamed at needing so much code to accomplish their goal. Is GDP as faulty a metric as LOC? Instead of being proud that we produce $47,000 while Japan only manages $33,000, should we instead be looking at why it takes us $47,000 to have a full and fulfilling life while Japan only needs $33,000? Are we really full and fulfilled with our lives, and getting a better life out of that $47,000 than Japan is out of its $33,000? Is increasing that number to $50,000 the best way to improve our lives? Or is there a better measurement that we should be looking at? Certainly more GDP helps immensely, it gives us more resources to spend on our goals, but I worry that treating GDP itself as the goal, we foolishly sacrifice “life value” for GDP, instead of spending our GDP to improve our lives.

Powered by WordPress