a little brainteaser

Posted on January 21, 2009 by Anand Sarwate

Here’s a little problem that Halyun brought up in group meeting today — a little googling showed that it’s a Putnam prep problem, but I won’t hold that against it. The problem is “Determinant Tic-Tac-Toe.” This is like regular Tic-Tac-Toe except that Player One puts a “1” in the square and Player Two puts a “0.” The grid forms a 3×3 matrix (call it $A$ ), and Player Two wants to make $\det(A) = 0$ , whereas Player One wants to make $\det(A) \ne 0$ . Player One gets to move first. Is there a winning strategy for either player? What if both players can place arbitrary real numbers? What about a general $n \times n$ grid?

A much belated report on my trip to Baja California in early November

Posted on December 7, 2008 by Anand Sarwate

We drove from San Diego to Calexico, passing through some of southeast California’s deserts. In Calexico we had a classy meal at a Foster’s Freeze and purchased Mexican car insurance (a necessity for Americans driving over there, although we were never asked to prove that we had it). Another quirk of the law is that you have to bring the title for the car with you, which seems a bit risky. Going through the border to Mexicali was no problem, although getting out of Mexicali and on to the highway was too difficult for me, so Jen took over at that point and we coasted down the highway (which was in pretty good condition, despite what tour books suggested) to San Felipe. The drive was mostly uneventful, except for the obligatory stop and car-check by incredibly bored Mexican military dudes who are being paid by the US to look for drugs. Or at least that’s what I assumed they were doing.

Continue reading →

surprising review of Australia

Posted on December 6, 2008 by Anand Sarwate

I was surprised to read in David Denby’s review of Australia in The New Yorker a rather stinging comment on the Baz Luhrmann’s colonialist (and racist) portrayal of the Aboriginal people:

In the midst of the spectacle, however, Luhrmann and his screenwriters, Stuart Beattie, Ronald Harwood, and Richard Flanagan, have attempted to denounce racism (Nullah is despised by the whites) and then to trace the beginnings of white respect for Aboriginal culture. Nullah’s grandfather, a shaman known as King George (David Gulpilil), is a major figure in the movie—well, in a way. Whenever the story gets stuck, he suddenly appears, in a loincloth, perched atop a peak, or perhaps a water tower—in any case, he’s up high. He then performs whatever magic is necessary to move the film along. At the end, King George summons Nullah to a rite of passage, a walkabout. Nullah’s disappearance into the desert, leaving the whites behind, is framed as a triumphant anti-colonial moment, but Luhrmann confuses the issue by accompanying the scene with, of all things, the stirring “Nimrod” passage from “Enigma Variations,” by Edward Elgar, the composer perhaps most closely associated with the glories of empire. With the same degree of appropriateness, Luhrmann might celebrate Barack Obama’s Inauguration with a thundering rendition of “Dixie.”

I can’t say I’m surprised at the ham-handedness of Luhrmann’s film — I hated Moulin Rouge and I’m sure Australia would be even worse, given how problematic the subject matter is. The film’s attempt at social critique fails because the writers never question their own intent. That’s the problem with lazy “anti-racism” — it acknowledges racism is bad but never digs in deeper to see how pervasive the problem really is.

another amusing footnote

Posted on December 5, 2008 by Anand Sarwate

I seem to have a penchant for picking books with amusing footnotes. Or maybe most math books have them and I’ve been remarkably unlucky. Here’s one from Random Fields and Geometry, by R.J. Adler and J.E. Taylor:

The use of $T$ comes from the prehistory of Gaussian processes, and probably stands for “time.” While the whole point of this book is to get away from the totally ordered structure of $\mathbb{R}$ , the notation is too deeply entombed into the collective psyche of probabilists to change it now. Later on, however, when we move to manifolds as parameter spaces, we shall emphasize this by replacing $T$ by $M$ . Nevertheless, points in $M$ will still be denoted by $t$ . We hereby make the appropriate apologies to geometers.

It’s a good book so far, and may help me solve some pesky technical point in a new problem I’ve been working on. Hooray for new problems!

Manuscript Central is not so central(ized)

Posted on December 5, 2008 by Anand Sarwate

I’m sure others who (perhaps secretly) read this blog have run into the Manuscript Central site. Several of the IEEE Transactions do their paper submissions via this site, which is a bit barebones for the money they are probably shelling out. However, there is no sharing of user data across different Transactions, so one has to make up a whole new profile and a whole new account for each different journal. That takes the Central right out of Manuscript Central.

I assume what brings this about is that the IEEE does not negotiate the contracts with MC, and instead each society is left to their own devices. Might it be possible to pool resources and develop a peer-review system that could be freely used by IEEE societies and integrated better into the IEEE site? It would probably save money in the medium-to-long run, especially if a lot of different societies signed on.

Amardeep Singh responds to “On Yankee Hindutva”

Posted on November 18, 2008 by Anand Sarwate

I just wanted to link to Amardeep’s timely post on Vijay Prashad’s analysis of Hindu organizations for desi youth in the US. Two interesting points to me were:

Religious practice in the US tends to become more like “going to church” (Amardeep cites Sikhs going to Gurudwara as an example).
Shadowy secret global Hindutva conspiracies are strawmen of a sort. The things I’d like to see are concerted challenges and alternative organizations to the VHP-A.

It’s timely because I’m rereading Prashad’s Karma of Brown Folk right now as part of my self-imposed South Asian-American Cultural Studies Bootcamp, sponsored by the UCSD Libaries. More posts on that to come in the future I hope.

be careful how you name your algorithm

Posted on November 13, 2008 by Anand Sarwate

The Lasso is a popular algorithm for selection used in statistics. In this recent paper posted to ArXiV the authors show that the Lasso is not algorithmically stable. It’s only to be expected, really. A twirling loop of rope is hardly an image one might associate to stability!

Last minute confusion on Proposition 8

Posted on October 30, 2008 by Anand Sarwate

Why on earth should it require only a simple majority to amend the state constitution? Is there some misguided notion that the voters will consider carefully the fact that amending the constitution is a big deal and should not be taken lightly, hence making it harder to amend?

Following the Perturbed Leader

Posted on October 28, 2008 by Anand Sarwate

I’m reading Cesa-Bianchi and Lugosi’s Prediction, Learning, and Games in more detail now, and in Chapter 4 they discuss randomized prediction and forecasting strategies. The basic idea is that nature has a sequence of states or outcomes $(y_1, y_2, \ldots, y_n)$ . You have a set of possible actions $\{1, 2, \ldots, N\}$ to choose from at each time. If you choose action $i$ at time $t$ then you incur a loss $\ell(i, y_t)$ . After you choose your action the state of nature is revealed to you. The goal is to come up with a strategy for choosing actions at each time $t$ , given the past states $(y_1, \ldots, y_{t-1})$ .

One simple strategy that you might consider is to choose at time $t$ to take the action $i$ which would have resulted in the minimum loss so far:

$I_t = \min_{i} \sum_{k=1}^{t-1} \ell(i, y_k)$ .

This seems like a good idea at first glance but can easily be “fooled” by a bad state sequence $(y_1, \ldots, y_n)$ . This strategy is called fictitious play because you are pretending to play each action over the past and choosing the one which would have given you the best performance to date. Unfortunately, the strategy is not Hannan consistent, which loosely means that the gap between the average loss under this strategy and the average loss under the best fixed action does not go to 0.

So what to do? One option, proposed by Hannan, is to add noise to all of the empirical losses $\sum_{k=1}^{t-1} \ell(i, y_k)$ and then choose the minimum of the noisy ones:

$I_t = \min_{i} \sum_{k=1}^{t-1} \ell(i, y_k) + Z_{i,t}$ .

This strategy is Hannan consistent and is called follow the perturbed leader since the action you choose is the best action after a perturbation.

If you got this far, I bet you were thinking I’d make some comment on the election. We’ve been following a perturbed leader for a while now. So here is an exercise : how is this prediction model a bad model for politics?

prove as you go or scaffold first?

Posted on October 16, 2008 by Anand Sarwate

I had an interesting conversation two weeks ago about the working process for doing theory work in CS and EE. We discussed two extremes of working styles. In one, you meticulously prove small statements, type them up as you go along, getting the epsilons and deltas right and not working on the next step until the current step is totally set. I call this “prove as you go.” The other is that you sketch out some proofs to convince yourself that they are probably true (in some form) and then try to chase down the implications until you have the big result. When some deadline rolls around, you then build up the proofs for real. This could be thought of as “scaffolding first.” Fundamentally, these are internal modes of working, but because of the pressure to publish in CS and EE they end up influencing how people view theory work.