Oz’ Balls Problem: The Solution

idledisc500

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 a blue ball. If the ball was blue, you put it back in the box and take out a red ball.

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

ozpoll

Peter Shor wrote in a comment “I’m fairly sure that there is not enough bias to get cn, but it intuitively seems far too much bias to still be c \sqrt{n}. I want to say n^c. At a wild guess, it’s either c = \frac{2}{3}or c = \frac{3}{4}, since those are the simplest exponents between \frac{1}{2} and 1.”  The comment followed by a heuristic argument of Kevin Kostelo and computer experiments by Lior Silberman that supported the answer n^{3/4}.
Continue reading

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

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

Itamar Pitowsky: Probability in Physics, Where does it Come From?

I came across a videotaped lecture by Itamar Pitowsky given at PITP some years ago on the question of probability in physics that we discussed in two earlier posts on randomness in nature (I, II). There are links below to the presentation slides, and to  a video of the lecture. 

A little over a week ago on Thursday, Itamar,  Oron Shagrir, and I sat at our little CS cafeteria and discussed this very same issue.  What does probability mean? Does it just represent human uncertainty? Is it just an emerging mathematical concept which is convenient for modeling? Do matters change when we move from classical to quantum mechanics? When we move to quantum physics the notion of probability itself changes for sure, but is there a change in the interpretation of what probability is?  A few people passed by and listened, and it felt like this was a direct continuation of conversations we had while we (Itamar and I; Oron is much younger) were students in the early 70s. This was our last meeting and Itamar’s deep voice and good smile are still with me.

In spite of his illness of many years Itamar looked in good shape. A day later, on Friday, he met with a graduate student working on connections between philosophy and computer science.  Yet another exciting new frontier. Last Wednesday Itamar passed away from sudden complications related to his illness.

Itamar was a great guy; he was great in science and great in the humanities, and he had an immense human wisdom and a modest, level-headed way of expressing it. I will greatly miss him.

Here is a link to a Condolence page for Itamar Pitowsky

Probability in physics:
where does it come from?
 

   

Itamar Pitowsky

Dept. of Philosophy, The Hebrew University of Jerusalem

The application of probability theory to physics began in the 19th century with Maxwell’s and Boltzmann’s explanation of the properties of gases in terms of the motion of their constituent molecules. Now the term probability is not a part of the (classical) theory of particle motion; so what does it mean, and where does it come from? Boltzmann thought to reduce the meaning of probability in physics to that of relative frequency. Thus, eg., we never find a container of gas in normal circumstances (equilibrium) with all of its molecules on the right hand side. Now, suppose we could prove this from the principles of mechanics- that a dynamical system with a huge number of particles almost never gets into a state with all its particles on one side. Then, to say that such an event has a vanishing probability would simply mean (and not only imply) that it is very rare.I shall explain Boltzmann’s program and assumptions in some detail, and why, in spite of its intuitive appeal, it ultimately fails. We shall also discuss why quantum mechanics with its “built in” concept of probability does not help much, and review some alternatives, as time permits.

For more information about Itamar Pitowsky, visit his web site. See his presentation slides.

Additional resources for this talk: video.

 

(Here is the original link to the PIPS lecture) My post entitled Amazing possibilities  about various fundamental limitations stated by many great minds that turned out to be wrong, was largely based on examples provided by Itamar.

A Problem on Planar Percolation

Conjecture (Gady Kozma):  Prove that the critical probability for planar percolation on a Cayley graph of the group Z^2 is always an algebraic number.

Gady  mentioned this conjecture in his talk here about percolation on infinite Cayley graphs.  (Update April 30: Today Gady mentioned to me an even bolder question: to show that for every group \Gamma, either all critical probabilities of its Cayley graphs are algebraic, or none is!!;  I recall a similarly bold conjecture regarding the property of being an expander which turned out to be false but was fruitful nevertheless.)

Many problems Continue reading