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?

What does “beyond a reasonable doubt” practically mean?

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

Is Backgammon in P?

 

The Complexity of Zero-Sum Stochastic Games with Perfect Information

Is there a polynomial time algorithm for chess?  Well, if we consider the complexity of chess in terms of the board size then it is fair to think that the answer is “no”. But if we wish to consider the complexity in terms of the number of all possible positions then it is easy to go backward over all positions and determine what is the outcome of the game when we start with each given position. 

Now, what about backgammon?  Continue reading

Emmanuel Abbe: Erdal Arıkan’s Polar Codes

Click here for the most recent polymath3 research thread. A new thread is comming soon.

Emmanuel Abbe and Erdal Arıkan

This post is authored by Emmanuel Abbe

A new class of codes, called polar codes, recently made a breakthrough in coding theory.

In his seminal work of 1948, Shannon had characterized the highest rate (speed of transmission) at which one could reliably communicate over a discrete memoryless channel (a noise model); he called this limit the capacity of the channel. However, he used a probabilistic method in his proof and left open the problem of reaching this capacity with coding schemes of manageable complexities. In the 90’s, codes were found (turbo codes and LDPC rediscovered) with promising results in that direction. However, mathematical proofs could only be provided for few specific channel cases (pretty much only for the so-called binary erasure channel). In 2008,  Erdal Arıkan at Bilkent University invented polar codes, providing a new mathematical framework to solve this problem.

Besides allowing rigorous proofs for coding theorems, an important attribute of polar codes is, in my opinion, that they bring a new perspective on how to handle randomness (beyond the channel coding problem). Indeed, after a couple of years of digestion of Arıkan’s work, it appears that there is a rather general phenomenon underneath the polar coding idea. The technique consist in applying a specific linear transform, constructed from many Kronecker products of a well-chosen small matrix, to a high-dimensional random vector (some assumptions are required on the vector distribution but let’s keep a general framework for now). The polarization phenomenon, if it occurs, then says that the transformed vector can be split into two parts (two groups of components): one of maximal randomness and one of minimal one (nearly deterministic). The polarization terminology comes from this antagonism. We will see below a specific example. But a remarkable point is that the separation procedure as well as the algorithm that reconstructs the original vector from the purely random components have low complexities (nearly linear). On the other hand, it is still an open problem to characterize mathematically if a given component belongs to the random or deterministic part. But there exist tractable algorithms to figure this out accurately.

Let us consider the simplest setting. Let X_1,...,X_n be i.i.d. Bernoulli(p) and assume that $n$ is a power of 2. Define G_n to be the matrix obtained by taking \log_2(n) Kronecker products of G_2=\begin{pmatrix}1&0\\1&1\\\end{pmatrix} , and multiply X=(X_1,...,X_n) with G_n over GF(2) to get U=(U_1,...,U_n). Note that U has same entropy as X, since G_n is invertible (its inverse is itself). However, if the entropy of X is uniformly spread out over its components, i.e., H(X)=nH(X_1), the entropy of U may not be, since its components are correlated. In any case, we can write H(U)= \sum_i H(U_i|U^{i-1}) where U^{i-1}=(U_1,...,U_{i-1}) are the `past components’. The polarization phenomenon then says that, except for a vanishing fraction of indices i (w.r. to n), each term H(U_i|U^{i-1}) tends to either 0 or 1.

Continue reading

Benoît’s Fractals

Mandelbrot set

Benoît Mandelbrot passed away a few dayes ago on October 14, 2010. Since 1987, Mandelbrot was a member of the Yale’s mathematics department. This chapterette from my book “Gina says: Adventures in the Blogosphere String War”   about fractals is brought here on this sad occasion. 

A little demonstration of Mandelbrot’s impact: when you search in Google for an image for “Mandelbrot” do not get pictures of Mandelbrot himself but rather pictures of Mandelbrot’s creation. You get full pages of beautiful pictures of Mandelbrot sets

.

Benoit Mandelbrot (1924-2010)

Modeling physics by continuous smooth mathematical objects have led to the most remarkable achievements of science in the last centuries. The interplay between smooth geometry and stochastic processes is also a very powerfull and fruitful idea. Mandelbrot’s realization of the prominence of fractals and his works on their study can be added to this short list of major paradigms in mathematical modeling of real world phenomena.

Fractals

Fractals are beautiful mathematical objects whose study goes back to the late 19th century. The Sierpiński triangle and the Koch snowflake are early examples of fractals which are constructed by simple recursive rules. Continue reading

Midrasha Talks are Now Online

Itai Benjamini listening to Gadi Kozma

There are 41 lectures from the Midrasha on Probability and Geometry: The Mathematics of Oded Schramm which are now online.

Joram Lindenstrauss’s concluding lecture (click on the picture to see)

Laci Lovasz

More pictures and links to some lectures below the line (I will slowly update them).

Continue reading

Test Your Intuition (11): Is it Rational to Insure a Toaster

Here is a question from last year’s exam in the course “Basic Ideas of Mathematics”:
 
You buy a toaster for 200 NIS ($50) and you are offered one year of insurance for 24 NIS ($6).
 
a) Is it worth it if the probability that damage covered by the insurance will occur during the first year is 10%? (We assume that without insurance, such damage makes the toaster a “total loss”.)
 
b) Is it worth it if the probability that the toaster will be damaged is unknown?
 
As an additional test of your imagination, can you think of reasons why buying the toaster insurance would be rational?