I’m at EPFL right now on my way back from a trip to India. My last work-related stop there was the Tata Institute of Fundamental Research, where I am working with Vinod Prabhakaran on some follow-up work to our ISIT paper this year on correlated sampling. TIFR has a lovely campus in Navy Nagar, right next to the ocean in the south of Mumbai. It’s a short walk across the lawn to the ocean:

The beach at TIFR, looking north to the haze-obscured skyline of Mumbai

The grounds themselves are pretty rigorously landscaped and manicured:

The main building seen across the lawn in front of the ocean.

Earlier in my trip I visited IIT-Madras, hosted by Andrew Thangaraj and Radha Krishna Ganti and IIT-Bombay, where I was working with Bikash Dey on extensions to some of our AVCs-with-delay work. It’s been a great trip and it’s nice to visit so many different schools. The challenges facing Indian higher education are very different than those in the US, and it’s a good change of perspective from my usual US-centric view of things. Maybe I’ll write more on that later.

But for now, I wanted to get back to some actual technical stuff, so I thought I’d mention something that came up in the course of my discussions with Vinod today. For a joint distribution $P(X,Y)$, Wyner defined the common information in the the following way:

$\mathsf{CI}(X;Y) = \min_{X--U--Y} I(XY ; U)$

One fun fact about the common information is that it’s larger than the mutual information, so $I(X;Y) \le \mathsf{CI}(X;Y)$. One natural question that popped up as part of a calculation we had to do was whether for doubly-symmetric binary sources we could have a bound like

$\mathsf{CI}(X;Y) \le \alpha I(X;Y)$

for some “nice” $\alpha$. In particular, it would have been nice for us if the inequality held with $\alpha = 2$ but that turns out to not be the case.

Suppose $(X,Y)$ and are a doubly-symmetric binary source, where $Y$ is formed from $X \sim \mathsf{Bern}(1/2)$ by passing it through a binary symmetric channel (BSC) with crossover probability $\alpha$. Clearly the mutual information is $I(X;Y) = 1 - h(\alpha)$. For the common information, we turn to Wyner’s paper, which says $\mathsf{CI}(X;Y) = 1 + h(\alpha) - 2 h( \frac{1}{2}( 1 - \sqrt{1 - 2 \alpha} ) )$, which is a bit of a weird expression. Plotting the two for $\alpha$ between 0 and 1/2 we get:

Mutual and Common Information for a DSBS

If we plot the ratio $\mathsf{CI}(X;Y)/I(X;Y)$ versus $\alpha$, we get the following:

Ratio of Common to Mutual Information for a DSBS

The ratio blows up! So not only is Common Information larger than mutual information, it can be an arbitrarily large factor larger than the mutual information.

It might seem like this is bad news for us, but it just made the problem we’re working on more interesting. If we get any results on that I might be less engimatic and blog about it.

I was in New York on Sunday afternoon and on the suggestion of Steve Severinghaus we took a trip to the brand-new Museum of Mathematics, which is a short walk from the Flatiron building.

The Museum of Mathematics

It’s a great little place to take kids — there are quite a few exhibits which illustrate all sorts of mathematics from recreational math and Martin Gardner-esque pastimes like tessellations to an interactive video-floor which draws minimum distance spanning trees between the people standing on it. It apparently does Voronoi tessellations too but it wasn’t in that mode when I was there. There’s also a video wall which makes your body into a tree fractal, games, and a car-racing game based on the brachistochrone problem. The kids were all over that so I just got to watch.

One of the nice things was that there was a touch-screen explanation of each exhibit from which you could get three different “levels” of explanation depending on how much detail you wanted, and also additional information and references in case you wanted to learn more. That’s good because I think it will let parents learn enough to help explain the exhibit to their kids at a level that the parents feel comfortable. That makes it a museum for everyone and not just a museum for math-y parents who want to indoctrinate their children. On the downside, a lot of the exhibits were broken or under repair or under construction, so we really only got to see about 2/3 of the things.

Apparently it’s also a good place to go on a first date, as evidenced by some surreptitious people-watching. So if you’re in New York and want a romantic or educational time (aren’t they the same thing?), go check it out!

Bon voyage and safe travels to all those headed to St. Petersburg for ISIT 2011. Perhaps Max will blog about it, since I am not going to attend. Or if any of you see Alex, maybe you can convince him to contribute a post or two here…

I am visiting India, so I will probably not post too much for the month. Assuming I don’t get eaten alive by the mosquitoes (a distinct possibility), I’ll post more in December.

Maybe I’ll post a wedding photo or two (not my wedding).

Due to extensive traveling around. At the end of August and beginning of September I attended a workshop at the American Institute of Mathematics on Permanents and modeling probability distributions. It was a lot of fun, and a lot different than any workshop I’d been to before. There were only 20 or so participants and every day we’d break out in smaller groups to actually work on some sub-problem or area. By the end of the week I felt like I’d had a crash course in large-alphabet probability estimation and also got a sense of the huge range of problems and techniques (from exchangeable random partition processes to Markov chain Monte Carlo) involved in tackling them.

Last week I gave a talk on gossip algorithms at UC Davis and got a chance to talk with a lot of people there. It was a great trip, except for the 6:30 flight time out of San Diego. Then last weekend there were heirloom tomatoes:

Heirloom Tomato with bread and Cowgirl Creamery Red Tail cheese

And also peach pie:

Peach pie...

Mmmm, pie.

After ISIT I went to visit the Electrical Engineering Department at the University of Washington. I was invited up there by Maya Gupta, who told me about a little company she started called Artifact Puzzles.

On the research end of things, I learned a lot about the the learning problems her group is working on and their applications to color reproduction. I also got a chance to chat with Maryam Fazel about rank minimization problems, Marina Meilă about machine learning and distance models for rankings (e.g. the Fligner-Verducci model), and David Thorsley about self-assembling systems and consensus problems. All in all I learned a lot!

On the social side I got to hang out with friends in Seattle and UW and hiked for an afternoon at Mt. Ranier. Photos are on Picasa!

I’m at ISIT 2009 now at the COEX Center. Korea is pretty good so far (pictures to be posted later). The conference started today with a plenary by Rich Baraniuk, who talked about compressed sensing. I’d seen parts of the talk before, but it’s always nice to hear Rich speak because he’s so passionate about how cool the thing is.

I’ll try to blog about talks that I saw that were interesting as time permits — this time I’ll try to reduce the delay between talks and posts!

Just as I started blogging more, I’m going to take a break for a family vacation. In the meantime, I put up some more photos from Hong Kong and Rio de Janeiro on my Picasa album.

I’ve had two good dinners already here (for those who are meat eaters). I should hit the gym to convert all the protein into muscle! The first was at Via Sete, which has pretty tasty appetizers, salads, and grilled meats and fish. We got some crab cakes (bolinhos) and calamari with manioc flour batter (it’s much soggy than normal fried calamari). I had a salad with grilled meat which was delicious (and also not too heavy, which was nice). The next dinner was at Braseiro de Gávea, a more traditional Brasilian restaurant. It was packed and the food was delicious — you basically order a set of grilled meat and it comes with one zillion side dishes (like farofa with eggs and banana, surprisingly delicious). I didn’t get to take pictures, but I might add them in later. Note : one dish serves about 3.5 people, so 3 dishes was waaaay too much food for the 7 of us. Afterwards we hit up the Academia de Cachaça, which was appropriate since some of us were in academia. They have a crazy array of cachaças to try in a pleasant open-air environment.

I have been castigated for not putting up more pictures of my trip to Hong Kong on Ye Olde Blog, so I’ll give a quick pointer to my Picasa album which has a lot of the pictures. So here is a somewhat backdated post on the trip.

On my first night there we went to Gaia Veggie Shop (大自然素食) in Mongkok for dinner. It’s an all-vegetarian place (with dishes containing egg marked on the menu). One of the dishes I liked best was a simple stir-fried pea shoots with ginger. I had forgotten how tasty pea shoots are, and the simplicity of the dish really brought out their flavor (this is the Cantonese style, I guess). The other option for dinner was Modern Toilet, a toilet-themed restaurant which may be worth a try later, although I was told the food wasn’t as good. I tried to take pictures of my restaurant adventures there (see the link). It’s spoiled me from eating Americanized Chinese food. Sidharth, my host, lives in a “market town,” which means he walks through a fresh produce market to get home every day. I got to try a lot of exciting fruits that are hard to get the US, including mangosteen, dragonfruit, lanzones, sitaphal (which I have only had in India, and is soooooo good), and even a durian shake (my second ever).

Being able to be in a place for more than one week was a real blessing, because I could go to some nieghborhoods more than once, and by the second week I would even leave without taking my guidebook or map with me, and just trust my memory and a hastily scribbled set of directions. Hong Kong is a pretty safe city, so wandering around and getting lost was a good and fun strategy. I’m sure people around me are sick of me talking about all the cool things I saw there, the quirky fun facts, and my love of the transit system there.

The coolest thing about transit in Hong Kong is the Octopus card, an transit card that works on all transit systems, various convenience stores (7-11 is everywhere there!), and even the CUHK cafeterias. You can add money to your card at 7-11, and there’s a deposit to get the card, so you can go to a negative balance (once) if you don’t have quite enough to get home. A close second is the red minibus system. These are 16-seater minibuses that run all night between different locations in Hong Kong. There are two that I used that went to CUHK, one from Mongkok and one from Causeway Bay. You pay something like 20 HKD and then once the bus is full it takes off at breakneck speed, only pulling over when someone calls out to the driver to stop. There’s a speedometer in the bus that starts beeping when the driver goes over 80 km/hr. Since I always took them late at night, the experience was a bit like being in a careening stick of dynamite. Exhilarating!

Oh, and we got some research ideas/projects started too.