You are currently browsing the monthly archive for February 2010.

Some interesting tips on binary random matrices again. Kolchin’s book also discusses some aspects of this (see Page 126 for example). It is interesting to see the asymptotic behaviour.

The probability that a random matrix ${k \times (k+m)}$ binary matrix with each element chosen uniformly (${0}$ and ${1}$ picked equally likely), is of full rank ${ k}$ for ${m \ge 0}$ is

$\displaystyle\rho =\prod_{i=m+1}^{\infty}{\left(1-\frac{1}{2^{i}}\right)}, \quad m=0,1,2,\ldots\ \ \ \ \ (1)$

The probability that a random matrix $k \times (k+m)$ binary matrix with each element chosen uniformly (${0}$ and $1$ picked equally likely), is of full rank $k+m$  for $m < 0$ is

$\displaystyle\rho =\prod_{i=1}^{k+m}{\left(1-\frac{1}{2^{k-i+1}}\right)}, \quad m=-1,-2,\ldots\ \ \ \ \ (2)$

Glanced upon a paper from the 2009 ISIT, titled “LT Codes Decoding: Design and Analysis” by Feng Lu et al. The authors discusses LT decoding strategy which is Peeling decoder (conventional simple LT decoding) followed by an extension based on the well known Widemann algorithm solving a sparse homogeneous linear system. Here is a brief summary as I understood.

On packet erasure channels (internet being one close realization of a model of this kind, where, the TCP/IP suit, one can either gets packets correctly delivered or lost in the wild), Luby Transform (LT) codes forms an easy way to transfer information.  It is well known that, asymptotically (When the number of information symbols  (or packets)  $k$ and the number of packets received $r$ are large) near full recovery is made possible by simple peeling decoder which grows in complextity at $\mathcal{O}(k)$. The claim is that, for $n >10000$  or so, with $r= k(1+\delta)$ , on average  we can, with high probability, recover all of  $k$ information packets  by simple unwrapping of xor-ed packets. A more precise statement will read as: If from $k$ information packets, each coded packet constructed independently by xor operation (the number of packets taken for xor operation follows a distribution; Plain vanila version of LT codes uses Soliton distribution), then the content of the original information source can be recovered from any $k+\mathcal{O} \left(\sqrt{k} \ln^{2} \left(\frac{k}{\epsilon}\right)\right)$ packets with probability $1-\epsilon$ by an average of $\mathcal{O} \left(k \ln \frac{k}{\epsilon}\right)$ symbol operations. However, when the number of input symbols is not large (say less, $n < 1000$ ) the overhead term $\delta$ is not small. It is not too surprising, since we need sufficiently large $n$ and $r$ to converge the performance in expectation.  One can think of solving the system of linear equations using Gaussian elimination and get the best figures, but the question mark stays on the complexity $\mathcal{O}(k^{3})$ of this method over the cheaper peeling decoder complexity $\mathcal{O}(k)$.

Conventional LT decoding based on Peeling decoding rule terminate, once the number of degree -1 packets (ripple as it is called in graph theory parlance) are void. One can hope to continue from there, by using Gaussian elimination and decode a a few more (if the graph matrix rank permits it). If the original graph is full rank, one can technically decode all of them.  Gauissian eliminatio being heavy, one hope to find an easy, preferably recursive method. Indeed there comes Wiedemann and that is what the authors use.  The authors propose what they call as full rank  decoding, which essentially is LT decoding, until there are no more degree one packets. From there, they borrow a packet and then uses Wiedemann algorithm which is somewhat light on computational complexity.

The larger aspect on whether this scheme do any better than conventional LT peeling decoder is the other question they answer. To achieve full recovery we need to have a full rank matrix. Now, the matrix being a sparse matrix defined over $\mathbb{F}_{2}^{k \times r}$ where $r$ is the number of received packets. The probability of the matrix having a full rank will directly help us to infer the decoding merits. This is an interesting piece since I had looked into the computation of the rank of a binary matrix and also the probability of a random matrix rank being equal to an arbitrary value. All this was done during the Modern Coding Theory doctoral course by Ruediger Urbanke at EPFL.  For binary random matrix, we can also setup a recursive formula and thereby a good inference on the probability of decoding can be arrived at.

Even though, the season-3 of the hilarious TV episode is being broadcasted for sometime. I  didn’t have had a chance to view  any of them on TV yet, but the other day, I checked youtube for some snippets. May be because of the two seasons of serials, I didn’t see anything impressive in the new ones. Not bad by any means, but it all started sounding a bit too repetitive now.  I have been an ardent fan of the first two season episodes. Nothing made me laugh broader than watching some of those hilarious picks of Dr. Sheldon and gang.

“One man, two hundred!” was the caption, BBC world news displayed, while broadcasting the (breaking out) news of the world record hit by India’s super star player Sachin Tendulkar.  It was against a formidable South African bowling attack in a one day international cricket match at Gwalior, the little master decided to showcase his fabulous reportoire of pure shot making on a cricket pitch. He has done it so many times in the past, but yesterday was a day when history book needed a fresh page. The first man to score 200 runs in a single innings of a 50 over match is stamped with the name Sachin Ramesh Tendulkar. What a feat from a great crciketer and amazing human being!

Times has published a truly nice article commemorating this new record. Cricket is not wideley popular in all parts of the globe. The United States is not among the cricket frenzy nation either. England and her former colonies are the main countries where the game took the center stage over many years. As for records, cricket is the second most popular game in the planet, after soccer. The article hence put the new feat in perspective for the non-cricketing community. Come to think of this record, we must realize that 200 runs need to be scrored from a maximum of 300 deliveries (excepting illegal deliveries such as no balls). On the average one batsman can hope to get about 150 deliveries. In baseball analogy, this is equivalent to getting 150 pitches. It seldom happens that one get more than this. That means, one will have to consistently hit the balls at a rate exceeding 100% strike rate. Tendulkar achieved the score in 147 balls, at a strike rate of 136.5%. It calls for multiple virtues including patience, stamina, focus and talent. All have to be combined and score runs at a faster rate.  It is not easy, by any means. It was something fabulous if not more. There have been scores close to 200 in the past by great cricketers including that from Tendulkar’s previous outings, but this one will go down as the best, literally because this came against a top quality bowling attack and a formidable fielding unit of the protease.

Here is the list of the top ODI scores.

 SR Tendulkar 200* 147 25 3 136.05 India v South Africa Gwalior 24 Feb 2010 ODI # 2962 CK Coventry 194* 156 16 7 124.35 Zimbabwe v Bangladesh Bulawayo 16 Aug 2009 ODI # 2873 Saeed Anwar 194 146 22 5 132.87 Pakistan v India Chennai 21 May 1997 ODI # 1209 IVA Richards 189* 170 21 5 111.17 West Indies v England Manchester 31 May 1984 ODI # 264 ST Jayasuriya 189 161 21 4 117.39 Sri Lanka v India Sharjah 29 Oct 2000 ODI # 1652 G Kirsten 188* 159 13 4 118.23 South Africa v U.A.E. Rawalpindi 16 Feb 1996 ODI # 1049 SR Tendulkar 186* 150 20 3 124 India v New Zealand Hyderabad (Deccan) 8 Nov 1999 ODI # 1523 MS Dhoni 183* 145 15 10 126.2 India v Sri Lanka Jaipur 31 Oct 2005 ODI # 2290 SC Ganguly 183 158 17 7 115.82 India v Sri Lanka Taunton 26 May 1999 ODI # 1463 ML Hayden 181* 166 11 10 109.03 Australia v New Zealand Hamilton 20 Feb 2007 ODI # 2527 IVA Richards 181 125 16 7 144.8 West Indies v Sri Lanka Karachi 13 Oct 1987 ODI # 457

Among them, Richards 189 against the then England may be the one comes closest in terms of quality of opposition bowling. Syed Anwar’s 194 against India is also a glorious innings played by the elegant left hander against India at Chennai. But neither Engalnd nor India will claim to have a strong fielding mastery when compared to the South African unit. So Tendulkar’s new innings clearly own special merit.

It is difficult to comprehend the stardom associated with a five foot tall man. To know this all, one need to be in India. Tendulkar earns the respect of close to a billion souls in India alone. Expectations are at levels beyond one can associate to any moving object. No parallels, really. Every time he goes to bat,  millions glue to the television sets (and now internet).  Social hierarchy still exist at large in Indian lsociety. Religion and politics still separates people. People fight for reasons less than logical, but in the name of religion and castes. It sometimes goes beyond what civilized society can comprehend. The difference between rich and poor is startling. But nothing of that

Numerically there is only a digital swap between 2001 and 2010. Similarities are more instead. Plenty of things were in common between the test match between India-Australia in 2001 and the one between India-South Africa which concluded yesterday. First, they both were great matches. Sheer classics in cricketing parlance, especially test cricket! Nothing can quite scale up to that  2001 epic event, which ended the great Australian juggernaut of consecutive test victories  (and that too at a phenomenal level of domination) but 2010 indeed lived up to the Eden garden’s charm and reputation. With high level of tension and hanging fortunes, Eden gardens was much  like a  grand theater set up for the climax . The balance was between a win for India and survival for South Africa. In the end, quite fittingly India managed to win and gave the home fans something remarkable to cheer about for years.

The final stage had two actors at their imperial best. Harbhajan singh and Hashim Amla. Amla was the epitome of concentration, all personified in human form. Things surrounding him was chaotic and noisy. None of the furies around him however bothered one cool mind of his. Googly, leg breaks, off spin all were dealt with the impeccable calmness. Yet, Harbhajan was the hero emerged in the grand finale. His reaction when Morkel was adjusted LBW has literally pumped the Eden gardens.  That heralded the match, curtains were down on the cricket field, but the celebrations had only began.  Test  match cricket came alive yet again. What treat!

If Harbhajan was the pivotal figure in the finishing stages, one cannot forget Zaheer Khan‘s contribution in the first innings. That one session post tea in day one triggered a possible result in India’s favour.   The stage was well set for the Indian batsmen to drive home the advantage. Boy, did the famous Indian batsmen cash in? The master and student combo were at their best show on day two. The way Tendulkar handled the day and his attacking student Sewhag was amazing. Their innings paved the way for the man who own part of the Eden pitch to come and do a stroll. VVS Lakshman in the company of Dhoni did the routine. When India declared their innings on day three, it was ample clear that India is well within a big win.

The nature had her own ideas to add to the drama. Bad light and rain shared the stage time on day four. But action on the curtailed day favoured India with three top order wickets, including that of the important number of Jacques Kallis. Day five was yet again bright and sunny. Amla stood the ground like a rock, even when things around him followed a different formula. Indian bowlers tried their best, but nothing seriously worked against Amla. The leg before shout by Harbhajan when Amla was in the 70s had serious merit, but that was the lone chance the cool mind offered to the 11 folks. Otherwise he was knocking everything came in his way to still.

In the final stages Tendulkar came to bowl a couple of overs or so. Considering that, it was he who took three pivotal wickets in the 2001 stage, it was a great ploy by the captain. The dangerous opener Hayden, the ever so dangerous Gilchrist and the flashy Shane Warne all were tapped by the magic of Tendulkar in the 2001 classic. But things changed a lot since. Lot of water has flown away under the bridge over nine years. Tendulkar hardly bowl these days,even at nets. Yet, the very second ball almost curtailed the match. One pitched a few inches outside the offstump took a near 90 degree turn and missed the Morkel stumps by a whisker. It was a fabulous delivery.  Not as great as the famous one to Moin Khan, but it still had some magic.  He had done this many a times in the past. So, I hastened to believe that, he was going to have a different script for the final moment. But how can Harbhajan leave his favourite ground without a five wicket haul? It was only fair to have him take that final wicket and seal the match.  As they say, so be it.

For South Africa, there will be disappointment,but no one needs to remind them where they lost the plot. The first day evening proved too costly for them. They were outstanding at Nagpur, but Calcutta favoured India. In all, it was a fabulous test series. It was hastily arranged.If only the cricketing authorities gave it a thought to have a longer test series (by ignoring the flashy one day series)! Not to be! Anyway why complain, when we had two great matches. Long live test cricket!

It is somewhat ironic that, the day to celebrate love is not named after Cupid, the Roman god of love. His mother goddess Venus and father Mercury are not considered either.  The Greek mythical folks cannot be happy either. Eros, the Greek god of love or his mother Aphrodite, the goddess of love are not the ones remembered by the lovers of this century. In the Hindu mythology, encomium is poured over to Kama (or Kamadeva), but who listens when it comes to naming the modern love day? All the accolades instead went to a saint who to his innocence did not really had any fun himself when it came to love, but he was generous enough to facilitate the young lovers.

One of the legend of St. Valentine’s day go like this. Valentine was a priest who served Rome during the third century. Emperor Claudius II decided to bring in a law to outlaw marriages. His claim was that, single men, without wives and families make better soldiers. The priest Valentine, apparently was not quite ready to bulge to this idea of Claudius. In those days, of course you don’t challenge a ruler in public. How powerful democracy is. We are lucky, don’t we?

Anyway, defying Claudius, Valentine continued to secretly perform marriages for young lovers. When Valentine’s actions were discovered, the king ordered that he be executed. The martyr Valentine became one of the most popular saints in centuries to come in Europe, especially in France and England.

Valentine day of the modern world has surely made St. Valentine proud for his worthy sacrifice. After all, it was all for a good cause. Love is beautiful. It is up-to the people to decide, what way they want to celebrate. There is nothing as beautiful than seeing people in love.  The very sign of love is pleasing to the eyes. Let love relish.

Happy Valentine’s day.