Taking balls away: Oz’ Version

This post is based on a comment by Oz to our question about balls with two colors:

“There is an interesting (and more difficult) variation I once heard but can’t recall where:

You have a box with n red balls and n blue balls. You take out each time a ball at random as before. But, if the ball was red, you put it back in the box and take out a blue ball. If the ball was blue, you put it back in the box and take out a red ball.

You keep as before until left only with balls of the same color. How many balls will be left (as a function of n)?

1) Roughly  εn for some ε>0.

2) Roughly \sqrt n?

3) Roughly log n?

4) Roughly a constant?

5) Some other behavior

Answer to test your intuition (18)

You have a box with n red balls and n blue balls. You take out balls one by one at random until left only with balls of the same color. How many balls will be left (as a function of n)?

1) Roughly  εn for some ε>0.

2) Roughly \sqrt n?

3) Roughly log n?

4) Roughly a constant?

poll18

Here is the collective intuition regarding this problem

Continue reading

Itai Ashlagi, Yashodhan Kanoria, and Jacob Leshno: What a Difference an Additional Man makes?

AshlagiKanoriaLeshno2

We are considering the stable marriage theorem. Suppose that there are n men and n women. If the preferences are random and men are proposing, what is the likely average women’s rank of their husbands, and what is the likely average men’s rank of their wives?

Boris Pittel proved that on average a man will be matched to the woman in place log n on his list. (Place one is his most preferred woman.) A woman will be matched on average to a man ranked n/log n on her list.

We asked in the post “Test your intuition (19)”  what is the situation if there is one additional man, and men are still proposing. This question is based on a conversation with Jacob Leshno who told me about a remarkable paper Unbalanced random matching markets by Itai Ashlagi, Yash Kanoria, and Jacob Leshno. Continue reading

Test Your Intuition (19): The Advantage of the Proposers in the Stable Matching Algorithm

Shapleygale

Stable mariage

The Gale-Shapley stable matching theorem and the algorithm.

GALE-SHAPLEY THEOREM Consider a society of n men and n women and suppose that every man [and every woman] have a preference (linear) relation on the women [men] he [she] knows. Then there is a stable marriage, namely a perfect matching between the men and the women so that there are no men and women which are not matched so that both of them prefer the other on their spouces.

Proof: Consider the following algorithm, on day 1 every man goes to the first woman on his list and every woman select the best man among those who come to her and reject the others. On the second day every rejected men go to the second woman on his list and every woman select one man from all man that comes to her (including the man she selected in the previous day if there was such a man) and rejects all others, and so on. This process will terminate after finitely many days and with a stable marriage! To see that the process terminate note that each day at least one man will come to a new women, or go back home after beeing rejected from every women (n+1 possibilities) and none of these possibilitie will ever repeat itself so after at most n^2+n days things will stabilize. When it terminates we have a stable marriage because suppose women W and men M are not married at the end. If M is married to a women he prefers less then W or to no women at all it means that M visited W and she rejected him so she had a better men than M.  Sababa!
It turns out that the above algorithm where the men are proposing and being rejected is optimal for the men! If a man M is matched to a woman W then there is not a single stable marriage where M can be matched to a woman higher on his list. Similarly this algorithm is worst for the women. But by how much?

Random independent preferences

Question 1:  There are n men and n women. If the preferences are random and men are proposing, what is the likely average women’s rank of their husbands, and what is the likely average men’s rank of their wives.

You can test your intuition, or look at the answer and for a follow up question after the fold.

Continue reading

Test Your Intuition (18): How many balls will be left when only one color remains?

(Thanks to Itai Benjamini and Ronen Eldan.) Test (quickly) your intuition:  You have a box with n red balls and n blue balls. You take out balls one by one at random until left only with balls of the same colour. How many balls will be left (as a function of n)?

1) Roughly  εn for some ε>0.

2) Roughly \sqrt n?

3) Roughly log n?

4) Roughly a constant?

Mittag-Leffler Institute and Yale, Winter 2005; Test your intuition: Who Played the Piano?

This is a little “flashback” intermission in my posts about my debate with Aram Harrow. This time I try to refer to Cris Moore’s question regarding  the motivation for my study. For the readers it gives an opportunity to win a $50 prize! 

Let me also bring to your attention an interesting discussion (starting here) between Peter Shor and me regarding smoothed Lindblad evolutions.

(Cris Moore, the debate’s very first comment!) I am also a little confused by Gil’s motivation for his conjectures.  (My response:)  To the best of my memory, my main motivation for skeptically studying quantum fault-tolerance was that I thought that this is a direction worth pursuing and that I had a shot at it.

micheldevoretposter (1)

While listening with Ravi Kannan to this 2002 lecture by Michel Devoret at Yale, I wondered if there are enough scientists working on the “mirage” side.

Flashback: Mittag-Leffler 2005

I started systematically thinking about quantum fault-tolerance in February 2005. There were several things that triggered my interest to the question in the previous fall and I decided to spend some time learning and thinking about it in our winter break.  One of those triggers was something Dorit Aharonov told me a few months earlier: she said that once, when she was telling her students about quantum computers, she suddenly had a feeling that maybe it was all just nonsense. Another trigger came from a former student who told me about a Polish scientist (whose name he could not remember) who wrote an article about impossibility of quantum error-correction. I thought that the lack of a quantum analog of the repetition code, and the unique properties of the majority function  in terms of sensitivity to noise that I studied with Itai Benjamini and Oded Schramm earlier could be a good starting point for looking skeptically at quantum computers.  

In our 2005 winter break, I spent two weeks at Yale and then additional two weeks at the Mittag-Leffler institute near Stockholm.  At Yale, I only had little time to think about quantum computers. I had to finish a survey article with Muli Safra about threshold phenomena (To a volume that Cris Moore and Allon Perkus were among the editors).  One of the last days in Yale we went to dinner with two guests, Chris Skinner who gave the colloquium talk, and Andrei Okounkov who visited me and gave a talk about partition enumeration and mirror symmetry. At the dinner Andrew Casson asked, out of the blue, if we think that quantum computers can be built and it almost seemed as if that Andrew was reading my mind on what I plan to work on the weeks to come. My answer there was the same as my answer now, that I tend to find it implausible.

Mittag-Leffler Institute February 2005 with Xavier Viennot and Alain Lascoux

In Sweden I spent most of my time on quantum fault-tolerance. I was jet-lagged and being jet-lagged in the Mittag-Leffler institute already worked for me once, when finding my subexponential randomized variant of the simplex algorithm was a substitute for sleeping some night in fall 1991 . In 2005 it was not as bad, I just came to my office very early in the morning and started working. And very early in the morning somebody was already playing the piano.

And who was playing the piano at the institute in the cold Swedish mornings of February 2005? The first reader to guess correctly, and convince me in a comment that she or he knows the answer without revealing it to everybody else will get $50. Continue reading

Test Your Intuition (17): What does it Take to Win Tic-Tac-Toe

ttt

(A few more quantum posts are coming. But let’s have a quick break for games.)

Tic Tac Toe is played since anciant times. For the common version, where the two players X and O take turns in marking the empty squares in a 3 by 3 board – each player has a strategy that can guarantee a draw.

Now suppose that the X player has a budget of Y dollars, the O playare has a budget of 100 dollars and before each round the two players bid who makes the next move. The highest bidder makes the move and his budget is reduced by his bid.

For example, if, to start with, the X player have 120 dollars, and if for the first move X bids 40 dollars and O bids 30 dollars, then X will make the first move and will be left with 80 dollars while O will be left with his 100 dollars.

What would you expect the minimal value of Y is so the X player has a winning strategy? Of course if Y>300, X can make 3 uninterrupted moves and win, but perhaps much less is enough?

(Thanks to Reshef Meir and Moshe Tennenholtz)

Update: Another variant of this game is when the player winning the turn pays his bid to the other player. (This version is called “Richman game,” while the variant above is called “Poorman game”. In this case if Y> 800 the X player can play three moves and win. And again the question is what is the infimum value of Y for which the X player can force a win…

What does “beyond a reasonable doubt” practically mean?

(Motivated by two questions from Gowers’s How should mathematics be taught to non mathematicians.)

Test Your Intuition (16): Euclid’s Number Theory Theorems

Euclid’s

Euclid’s book IX on number theory contains 36 propositions.

The 36th proposition is:

Proposition 36.If as many numbers as we please beginning from a unit are set out continuously in double proportion until the sum of all becomes prime, and if the sum multiplied into the last makes some number, then the product is perfect.

It asserts that if 2^n-1 is a prime number then 2^{n-1}\cdot (2^n-1) is a perfect number. (A number m is perfect of it is equal to the sum of its proper divisors.)

This is certainly a remarkable achievement of ancient Greek mathematics. Other Propositions of the same book would be less impressive for us:

Proposition 23.If as many odd numbers as we please are added together, and their multitude is odd, then the sum is also odd.

Proposition 24.If an even number is subtracted from an even number, then the remainder is even.

Proposition 25.If an odd number is subtracted from an even number, then the remainder is odd.

Proposition 26.If an odd number is subtracted from an odd number, then the remainder is even.

Proposition 27.If an even number is subtracted from an odd number, then the remainder is odd.

Proposition 28.If an odd number is multiplied by an even number, then the product is even.

Proposition 29.If an odd number is multiplied by an odd number, then the product is odd.

Test your intuition: What is the reason that deep mathematical results are stated by Euclid along with trivial results.

Test Your Intuition (15): Which Experiment is More Convincing

Consider the following  two scenarios

(1) An experiment tests the effect of a new medicine on people which have a certain illness. The conclusion of the experiment is that for 5% of the people tested the medication led to improvement while for 95% it had no effect. (The experiment followed all rules: it had a control test it was double blind etc. …)

A statistical analysis concluded that the results are statistically significant, where the required statistical significance level is 1%. This roughly means that the probability p_1  that such an effect happend by chance (under the “null hypothesis”) is less or equal 0.01. (This probability is called the p-value. Suppose that p_1= 0.008.)

(2) An experiment tests the effect of a new medicine on people which have a certain illness. The conclusion of the experiment is that for 30% of the people tested the medication led to improvement while for 70% it had no effect. (The experiment followed all rules: it had a control test it was double blind etc. …)

A statistical analysis concluded that the results are statistically significant, where the required statistical significance level is 1%. (Again, this roughly means that the probability p_2  that such an effect happend by chance (under the “null hypothesis”) is less or equal 0.01. And again suppose that p_2= 0.008.)

Test your intuition: In which of these two scenarios it is more likely that the effect of the medication is real.

You can assume that the experiments are identical in all other terms that may effect your answer. E.g., the theoretical explanation for the effect of the medicine. Note that our assumption p_1=p_2 is likely to imply that the sample size for the first experiment is larger.