Consider the following game: you have a box that contains one white ball and one black ball. You choose a ball at random and then return it to the box. If you chose a white ball then a white ball is added to the box, and if you chose a black ball then a black ball is added to the box. Played over time, what is the probability that more than 80 percents of the chosen balls are white?

This is not as clear cut a question as the earlier ones, and if you do not know an answer then it will be difficult to figure one out just based on intuition. (But perhaps possible).

If you are intrigued by the question and would like to explore what an answer could be, I would be interested to know how you tried to find an answer.  Asked a colleague? Looked at a book (which?)? Looked online (where?)?

Here is the question:

A differentiable complex function automatically has derivatives of every order. (In contrast to differentiable real functions that need not have even second derivatives at any point.)

Can you describe this “miracle” as part of a more general phenomenon?

Let G be a graph and u and v two vertices.

(1) Let H be a random graph where every edge of G is chosen with probability ½. Let p be the probability that there is a path between u and v in H.

(2) Let T be a random orientation of the graph G. Namely, every edge {x,y} is directed from x to y with probability ½ and otherwise it is directed from from y to x. Let q be the probability that there is a directed path from u to v in T.

What is the relation between p and q?

This is an old theorem of Colin McDiarmid: Continue reading

Question: Let $X=[0,1]^d$ be the $d$-dimensional cube. Turn $X$ into a torus $T^d$ by identifying opposite facets. What is the minumum $(d-1)$-dimensional volume $f(d)$ of a subset $Y$ of $X$ which intersects every non-trivial cycle in $T^d$.

Answer: Taking $Y$ to be all points in the solid cube with one coordinate having value 1/2, gives you a set $Y$ that seperates all cycles and has $(d-1)$-dimensional volume equals $d$. It is not difficult to prove that $f(d) \ge C\sqrt d$. Guy Kindler, Ryan O’donnell, Anup Rao and Avi Wigderson proved the existence of $Y$ which seperates all cycles with $vol(Y) =O(\sqrt d)$. A simpler argument was found by Noga Alon and Boaz Klartag.  For an even simpler treatement of this result along with several discrete analogs see this paper by Noga.

Let $X=[0,1]^d$ be the $d$-dimensional cube. Turn $X$ into a torus $T^d$ by identifying opposite facets. What is the minumum $(d-1)$-dimensional volume $f(d)$ of a subset $Y$ of $X$ which intersects every non-trivial cycle in $T^d$.

Question: Let $Q_n=[-\frac 12,\frac 12]^n\subseteq {\bf R}^n$ be the cube in ${\bf R}^n$ centered at the origin and having $n$-dimensional volume equal to one.  What is the maximum $(n-1)$-dimensional volume $M(d)$ of $(H\cap Q_n)$ when $H \subseteq {\bf R}^n$ is a hyperplane?
Can you guess the behavior of $M(n)$ when $n \to \infty$? Can you guess the plane which maximizes the area of intersection for $n=3$?
Question:  Suppose that we sequentially place $n$ balls into $n$ boxes by putting each ball into a randomly chosen box. It is well known that when we are done, the fullest box has with high probability $(1+o(1))\ln n/\ln \ln n$ balls in it. Suppose instead that for each ball we choose two boxes at random and place the ball into the one which is less full at the time of placement. What will be the maximum occupancy?