Archive for the 'Probability' Category

New random()

A new advance on a method known as a randomness extractor makes it easier for machines generate truly random numbers by harvesting randomness from the environment.

The new randomness extractor combines two independent sources of weakly random numbers into one set that is nearly random, with only minor deviations. Then the researchers use a “resilient function,” a method of combining information, to turn the string of numbers into one truly random bit — a 1 or 0.

Compared with the previous state-of-the-art randomness extractors, which required input that was already very close to random, the new method can mine sources that are “much, much, much, much weaker,” says computer scientist Avi Wigderson of the Institute for Advanced Study in Princeton, N.J. The new extractor is a “substantial improvement over the previous results, and it’s very close to the best you can hope for.”

Advertisements

Best Mathematical Puzzle ?

One of the most interesting mathematical problems ever :

There are 100 prisoners who are sentenced to death. However, the prison’s head, being merciful, offers them a possible way out: He puts 100 identical boxes, perfectly arranged in a row, in the death chamber and places the prisoner’s names in them, one name per box. The prisoners wait in a room outside the death chamber. Each prisoner is asked to proceed to the death chamber and open at most 50 boxes. If he finds his name in one of them he is transferred to the mercy room where he waits. If all prisoners succeed in finding their names then they are all spared from death and are released. On the event that one of them fails to find his name in one of the 50 boxes of his choice, the process is stopped and all prisoners are immediately executed. The prisoners can talk to one another whilst in the waiting room, but, once a prisoner gets transferred to the death chamber or the mercy room, he cannot tell the others anything at all.

Can the prisoners devise a strategy to increase their chance of survival?

Without a strategy, each prisoner has a 50% chance to find his name, and the chance that all of them find their names and survive is practically zero (1/2^100). Give it a shot. Hint: The prisoners actually have a good chance of survival.

Professor Takis Konstantopoulos posted this a few weeks ago and he also posted the answer here if you are ready to give up.