## Monday, August 13, 2007

### Mystery of Indian Bay Leaves

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

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

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

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

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, s_{0} using 0 in the i-th bit and s_{1} with 1 in the i-th bit. These are the cases,

- s
_{0}is in S and s_{1}is in S': Guess 1 as his bit. If s is in S', guess is correct. - s
_{0}is in S' and s_{1}is in S: Guess 0 as his bit. If s is in S', guess is correct. - Both s
_{0},s_{1}are in S: So, the actual string s must also be in S. He can just say pass. - Both s
_{0},s_{1}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

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

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

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 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)

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

- 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 ?
- 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 ?

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

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$

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

"Shatakoti santanere, he mugdha janani. Rekhecho bangali kore, manus koroni"

- Useful exit ramps from AJC flyover. Those will actually reduce the congestion.
- 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).
- 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.
- 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.
- The city's first off-the-river water treatment plant will be unveiled at Dhapa.
- Solar-powered street lights, trash bins on roads, less water logging.
- Deposition of property tax and licence fees at any CMC counter.
- CAT-II Instrumental Landing System will be operational at the airport. The secondary runway expansion by another 440 m will be completed.
- CAS will enter (and along with it, DTH too).
- After all the chaos, construction of the Tata Motors plant with start in Singur.
- After what seems like a century, tyres will roll out of Dunlop's Sahagunj factory. Talk about revival then.
- Infosys will make a big bang entry on the 100 acres to be offered by March 2007 opposite Vedic Village.
- 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.
- Real high speed Broadband for home users and increased Wi-Fi (or even better, Wi-Max like Bangalore) coverage.