Combinatorics and more

Test Your Intuition (7)

July 8, 2009 by Gil Kalai

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?

Read the rest of this entry »

Posted in Probability | 17 Comments »

Chess can be a Game of Luck

July 5, 2009 by Gil Kalai

Can chess be a game of luck?

Let us consider the following two scenarios:

A) We have a chess tournament where each of forty chess players pay 50 dollars entrance fee and the winner takes the prize which is 80% of the the total entrance fees.

B) We have a chess tournament where each of forty chess players pay 20,000 dollars entrance fee and the winner takes the prize which is 80% of the the total entrance fees.

Before dealing with these two rather realistic scenarios let us consider the following more hypothetical situations.

C) Suppose that chess players have a quality measure that allows us to determine the probability that any one player will beat the other. Two players play and bet. The strong player bets 10 dollars and the waek player bets according to the probability he will win. (So the expected gain of both player is zero.)

D) Suppose again that chess players have a quality measure that allows us to determine the probability that any one players will beat the other. Two players play and bet. The strong player bets 100,000 dollars and the weak player bets according to the probability he will wins. (Again, the expected gain of both players is zero.)

When we analyze scenarios C and D the first question to ask is “What is the game?” In my opinion we need to consider the entire setting, so the “game” consists of both the chess itself and the betting around it. In cases C and D the betting aspects of the game are completely separated from the chess itself. We can suppose that the higher the stakes are, the higher the ingredient of luck of the combined game. It is reasonable to assume that version C) is mainly a game of skill and version D) is mainly a game of luck.

Now what about the following scenarios:

E) Two players play chess and bet 5 dollars.

Here the main ingredient is skill; the bet only adds a little spice to the game.

F) Two players play chess and bet 100,000 dollars.

Well, to the extent that such a game takes place at all, I would expect that the luck factor will be dominant. (Note that scenario F is not equivalent to the scenario where two players play, the winner gets 300,000 dollars and the loser gets 100,000 dollars.)

Let us go back to the original scenarios A) and B). Here too, I would consider the ingredients of luck and skill to be strongly dependant on the stakes. The setting of scenario A) can be quite compatible with a game of skill where the prizes give some extra incentives to participants (and rewards for the organizers), while in scenario B) it stands to reason that the luck/gambling factor will be dominant.

One critique against my opinion is: What about tennis tournaments where professional tennis players are playing on large amounts of prize money? Are professional tennis tournaments games of luck? There is one major difference between this example and examples A and B above. In tennis tournaments there are very large prizes but the expected gain for a player is positive, all (or at least most) players can make a living by participating. This changes entirely the incentives. This is also the case for various high level professional chess tournaments.

For mathematicians there are a few things that sound strange in this analysis. The luck ingredient is not invariant under multiplying the stakes by a constant, and it is not invariant under giving (or taking) a fixed sum of money to the participants before the game starts. However, these aspects are crucial when we try to analyze the incentives and motives of players and, in my opinion, it is a mistake to ignore them.

So my answer is: yes, chess can be a game of luck.

Now, what about poker? Read the rest of this entry »

Tags: Chess, Gambling, Games of luck, Games of skill, Poker, Robert Aumann
Posted in Controversies, Economics, Games, Law, Probability, Rationality | 11 Comments »

Raigorodskii’s Theorem: Follow Up on Subsets of the Sphere without a Pair of Orthogonal Vectors

July 2, 2009 by Gil Kalai

Andrei Raigorodskii

(This post follows an email by Aicke Hinrichs.)

In a previous post we discussed the following problem:

Problem: Let $A$ be a measurable subset of the $d$ -dimensional sphere $S^d = \{x\in {\bf R}^{d+1}:\|x\|=1\}$ . Suppose that $A$ does not contain two orthogonal vectors. How large can the $d$ -dimensional volume of $A$ be?

Setting the volume of the sphere to be 1, the Frankl-Wilson theorem gives a lower bound (for large $d$ ) of $1.203^{-d}$ ,
2) The double cap conjecture would give a lower bound (for large $d$ ) of $1.414^{-d}$ .

A result of A. M. Raigorodskii from 1999 gives a better bound of $1.225^{-d}$ . (This has led to an improvement concerning the dimensions where a counterexample for Borsuk’s conjecture exists; we will come back to that.) Raigorodskii’s method supports the hope that by considering clever configurations of points instead of just $\pm 1$ -vectors and applying the polynomial method (the method of proof we described for the Frankl-Wilson theorem) we may get closer to and perhaps even prove the double-cap conjecture.

What Raigorodskii did was to prove a Frankl-Wilson type result for vectors with $0,\pm1$ coordinates with a prescribed number of zeros. Here is the paper.

Now, how can we bit beat the $1.225^{-d}$ record???

Posted in Uncategorized | 1 Comment »

Test Your Intuition (6)

June 29, 2009 by Gil Kalai

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?

Posted in Uncategorized | 11 Comments »

Praise For ‘Gina says’

June 24, 2009 by Gil Kalai

Praise for: ” ‘Gina Says,’ Adventures in the Blogsphere String War

(Below the dividing line: Greg Kuperberg, Scott Aaronson, Clifford Johnson, Peter Woit, Motty Perry, Caterina Calsamiglia, Yuval Peres, Eva Illouz, and (right from the comment section) Luca Trevisan, Thomas Love, John Sidles, Jacques Distler, Marni D Sheppeard, (and from other journals/blogs) Hamish Johnston, Lance Fortnow: .

Download the first part of the book (pdf file) (See also this post)

Shmuel Weinberger (August 07): Very much enjoyed the story of Gina’s involvement in the blog world– i read it through on my flight back to America. It was a very interesting if occasionally difficult read. Probably the part that resonated most was the advice (i think it came from your father) that every subject is fascinating after you study it deeply.

Avi Wigderson: (August 07) I expected no less from the author of the immortal translation of the classic book “Where is Pluto?”

Oded Schramm (Dec 2007): Though it is somewhat uneven, there were some definite enjoyable highlights. (Feb. 08 ) What about a sequel? I’m really curious what’s happening with Gina these days?

Itai Benjamini It was such a joy to listen to your unique voice (music) yet again. A typo: Section 20 “children’s teaching disabilities” should be “children learning disabilities”. (Feb 08 ):

Elchanan Mossel (Feb 08): I read it when I was sick and couldn’t do other things, and it cheered me up

Olle Haggstrom (March 08): I found it a real page-turner, and read the entire thing for four straight hours last night! Very interesting stuff, on several levels. And very original, of course. May I ask what is your relation to Gina? You seem to have remarkable insight into her mind…

Ken Binmore (June 08) Dear Gil, I like your book a lot. If you get it published, it could do with Read the rest of this entry »

Posted in Book review, Gina Says | 10 Comments »

My Book: “Gina Says,” Adventures in the Blogsphere String War

June 23, 2009 by Gil Kalai

I wrote a book. It is a sort of a popular science book and it is also about blogging and debating.

You can download the first part of the book : It is a 94 page pdf file.

“Gina Says,”

Adventures in the

Blogsphere String War

selected and edited by Gil Kalai

Praise for “Gina Says”

Preface

Debates portrayed in books, are the worst sort of readings, Jonathan Swift.

In the summer of 2006 two books attacking string theory, a prominent theory in physics, appeared. One by Peter Woit called “Not even wrong” and the other by Lee Smolin called “The trouble with Physics.” A fierce public debate, much of it on weblogs, ensued.

Gina is very curious about science blogs. Can they be useful for learning about, or discussing science? What happens in these blogs and who participates in them? Gina is eager to learn the issues and to form her own opinion about the string theory controversy. She is equipped with some academic background, even in mathematics, and has some familiarity with academic life. Her knowledge of physics is derived mainly from popular accounts. Gina likes to debate and to argue and to be carried by her associations. She is fascinated by questions about rationality and philosophy, and was exposed to various other scientific controversies in the past.

This book uses the blog string theory debate to tell about blogs, science, and mathematics. Meandering over various topics Read the rest of this entry »

Posted in Blogging, Gina Says | 23 Comments »

A Little Story Regarding Borsuk’s Conjecture

June 22, 2009 by Gil Kalai

Jeff Kahn

Jeff and I worked on the problem for several years. Once he visited me with his family for two weeks. Before the visit I emailed him and asked: What should we work on in your visit?

Jeff asnwered: We should settle Borsuk’s problem!

I asked: What should we do in the second week?!

and Jeff asnwered: We should write the paper!

And so it was.

Posted in Uncategorized | 2 Comments »

Borsuk’s Conjecture

June 21, 2009 by Gil Kalai

Karol Borsuk conjectured in 1933 that every bounded set in $R^d$ can be covered by $d+1$ sets of smaller diameter. Jeff Kahn and I found a counterexample in 1993. It is based on the Frankl-Wilson theorem.

Let $\cal G$ be the set of $\pm 1$ vectors of length $n$ . Suppose that $n=4p$ and $p$ is a prime, as the conditions of Frankl-Wilson theorem require. Let ${\cal G'} = \{(1/\sqrt n)x:x \in {\cal G}\}$ . All vectors in ${\cal G}'$ are unit vectors.

Consider the set $X=\{x \otimes x: x \in {\cal G}'\}$ . $X$ is a subset of $R^{n^2}$ .

Remark: If $x=(x_1,x_2,\dots,x_n)$ , regard $x\otimes x$ as the $n$ by $n$ matrix with entries $(x_ix_j)$ .

It is easy to verify that:

Claim: $<x \otimes x,y\otimes y> = <x,y>^2$ .

It follows that all vectors in $X$ are unit vectors, and that the inner product between every two of them is nonnegative. The diameter of $X$ is therefore $\sqrt 2$ . (Here we use the fact that the square of the distance between two unit vectors $x$ and $y$ is 2 minus twice their inner product.)

Suppose that $Y \subset X$ has a smaller diameter. Write $Y=\{x \otimes x: x \in {\cal F}\}$ for some subset $\cal F$ of $\cal G$ . This means that $Y$ (and hence also $\cal F$ ) does not contain two orthogonal vectors and therefore by the Frankl-Wilson theorem

$|{\cal F}| \le U=4({{n} \choose {0}}+{{n}\choose {1}}+\dots+{{n}\choose{p-1}})$ .

It follows that the number of sets of smaller diameter needed to cover $X$ is at least $2^n / U$ . This clearly refutes Borsuk’s conjecture for large enough $n$ . Sababa.