Three classic results on the AVC

I wrote a summary of three classical results on arbitrarily varying channels that I think make a nice story. The first is the original 1960 proof by Blackwell, Breiman, and Thomasian. The second is Ahlswede’s elimination technique. The last is the symmetrizability result of Csiszár and Narayan. Together, these three results settle some basic questions regarding arbitrarily varying channels, and I tried to make the exposition self-contained and readable by people who have had a basic course in information theory.

Macaca and George Allen

Senator George Allen (R-VA), in reference to an American-born citizen, S.R. Sidarth :

This fellow here over here with the yellow shirt, Macaca, or whatever his name is. He’s with my opponent… Lets give a welcome to Macaca, here. Welcome to America and the real world of Virginia.

This casual racism gives lie to the claims of “non-racism” made by so many people in the US. In the case of the American who has never met a person of South Asian descent, such bigoted remarks may best be explained by ignorance combined with immersion in a culture that resists difference. But for an elected representative who cannot possibly claim inexperience, it reveals a deliberate and ingrained racism that colors every decision. Maybe he hasn’t really outgrown his high school years, when he sported the confederate flag. Via TPM.

Update : Video.

Chez Panisse

(Shattuck between Cedar and Vine) I’ve lived in Berkeley for 4 years and I finally went to Chez Panisse, the restaurant of Alice Waters that supposedly revolutionized California food. We ended up going upstairs, to the Cafe, which is more relaxed and cheaper (but not cheap by any stretch of the imagination). Liz and I split everything and we had, between us,

  • 1 Bottle 2003 Catherine and Pierre Breton Bourgueil “Galichets”
  • Cannard Farm cucumber, chervil, and radish salad with local albacore tuna
  • Baked Sonoma goat cheese with garden lettuces
  • Local king salmon baked in the wood oven with gypsy peppers, summer chanterelles, and roasted potatoes
  • Hoffman Farm chicken al mattone with tomato-potato gratin, corn, and okra
  • Pistachio cake with kirsch cream and blackberries

The dominant impression that I had from each of the dishes was that fresh ingredients are absolutely delicious. None of the dishes struck me as particularly amazing, but the flavor came from the ingredients. That’s one way of cooking, but the herbing and spicing came off a little dull to me. Nothing on the menu looked vaguely spicy to me.

I don’t think I’ve ever had cooked tuna that didn’t taste really fishy, but this fish was mellow, almost buttery, and the cubumbers were nice and sweet. Try as I might, I couldn’t taste the chervil, but it looked pretty. Whatever dressing they put on the garden lettuces was far too salty for my taste. The cheese came in two little rounds covered in spiced crumbs and warmed so it was gooey. Wrapping some goat cheese in the lettuce yielded little crunchy tangy packets of yumminess.

As I learned last night, “al mattone” means cooking the chicken under a brick. What we ended up with was something almost resembling fried chicken, with a crispy skin and firm but juicy meat inside. The gratin was probably one of my favorite parts of the meal — the vegetables’ sweetness complemented the slighly crunchy potatoes, and the okra was just right. The salmon was actually unremarkable, which is where the freshness really came to the fore. The only disappointing thing about this dish was the gypsy peppers, which I thought had no taste and weren’t at all spicy. Of course, I’d never heard of gypsy peppers before.

The pistachio cake was good, but remarkable only for its moistness. In restrospect I should have gotten the nectarine cobbler, but I think at the time we were both too stuffed. The wine is a keeper. I know I can get it at Kermit Lynch, so I’ll try to find it there. I know nothing about wine, so I can’t say it had spicy oaky notes or anything like that.

Will I go back? Probably, but I didn’t feel like the meal was interesting enough for me to try and go there whenever I save up enough spare cash. It was definitely good, and I’ll try and go there one or two more times before I leave.

paper a day : importance sampling in rare-event simulations

Introduction to importance sampling in rare-event simulations
Mark Denny
European Journal of Physics, 22 (2001) : 403–411

This paper is about importance sampling (IS), which a method to improve the error behavior of Monte Carlo (MC) methods. In engineering systems, getting good simulation results for rare events (such as decoding error) on the order of 10-10 would require an obscene amount of computation if you just did things the naive way. For example, the quality of a numerical bound on the tail probability of a random variable gets worse and worse as you look farther and farther out. Importance sampling is a method of reweighting the distribution to either get a smaller error in the regime of interest and/or uniformize the estimation error. This paper gives some motivation, a simple IS algorithm, analysis, and some simulations. It’s pretty readable, and I went from knowing nothing about importance sampling to getting a decent idea of how to use it in practice, along with its potential problems and benefits.

a quote that gives some comfort

From Van H. Vu’s “Concentration of Non-Lipschitz Functions and Applications,” Random Structures and Algorithms 20 : 262–316, 2002 :

Finding this hypothesis was actually the hardest part of our work, requiring some insight and a numerous number of attempts. As the reader will see after reading Section 5, a proper induction hypothesis not only allows us to derive a powerful result, but also reduces the proof to a rather routine verification of a few conditions.

I have spent a long time reading through difficult proofs with numerous lemmata, wondering why it had to be so complicated. Some things have to be proved by brute force. For others, just phrasing the problem in the right way can make the proof seem trivial. Some might say “well, I could have done that,” but the more accurate response is “I wish I had thought to do it that way.”