Let $latex {n}&fg=000000$ be a natural number. We consider the question of how many «almost orthogonal» unit vectors $latex {v_1,\ldots,v_m}&fg=000000$ one can place in the Euclidean space $latex {{\bf R}^n}&fg=000000$. Of course, if we insist on $latex {v_1,\ldots,v_m}&fg=000000$ being exactly orthogonal, so that $latex {\langle v_i,v_j \rangle = 0}&fg=000000$ for all distinct $latex {i,j}&fg=000000$, then we can only pack at most $latex {n}&fg=000000$ unit vectors into this space. However, if one is willing to relax the orthogonality condition a little, so that $latex {\langle v_i,v_j\rangle}&fg=000000$ is small rather than zero, then one can pack a lot more unit vectors into $latex {{\bf R}^n}&fg=000000$, due to the important fact that pairs of vectors in high dimensions are typically almost orthogonal to each other. For instance, if one chooses $latex {v_i}&fg=000000$ uniformly and independently at random on the unit sphere, then a standard computation (based on viewing the $latex {v_i}&fg=000000$ as gaussian…

Cantor’s theorem is somewhat infamous as a mathematical result that many non-mathematicians have a hard time believing. Trying to disprove Cantor’s theorem is a popular hobby among students and cranks; even Eliezer Yudkowsky₁₉₉₃ fell into this trap once. I think part of the reason is that the standard proof is not very transparent, and consequently is hard to absorb on a gut level.

The goal of this post is to present a rephrasing of the statement and proof of Cantor’s theorem so that it is no longer about sets, but about a particular kind of game related to the prisoner’s dilemma. Rather than showing that there are no surjections $latex X \to 2^X$, we will show that a particular kind of player in this game can’t exist. This rephrasing may make the proof more transparent and easier to absorb, although it will take some background material about the…

In preparation for my upcoming course on random matrices, I am briefly reviewing some relevant foundational aspects of probability theory, as well as setting up basic probabilistic notation that we will be using in later posts. This is quite basic material for a graduate course, and somewhat pedantic in nature, but given how heavily we will be relying on probability theory in this course, it seemed appropriate to take some time to go through these issues carefully.

We will certainly not attempt to cover all aspects of probability theory in this review. Aside from the utter foundations, we will be focusing primarily on those probabilistic concepts and operations that are useful for bounding the distribution of random variables, and on ensuring convergence of such variables as one sends a parameter $latex {n}&fg=000000$ off to infinity.

We will assume familiarity with the foundations of measure theory; see for instance these…