Category Archives: Probability

Lawler-Kozdron-Richards-Stroock’s combined Proof for the Matrix-Tree theorem and Wilson’s Theorem

   David Wilson and a cover of Shlomo’s recent book “Curvature in mathematics and physics” A few weeks ago, in David Kazhdan’s basic notion seminar, Shlomo Sternberg gave a lovely presentation Kirchho ff and Wilson via Kozdron and Stroock. The lecture is based on … Continue reading

Posted in Combinatorics, Computer Science and Optimization, Probability | Tagged , , | 4 Comments

Oz’ Balls Problem: The Solution

A commentator named Oz proposed the following question: You have a box with n red balls and n blue balls. You take out each time a ball at random but, if the ball was red, you put it back in the box and take out … Continue reading

Posted in Probability, Test your intuition | Tagged , , , | 1 Comment

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 … Continue reading

Posted in Guest post, Probability, Test your intuition | Tagged , , | 14 Comments

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)? … Continue reading

Posted in Probability, Test your intuition | Tagged , , , , | 3 Comments

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

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 … Continue reading

Posted in Economics, Games, Probability, Test your intuition | Tagged , , , , | Leave a comment

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

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 … Continue reading

Posted in Combinatorics, Games, Probability, Test your intuition | Tagged , , , , , , | 7 Comments

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 … Continue reading

Posted in Probability, Test your intuition | 26 Comments

What does “beyond a reasonable doubt” practically mean?

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

Posted in Law, Probability, Test your intuition | 18 Comments

Noise Sensitivity and Percolation. Lecture Notes by Christophe Garban and Jeff Steif

Lectures on noise sensitivity and percolation is a new beautiful monograph by Christophe Garban and Jeff Steif. (Some related posts on this blog: 1, 2, 3, 4, 5)

Posted in Combinatorics, Probability | Tagged , , , , | Leave a comment

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 … Continue reading

Posted in Computer Science and Optimization, Games, Open problems, Probability | 9 Comments