Monday, August 13, 2007

Mystery of Indian Bay Leaves

Indian cooking, especially north and eastern region, uses Tej Pata/Tej Patta to a huge extent. It is also part of the magic aromatic mixture known as Garam Masala. So I too use them here in Boston, and till now bought the Bay leaves found in the local grocery stores. And almost anytime I used it, I had a feeling that they are not quite the same as the traditional Tej Pata I am used to.

I used to have a feeling that they may not be the same thing. Until someone told me that he was surprised to know that Bay leaves are used in Indian cooking. That got me thinking and I googled my brain as well as the internet to hunt for the difference, if any. The first prominent difference I always noticed that the bay leaves did not have that strong an aroma as back home. I generally pushed that argument aside, citing quality difference. After all I do grocery at cheap neighbour stores. But now I remembered from my school bio classes - tej pata back home had several (3 ?) parallel veins unlike the single pinnate-style bay leaves I see here. A bit of internet search revealed that they are indeed different. Tej Pata ...are often erroneously labeled as "Indian bay leaves" though the bay leaf is from the Bay Laurel, a tree of Mediterranean origin in a different genus, and the appearance and aroma of the two are quite different... Indeed they are different. Next time I go to a grocery, I will know what to look for.

Friday, August 10, 2007

Kudos to Anil Kumble

A post just for the century by Anil Kumble in the 3rd Test match between
India-England (July-Aug, 2007).

He has been called as the unsung hero by many before, now he is again a hero
but for an altogether different reason. Congratulations, Anil Kumble.

Wednesday, July 25, 2007

Good bye Mr President

Dr Avul Pakir Jainulabdeen Abdul Kalam, India's 11th president (2002-2007) is on his way out. I wish him good luck on his future endevours. I also welcome our 12th president, Mrs Pratibha Patil, earlier governor of Rajesthan.

Abdul Kalam was an exemplary statesman. Constitutionally, the post of Indian president is a ceremonial head but without any effective power. Most of the times, the ruling party had its say on the presidential election. So all they did was to visit countries as head of the nation, give speeches and help the ruling party in passing the bills of their choice. APJ was chosen during NDA's regime of 1998-2004 not because of his political inclination, which he did not have, but because of his iconic image and charisma. Elected, rather nominated, out of protocol, this scientist chose to defy the norms and protocols left and right when it came to presidential grandeur.

What more, he used to utilize his time judiciously. Even the people en masse could feel his activity. Today he was visiting some school in some village, tomorrow he was in some submarine of India navy and maybe the next day, he is addressing some doctors via teleconferencing. It has been reported that his days usually had 10 meetings. Not surprisingly, several visions of this visionary scientist met reality. Indian all over the world and more importantly, even in the remotest villages came to know of him. Know that the post of president is not meant to only enjoy the power but to actually meet the responsibility that accompanies the power. APJ has an excellent skill in writing. His books and articles are quite popular in India especially among the younger generation. Of all the 5 presidents that I actively remember, I don't think I remember any of the rest 4 for anything. I was not even clear how much a president can do ? APJ proves, when there is a will, there is a way.

I hope our current president can live up to the reputation of the president's post. India is aware of the president's office, the youth in this country are well trained to dream and chase the dream. I hope Mrs President will similarly uplift the morale of Indian women. I do not want all Indian women to join politics or airforce or become executives. I just want them to be aware of their position in the society and live with their head held high.

Welcome Mrs President and good luck!

Wednesday, July 4, 2007

Kolkata kebal bhule bhara

Those who teach frequently use examples to explain concepts. Those who write software programs love reproducible test cases which they can debug, analyze and correct. With utmost humbleness, I believe the civic engineers have neither experienced good teaching nor have decent engineering skills. Year after year, with sure shot prediction, Kolkata floods during monsoon. Its pretty easy to guess, any heavy rainfall will cause water logging. It becomes an even better test case because the water does not go down quickly once the rain stops. So here is a situation that is realized 3-4 times a monsoon season and provides ample time to check design and implementation flaws. Given that the situation is not improving, in fact, degrading year after year only has one conclusion: like the Indian cricket team, the engineering team needs fresh blood and talented minds.

Final note: please do your part by not throwing plastic bags around. Whether its the drains, empty land or waterbody, the fundamental problem they cause is to block the flow of water. Store them at home and when enough is deposited, dump it in a garbage dump. Though there is no adequate plastic recycling program, at least this will prevent plastics from blocking water flow around your house.

Wednesday, April 18, 2007

Another Take on the 7-Hats problem

Consider the problem described here.

Let 0 denote Red and 1 denote Blue. Fix an order among the n players. So the different ways to put hats is all possible n-bit strings, each occurring with equal
probability. Any assignment is an n-bit string.

The players could decide the following strategy. They split all n-bit strings into two disjoint sets S and S' (S'=complement of S). They try to split it in a certain way so that they are able to correctly guess (which means at least one guesses correctly and others pass) when the assignment is in S'. Then their probability of success will be |S'|/|S|+|S'|.

Property of S,S': Let the actual assignment be s. They want, if s is in S, someone to be able to guess correctly and no one wrongly. One way to ensure this is if for all s in S', there is some i in 1...n (at least one bit position), such that flipping the i-th bit of s gives a string in S. The players will decide in advance a suitable S and S' satisfying this property.

Then then need to decide a strategy based on S and S'. Here is a simple one. Each person i can see (n-1) bits. He considers the two possible n-bit assignments, s0 using 0 in the i-th bit and s1 with 1 in the i-th bit. These are the cases,

  • s0 is in S and s1 is in S': Guess 1 as his bit. If s is in S', guess is correct.
  • s0 is in S' and s1 is in S: Guess 0 as his bit. If s is in S', guess is correct.
  • Both s0,s1 are in S: So, the actual string s must also be in S. He can just say pass.
  • Both s0,s1 are in S': So, the actual string s is in S'. He can say pass. By the property above, there is some j such that s is obtained from S by flipping bit j. Then person-j will guess correctly.

By the strategy above, they win if the string s is in S'. The tricky part is to find the correct S and S' satisfying the property above. They can be found using various algorithms e.g. using brute force or greedy approach. For example when n=3, one possiblity is S={000,001,010,011} and S'={100,101,110,111} (so the success probability is 1/2).

It turns out the above property is satisfied by error detecting codes detecting 1-bit error. All the non-codewords in a 1-bit error detecting code are obtained by flipping 1-bit of some codeword; so S is the set of codewords. Any such error detecting code with k codewords will give a strategy with error probability k/2^n. The probability can be maximized by finding a error detecting code with the smallest set of codewords. The (7,4)-Hamming code is one such example with 16 codewords; so using its codewords as S gives a strategy with error probability 16/128=1/8.

Note that, the game does not allow the players to collaborate once the game starts, which means they are not allowed to pass hints to others by choosing which order to make their guess or listening to others before making guess. If colloboration is allowed, the error can be made very small 2/2^n.

Monday, April 9, 2007

7-hats problem

7-hat problem: 7 persons are assigned red or blue hats, uniformly at random, with their eyes closed. When they open their eyes, they look around and try to predict the colour of their own hat by saying blue, red or staying silent. They lose if any of them is wrong or if all stay silent. What is the maximum probability of winning ?

Consider the various possibilities,

A) (prob: 1/128) 0 red, 7 blue: All players see 6 blue. To win, they should say blue.
B) (prob: 7/128) 1 red, 6 blue: 1 player sees 6 blue (should say red), other 6 see 5 blue (should say blue).
C) (prob: 21/128) 2 red, 5 blue: 2 players see 5 blue (should say red), other 5 see 4 blue (should say blue).
D) (prob: 35/128) 3 red, 4 blue: 3 players see 4 blue (should say red), other 4 see 3 blue/3 red (should say blue).
and complement cases (interchange red and blue in the four cases).

If the players decide based on the number of blue/red hats, they can decide a strategy to win alternate cases. So the best they can do is to satisfy (B), (D) and their complementary cases i.e. anyone seeing 6 or 4 blue will say red and vice versa, others stay silent. They will win with probability 84/128 = 21/32 = 0.656.

They can take into account ordering information beside just looking at the numbers. This will give them higher chance of winning. Lets look at the 3-hat problem once again.

Consider how the players might decide a strategy. They can decide an order among themselves so that the values, 0 (for red) or 1 (for blue), form a bit-string of length 3. When they open their eyes, they will consider both the possibilities for themselves and decide accordingly. They could decide beforehand a set S, and its complement S' and a strategy such that for every player if bit b (b in {0,1}) puts the string in S, he says b for himself; otherwise stays silent. What are the properties needed for such a set S ?

1) For all s' in S', changing one bit of S' should put it in S. Otherwise, the player will not be able to decide. (The same could also hold for S, but that is not a strict requirement since the players are allowed to stay silent. So, if both 0 and 1 puts the value in S, the player stays silent).

2) For all s in S, there must be some s' in S' such that, s is obtained by flipping some bit of S'. Otherwise, all players will remain silent and they will lose. If such s' exists, then one of the players will be correct.

If they find such an S (and S'), they will win if the value is in S.
Consider any s in S. By (2), there exists some s' such that s=flip(s'). Say the flip occurs in position i. Then, player i will say the correct value. Others will either stay silent (both 0 and 1 put it in S) or say the correct thing (only one of the values put it in S) (it cannot be that neither puts it in S by (1)).
Consider any s in S'. Everybody will be either wrong or stay silent (in which case they also lose).
So, they win with probability size(S)/size(S)+size(S').

(1) => all strings in S' are at least 2 bit-flips apart. So, the trick is to come up with S and S' such that S' has strings separated by at least 2 bit-flips and all strings in S are obtained by flipping one bit of some string in S'. You can greedily construct some sets. Put any string s in S'. Flip one bit of s at a time and put them in S. When done, look at the strings left and pick one not used. Put that in S'. Continue.

E.g. for 3-hat, S' could be {000, 011, 101, 110} (prob of winning 4/8 = 0.5) or S' could be {000, 111} (prob of winning 6/8=0.75).

The above strategy has nothing to do 3. This could as well be used for 7-hat.

For 7-hat, the strategy at the top would work. S' is the string in cases (A) and (C) (and complement sets). Verify easily that all 7-bit strings are either in S' or S, all strings in S are one-bit away from some string in S' and all strings in S' are 2-bit flips apart.

Finding the best S and S' manually is a bit difficult. If you are familiar with coding theory, you can observe that any code that detects one bit error will work (S' would be the set of codewords; since they differ by 2, one bit error can be detected). E.g. the Hamming code for 7-bit codewords, gives S' of size 16 (out of total 128). So, using S' as the set of codewords of (7,4) hamming code, the players can win with probability 7/8. Note that, hamming code not only detects but corrects one-bit of error. Any other 1-bit error detecting code will also work but will give a lower probability of winning.

Wednesday, March 28, 2007

Probability puzzle: Uniform Everytime

Assume I have a bag with several distinct objects. Particularly, I do not tell you how many objects I have. At each step, I take out one item and give it to you. I may do this in any order, with any probability distribution or even adversarially. You can only hold one item in your hand at a time. So, at each step, you get to choose whether to retain the object already in hand or replace it with the new one. When I run out of objects (or I am simply tired and quit), I stop.

Your goal is adopt a strategy so that the object in your hand at the end is uniformly at random among all items. In other words, irrespective of how many objects I give you or however I choose them, this item in your hand should be equally probable to any other item.

Go figure!
(courtsey Nenad)

Saturday, March 24, 2007

Worshipping False Gods

Yet again, the Indian cricket team failed. Being hyped by the media as
the team with the best batting line-up, this is no the first time the
batting order has seen a complete collapse and I fear this would not
be the list time either. Indian cricketers enjoy a god-like (not
God-like, yet) status back home. The facilities, the perks, the
attention and the support they get from the fans, officials and media
is phenomenal and unparalleled. So it sounds right when the fans treat
them harshly after poor defeats. Sometimes their show of
disappointment gets a bit overboard which is definitely not desired.
But again, when the worship the cricketers, nobody complains either!

I don't know about the other subcontinent teams but the gods in the
team are definitely past their days of glory. They are only fit for
consultations now; they should be retired and fresh blood should be
brought into the team. It has happened time and again. It took the
board 2 full years to sack and drop Sourav Ganguly. He returned in the
team after regaining his batting form. Look ma! Sourav is now scoring
runs. When and if he loses his rhythm again, he should be dropped.
Same for Sachin, Sehwag and other non-performers.

I feel the cricketers should also be restricted from doing too much
non-cricket stuff. They spend time after endorsements, other business
(whats this recent craze about opening restaurants ?) and doing public
speeches for political parties. Appearing in one or two advertisements
for public service is good, since quite a few of the cricketers are
seen as role models by the youngsters but not as brand ambassadors.
Similarly, being citizen of India they are entitled to the freedom of
voicing their opinion but not with any regularity.

BCCI should cap non-cricket involvement, spend more resource and
effort after domestic cricket and make the seniors also play domestic
cricket. That keeps them in practice and on the other hand provides
the young guns with better exposure. I personally don't think a
foreign coach is necessarily a bad or a good thing. Give the job to
the best person. The richest cricket board can afford to pick the
best.

In other news, Sachin is only one duck away from equalling Srinath's
Indian record of most (19) ODI ducks.

Saturday, March 3, 2007

Debugging Probablity: Car, Goats and Monty Hall

The Monty Hall puzzle is a famous probabity puzzle. In one of its various forms, there is a room with 3 closets. One of them has a car behind it, the other two has a goat each. When you enter the room, the doors were closed so you do not know which closet has what. The challenger asks you to guess which closet contains the car. If you guess correctly, you get the car. If incorrect bad things will happen, no guarantees here. So you think a lot, probably make phone calls to friends and make a guess, say X. Then you proceed to open the door to see what is in your fate. But the challenger stops you and opens one of the other closets Y that has a goat. Then he even gives you a chance to make a new guess Z. You have two options, stick with previous guess (X=Z), switch to the other unopened closet (X!=Z). What to do ?

The correct behaviour (by probability) is to change the guess to the closet that is still unopened, X!=Z. That will double your chance of winning. There are several ways to reason about this. But I am more interested in debugging other claims, mostly faulty. So, lets look at the different explanations.

We can make one assumption. To stop the challenger from getting the better of you, you should choose X uniformly at random from all three closets. So, P[X=car]=1/3 and P[X=goat]=2/3.

1. Repeat the experiment a million times. You would get the the car only one third of the time by sticking to your first door. People who always switch would therefore win the other two thirds. Therefore you should switch.
The only cases when you win by switching is when X=goat. So, P[winning | switching]=2/3 (probability taken over X).

2. Consider all possible cases:
  • X=goat1, Z=X (loose)
  • X=goat1, Z!=X (win)
  • X=goat2, Z=X (loose)
  • X=goat2, Z!=X (win)
  • X=car, Z=X (win)
  • X=car, Z!=X (loose)
3 cases you win by switching, 3 you dont. So, does not matter if you switch or not.
Actually, the complete table says that, if you randomly decide to switch or not switch, then you have a 50-50 chance of winning. Further, it even says that P[win | switch]=P[win | Z!=X]=2/3.

3. One argument is that revealing Y does not matter. The probability of finding the car in the remaining two doors was equal in the beginning, and they are still equal now. The fact that you put your hand on one of them cannot increase or decrease its probability of having the car under it.
The explanation is a bit ambigous. Lets look at various cases and explanations. These are all different experiments.
[C1] At the beginning itself, the challenger opens one of the goat containing closets. P[car in one of the other two]=1/2 in this case.
[C2] The challenger opens a goat closet. The he randomly reshuffles the contents of the other two closets. Here,
P[X=car]=1/3
P[X=car | switch]=P[X=car | not switch]=1/2
[C3] The challenger opens one door while your eyes are closed, showing a goat to the audience.
P[X=car] = 1/3
P[X=car | revealing] = 1/3
this is the same experiment. Just because he opened a door does not change your sample space.
[C4] The challenger reveals a goat closet to you.
P[X=car]=1/3
But, P[X=car | revealing] != 1/2 because the challenger did not reshuffle the contents. In fact, knowing a closet contains a goat makes the probability of winning by switching 2/3. This is different from C1. The challenger has been forced to reveal some information not known before. If X=goat, Monty had to open the non-car closet. If X=car, he will not reveal any information. 2/3 of the cases X=goat, in which case he would leave the car closet closed. 1/3 of the cases X=car and he could choose any goat-door without saying anything. So, if you switch, you have a winning chance of 2/3. Note that, the analysis depends on your initial uniformity of choosing a closet but independent of challengers choice of Y.

4. The analysis sounds easier if you consider a related problem. Say there are 1000 closets, one car and 999 goats. Do the same experiment but here the challenger reveals 98 of the goat closets.
Initially P[X=car]=1/1000. When the challenger opens all but 2 doors, P[X=car] cannot possibly remain the same. In fact, by the argument in C4 above, 999/1000 times X=goat, so the challenger would be forced to leave the car closet open. Then, P[win | switch]=999/1000.

5. Another way of looking at it is, P[X=car]=1/3 which means that if you consider all possible items in the closet, in 1/3 of the cases it would be a car i.e. P[one of the other two has car]=2/3 Revealing a goat does not change this probability (it does change some conditional probabilities). So, even after revealing, P[one of the other two has car]=2/3. But now you know that one of the other two definitely has a goat. So, P[one of the other two that is unopened has a car]=2/3.

6. Consider a slight variant of the puzzle. There are 4 doors with 1 car and 3 goats. After you choose X, the challenger opens one door with goat. Now, with probability 3/4, you chose a goat closet. In which case, the challenger leaves a car closet and a goat closet open. Let us say you always switch to any of the them with probability 1/2. Then your probability of winning in this case is 3/8. With probability 1/4, you choose a car, in which case you always loose when you switch. So, switching gives you 3/8 probability of winning. On the other hand, if you do not switch, then you only win when you chose the car closet, which happens with probability 1/4=2/8. So, switching is better, but not by that much.

Thursday, February 22, 2007

A Dog ate my brain

Even a few years ago (at or before IIT-K), I would comfortably solve these kind of basic probability questions. Yesterday, I erred when Kanishka asked them and today had a hard time arriving at the solution from first principles.
  1. X has two children. One of them is a girl. What is the probability that the other is also a girl ? If you have think something is fishy, compare it with this one:
    • X has two children. The younger is a girl. What is the probability that the elder one is also a girl ?
  2. X wants to shoot Y. He puts two bullets in (edited adjacent slots in) a six-barrell revolver. Then he rolls the barrell. He pulls the trigger at Y, but luckily, no shot is fired. He gives two options to Y, either X will fire again or X will roll the barrell and fire once more. Which is better for Y ?
Assume equal probabilities wherever it makes sense.

It looks like in the pursuit of freedom and exposing the creative self in myself, I am losing my precious little grey-cells. Eh bien! Hope it's not too late.

Friday, February 9, 2007

two sides of iwo jima

I write this as I am watching Flags of our Fathers, the American version of Letters from Iwo Jima. I watched the Japanese side of the movie with Saikat about three weeks ago. I would consider Iwo Jima one of the best movies I have seen so far. From the brief first impression, I am already at love with FouF. Its definitely heading the same way. Clint Eastwood is a damn good director.

The movie gets high score from me in different aspects. The set director and the person behind the camera did a wonderful job. The colours during the war shootouts, the cold colours of the ships, the guns, the bluish-gray Mount Surabachi from far, they sure sent a shiver down my spine. Watch it in big screen and you would see excellent wallpapers in motion in front of your eyes. If you have seen Saving Private Ryan and played MoHAA, let me tell you this would make

This could very well be a Kubrik movie. War is just one facet of the movie. I have seen quite a few war movies, all kinds from showing the severity of warfare to movies depicting mockery. These two would keep you thinking hours after watching them. And any time you hear about a man made war, you would be able to see it, hear it, feel it, in the correct perspective. Wonderful editing stiches the beatiful pieces and facts together to make a movie out of reality. Just how you would like it to be.

The two talk about different things. But combined they draw the full picture of a war, of an invasion and of fighting for one's motherland. If you have not watched any of them, watch it. "Sorry for your loss". Well said, lady!!!

Thursday, January 18, 2007

Land of $USA$

Call USA the land of opportunities, land of liberty but calling it the land of money is not quite right. In most of the places in this country you get lots of opportunity; personal freedom is visible everywhere and actively sought after. But you cannot just get rich here by coming to USA. I think the last fact is true about any country or place, but definitely true for this country.

Its surprising that I had the opposite perception before coming here. I am pretty sure that is the case by default for the common person on the street back home. Sure, any country has relatively richer and relatively poorer people but really poor people, who think before they spend; neh, not Americans.
Thus imagine my shock when I spotted a homeless beggar on the streets of Boston. Come winter and I read about shelter homes for homeless people.

I never give money to street beggers in India, not because I do not sympathise with them but more because begging has become an easy profession. I rarely meet someone who really needs to beg and it is nearly impossible to distinguish them from the fake beggers. I have ended up giving money to people on the streets here; again, not because I sympathised with them but I was so startled and ashtonished that I could not think what to do.

Gradually it became easier to accept the reality. I even know where some of the homeless people spend their night at. I have seen people at grocery stores, catalogue in their hands, searching for the cheapest thing and choosing products which save even a quarter. The divide between rich and poor is enormous here. I used to think that $4.00 for a sandwich is a pretty good deal but some of my american friends proved me wrong. If I were in India, I would have never considered it a good deal; there I am used to judging value by cost price (including labour). Every day I see numerous ads in TV about furnitures. They advertise how you can buy a $400 sofa without paying any interest for 1 year. I would never have imagined there could be people who need to pay $400 in installments over a year.

I guess one reason behind my misconception could be the graduate student stipend. Average graduate student stipend in Boston area, before tax, comes out to be about $2000. Thats about $12.5 per hour. I did some private tutoring sometimes. My friends sometime do. The students pay $25 to $30 per hour on average. Thats a whole lot higher than $8 an hour, which a lot of undergrads and non-funded students work for on campus. And its nearly double the minimum wage. No doubt tipping has whole new meaning here. Please tip generously .

Like most people here, I carry credit cards. More that one. I seldom use them as _credit_ cards, I use them so that I do not have to carry cash. I was shocked to hear that I am in the minority. People here have huge debt on credit cards. They get a new credit card to avail of the free no-interest transfer for 6 months or so and then interest starts piling on that too. Debt never decreases in middle class family. Number of credit cards keep increasing. I even read about people who cannot apply for credit cards anymore because of their credit history. There can be people like this ? In America! I guess thats reality.

Monday, January 1, 2007

Season's Greetings, Tilottama

My plans of watching the first sunrise of 2007 went haywire due to the rain. So, here I am, writing my first blog of 2007. Rather, creating a laundry list of predicted improvements in Kolkata/West Bengal. I plan to go through this list at the end of 2007 (with the help of Telegraph). I am telling you in advance, I will be excited even if 10% of the plans are materialised.
"Shatakoti santanere, he mugdha janani. Rekhecho bangali kore, manus koroni"
  1. Useful exit ramps from AJC flyover. Those will actually reduce the congestion.
  2. Main road of Rajarhat will be completely rebuilt, with the specification of the Indian Road Congress (read: so that the road can withstand a couple of monsoon seasons).
  3. Infrastructure in Sector V will finally be revamped by the Nabadiganta Industrial Township Authority, starting with seven arteries in tech town being repaired and then beautified.
  4. The "country's first automated underground parking plaza" in front of New Market will finally be commissioned this year. The latest (N'th) date is Poila Baisakh. Keep your fingers crossed on this one.
  5. The city's first off-the-river water treatment plant will be unveiled at Dhapa.
  6. Solar-powered street lights, trash bins on roads, less water logging.
  7. Deposition of property tax and licence fees at any CMC counter.
  8. CAT-II Instrumental Landing System will be operational at the airport. The secondary runway expansion by another 440 m will be completed.
  9. CAS will enter (and along with it, DTH too).
  10. After all the chaos, construction of the Tata Motors plant with start in Singur.
  11. After what seems like a century, tyres will roll out of Dunlop's Sahagunj factory. Talk about revival then.
  12. Infosys will make a big bang entry on the 100 acres to be offered by March 2007 opposite Vedic Village.
  13. Calcutta University will open a number of advanced research centres in areas like social science, modern biology, nano-technology. A slew of study centres will become operative.
  14. Real high speed Broadband for home users and increased Wi-Fi (or even better, Wi-Max like Bangalore) coverage.
Good luck, Kolkata. Wish you all the best. I love you.