Herd immunity

If enough members of a group of animals (including humans) are immunized against a disease, the entire group is more likely to escape infection.

The problem with herd immunity, however, is deciding who has to get the shots. Individually healthy people would prefer not to go through the effort of getting the shot and “free ride” on those who do. The situation is akin to the prisoner’s dilemma, which may explain the low vaccination rate in the U.S.

The pigeonhole principle

The pigeonhole principle is one of those which people believe one of the most faltoo principles in Combinatories.

Imagine that 3 pigeons need to be placed into 2 pigeonholes. Can it be done? The answer is yes, but there is one catch. The catch is that no matter how the pigeons are placed, one of the pigeonholes must contain more than one pigeon.

The logic can be generalized for larger numbers. The pigeonhole principle states that if more than n pigeons are placed into n pigeonholes, some pigeonhole must contain more than one pigeon. While the principle is evident, its implications are astounding. The reason is that the principle proves the existence (or impossibility) of a particular phenomenon.

The pigeonhole principle (more generalized)

There is another version of the pigeonhole principle that comes in handy. This version is “the maximum value is at least the average value, for any non-empty finite bag of real numbers” (thanks Professor Dijkstra)

Do not let the math jargon intimidate you. The idea is intuitive. For typical data sets, the average is the “middle” value, so clearly the maximum should be at least as big. While this version sounds different, it is mathematically the same as the one stated with pigeons and pigeonholes. Let’s see how the two are connected.

Consider again the problem of stuffing pigeons into pigeonholes and consider the average. If we have more than n pigeons and n pigeonholes, then the average value of (pigeons / pigeonholes) is greater than one. This means the maximum value should also be larger than one. In other words, there has to be some value of more than one pigeons per pigeonhole. Indeed, the two versions are about the same idea.

Now see the power of idea

1 .If you pick five numbers from the integers 1 to 8, then two of them must add up to nine.

Every number can be paired with another to sum to nine. In all, there are four such pairs: the numbers 1 and 8, 2 and 7, 3 and 6, and lastly 4 and 5.

Each of the five numbers belongs to one of those four pairs. By the pigeonhole principle, two of the numbers must be from the same pair–which by construction sums to 9

2. On New Years at New York’s Time Square, over 820 people will have the same birthday.

It will now be useful to use the second version “the maximum must at least be the average.”

There are roughly 300,000 attendees on New Years split over a possible 366 birthdays. The average is 300,000 / 366 = 819.7 people per birthday. The maximum must at least be the average, so there must be a birthday that at least 820 people share.

3. Imagine a certain college has 6,000 Indian students, at least one from each of the 30 states/UT. Then there must be a group of 200 students coming from same state.

Again, we invoke the second version that “the maximum must at least be the average.”

The average is 6,000 / 30 = 200 students per state. The maximum must at least be the average, so there must be a state where 200 students share in common.

Netflix Contest
Netflix contest illustrates the power of Internet and ability to generate scientific interest. The Netflix contest has been widely followed because its lessons could extend well beyond improving movie picks. The researchers from around the world were grappling with a huge data set — 100 million movie ratings — and the challenges of large-scale predictive modeling, which can be applied across the fields of science, commerce and politics. The way teams came together, especially late in the contest, and the improved results that were achieved suggest that this kind of Internet-enabled approach, known as crowdsourcing, can be applied to complex scientific and business challenges. That certainly seemed to be a principal lesson for the winners. The blending of different statistical and machine-learning techniques “only works well if you combine models that approach the problem differently,” said Chris Volinsky, a scientist at AT&T Research and a leader of the Bellkor team. “That’s why collaboration has been so effective, because different people approach problems differently.” Yet the sort of sophisticated teamwork deployed in the Netflix contest, it seems, is a tricky business. Over three years, thousands of teams from 186 countries made submissions. Yet only two could breach the 10-percent hurdle. “Having these big collaborations may be great for innovation, but it’s very, very difficult,” said Greg McAlpin, a software consultant and a leader of the Ensemble. “Out of thousands, you have only two that succeeded. The big lesson for me was that most of those collaborations don’t work.”

Collaborative Science

What is possible, and what is not possible on Internet in collaborative framework is a fascinating area to work upon. Theories on muti-party computations not necessarily secured would be a great area to look on.

Telegraph has created its list of top 10 Nobel prize winners. Last on the list is Sir Clive Granger who was an econometrician for his analysis of time series data with his colleague Rob. Being modest as all great people are, he credits all his success to the lucky breaks he got in his autobiography. He never made to Cambridge and Oxford, but pipped a lot of them to Nobel prize, he concludes

" My story ends with a recipe for success. Do not start too high on the ladder, move to a good but not top university, work hard, have a few good ideas, chose good collaborators (I had over eighty in my career), attract some excellent students, wait twenty years or so, and then retire. It worked for Rob and I."

Continuing with diagonalization

Diagonalization uses some interesting logic to state that if you postulate a statement, an contradictory statement also exists, and you cannot have an algorithm that can solve both contradictory states. But there is a catch. What if there are no contradictions in nature. What if the nature is always right, and found its solutions. Can natural numbers display alternate properties. Can we have unconstrained input set for Turing Machines. If a given state is achieved, what if an alternate state does not exists. In that case Hilbert's second principle can still be realized, and you can create a set of axioms that prove all mathematical statements.

On other implications of Halting problem being not solvable

The Halting problem is a fundamental result in Complexity theory which says that a Turing Machine cannot be created which can solve all problems that could be decided in finite time. If such a machine could be created it could be shown to be self contradictory through diagnolization principle (assuming a problem has been solved by that machine, another problem can be created with opposite results which the machine then cannot solve). This concept was used by Godel to prove his incompleness theorem. The theorem says that you cannot create a set of principles(axioms) that can prove all mathematical statements with completeness(prove all statements true), and soundness(prove all wrong statements false). He said if such a proof system were created, it would solve the halting problem, an impossibility. The implications of this approach are very large. It puts a fundamental limits on what mankind can achieve. Take a glance.

a. A society where everyone is equally rich cannot be created: To create an equal society you will have to create a perfect set of distribution laws, and if it were created, diagonalization can show it to self contradictory. I will ignore diagnolization inferences in remaining parallelizations.

b. Mankind cannot solve all problems in Science..there will always be unsolved problems. Researchers be happy.."Everything that needs to be discovered has been discovered" will never happen.

c. A pure society created on the principles of Koran, Ram Rajya or any other religious conjecture will never achieve perfect happiness for its members: If such a society were created, an equivalent Turing Machine could be created that would solve the happiness function. And through diagnolization it could be shown that an alternate happiness function exists for the same solution which would be contradictory to results already obtained, an impossibility.

d. Poverty can never be eliminated from the face of earth: If poverty were eliminated, through diagonalization it can be shown that an alternate defnition of poverty function exists, and a contradiction would appear in society.

Can you think of others :)

Unification Theories

Physics as a science has attempted to find common causes from unrelated events. A lot of effort has gone into unification attempts like the Maxwell great attempt to unify electomanetic wave equations. Was this approach important..does it have practical implications..It does..Newton unified diverse observations like apple falling on earth, and moon rotating around the earth to create the concept of gravititional forces..resulting all in advances is space technology today. Oersted in the days of gas lamp unified independent observations of magnetism and electricity, resulting in modern field of electrical engineering and specifically turbines which is the basis of all electricity we take for granted today. The Nobel prize in1959 was awarded to the attempts of unifying weak atomic currents and electromagetic interactions. This was the first time a Muslim received Nobel prize (Abdus Salam, Pakistan).

Travel and Nobel Prize 2009 and my travel
Place I visited in last 1 week are celebrating their Nobel prize winners
Hong Kong: Country is celebrating Charles Kao winning Nobel Prize in Physics for discovery of mechanics behind fiber optics. South China morning Post celebrated it with full gusto.
Mumbai: Indian origin Venkatraman Ramakrishnan won 2009 prize in chemistry for work related to ribosomes.
San Francisco: Elizabeth Hepburn for UCSF won Medicine Prize for discovery of teloremase
Santa Barbara: Caol Greidner now in John Hopkins co-winner of Medicine Nobel prize was an undergrad student here in UCSB.
Literature, peace and economics prizes are yet to be announced.