Randomness is Weird

By Jean Pierre Mutanguha

I've had this thought stuck in my head since December. I was at a conference talk about groups acting on certain spaces. These groups have certain “special” properties and, at the end, the speaker lists several of these properties. Amongst them was the fact that these “special” properties weren't special afterall: 'most' groups had them. He went one step further, he gave us an example like this:

\[ \left\langle q,w,e,r,t,y,u,i,o,p ~|~ \begin{matrix}etreuyuwreui, tuwtwreyyieiqr, pqiyerwrutiyoowitqr,\ tqrqwwerytiuop, iotuetettuou \end{matrix} \right\rangle \]

and said, “Here's a random group I made on the way here. I was on the bus and I laid my fingers lightly on the keyboard. Whenever, the bus bumped it would make me type random letters. Isn't it incredible that I can claim this group has these 'special' properties?!” To be fair, this was only meant as a joke; the description of how he came up with the group got a laugh out of everyone (myself included) in the room.

Despite knowing it was a joke, something about it bothered me. I talked to my advisor afterwards about it and he pointed out to me that 'randomness' doesn't make any sense without a sample space. Basically, my issue was: “What if he wasn't just joking? Do we really know if that group he showed has these properties?” And my advisor explained, “The joke aside, his statement doesn't make sense. He can't meaningfully say here's a random group without describing the sample space (and probability distribution).” Ok, so he didn't explicitly say what the sample space was but he was talking about finitely presented (f.p.) groups. Could that be the implied sample space? If it were then we would like to say that while chosing any random f.p. group, any such group was equally likely. We don't want our method of choosing to favor some groups over others. This would give us a uniform distribution.

So what if he said, “here's a random group from the sample space of f.p. groups chosen with uniform distribution”? Well, it would be nonsense because it is impossible to put a uniform distribution on a countably infinite sample space! To explain why this is true I would have to define what a probability distribution on a sample space (probability space) is and what it means for it to be uniform. This is where measure theory comes into play and completely derails the topic. But I'll try to illustrate this with the integers, which are also countably infinite:

Theorem 1. \( \mathbb Z \) can't be a uniform distribution probability space.

Sketch proof by contradiction: Suppose it were. Then let \( p(0) \) be the probability of choosing 0. We only know that \( p(0) \in [0,1] \). Since the probability is uniform, \( p(0)=p(1) = p(-1) = p(2) = \cdots \). Let \( x = p(0) \). Since \( \mathbb Z \) is countably infinite, we can add up all probabilities to get the total probability, \( 1 \): \[ 1 = \sum_{i \in \mathbb Z} p(i) = \sum_{i \in \mathbb Z} x \] But there's no real number \( x \) that can be added (countably) infinitely many times to get \( 1 \). So \( \mathbb Z \) can't be a uniform distribution space.\(~\Box\)

The above argument holds if \( \mathbb Z \) is replaced with any countably infinite set, e.g., set of f.p. groups. Furthermore, when the sample space is uncountable, e.g. \( [0,1] \), then a similar argument can show that not all subsets of the sample space have a well-defined probability (measure).

Corollary. It doesn't make sense to ask for the probability that a random integer (chosen uniformly) is even.

On the other hand, if the sample space was \( { 1,2,3, 4 } \) then we would need to find \( x \) such that \( 1 = \sum_{i=1}^4 x = 4x \). So \( x = 0.25 \). So a sample space of \( 4 \) items can have a uniform distribution where each item has a probability of a quarter of being chosen.

And that corollary is what my advisor was telling me in the context of f.p. groups. I understood him but the speaker was talking about random f.p. groups just a few minutes earlier. People have written papers upon papers talking properties that random groups have. What is going on? Well, they're redefining what it means to be random when dealing with countably infinite sets.

We're not allowed to choose uniformly randomly from a countably infinite set \( S \) but we can do it for finite sets. So one thing we can do is arrange our set \( S \) into nested hierarchies of finite set \( S_n \), i.e. \[ S_n \subset S \text{ is finite } \forall n \in \mathbb N \] \[ S_1 \subset S_2 \subset S_3 \subset S_4 \subset \cdots \] \[ \bigcup_{n=1}^\infty S_n = S \] Suppose, \( S = \mathbb Z \) and we are interested in whether a 'random' number is even. Then let \( S_n = { i \in \mathbb Z~:~ |i| \le n } \). Now each \( S_n \) is finite (size \( = 2n+1 \)), each one is contained in the next one, and their union is the full set \( \mathbb Z \). Since we can choose uniformly from each \( S_n \), we can ask the probability that a random integer in \( S_n \) is even. Let's call this probability, \( P(\text{even}|S_n) \). Then we compute that:

\[ \begin{aligned} P(\text{even}|S_1) &= \frac{1}{3} & & & P(\text{even}|S_2) &= \frac{3}{5}\\ P(\text{even}|S_3) &= \frac{3}{7} & & & P(\text{even}|S_4) &= \frac{5}{9}\\ P(\text{even}|S_5) &= \frac{5}{11} & & & P(\text{even}|S_6) &= \frac{7}{13} \end{aligned} \]

As you can see, the probability is getting closer and closer to \( \frac{1}{2} \) as \( n \) grows. So we (informally) say the probability that a random integer is even is \( \frac{1}{2} \). But we have to be very careful. We only got the half because of how we defined each \( S_n \). I could have defined them different so that the probability got closer and closer to any number in \( [0,1] \). Yes, I could have defined the \( S_n \)'s so that the probabilities converged to \( 0 \) and we'd have to say the probability a random integer is even is \( 0 \). But the \( S_n \)'s I defined above are the preferred ones because they make use of the natural order of the integers. However, with the same \( S_n \)'s, the prime number theorem implies that:

The probability that a random positive integer is prime is 0.

Wait... What? But prime numbers exist! What do you mean a random number can't be prime? This is another place where probability gets confusing. We all start to learn about (uniform) probability in situations where the sample space is finite. We are taught that the there is an equivalence between probabilistic statements and existential statements. For example, saying “The probability that a random card is a heart is 1/4” is the same thing as saying “13 of the 52 cards are hearts.” Or saying, “The probability that a random student is 8 years old is 0” means “None of the students are 8 years old.” In particular, saying “No random student is 8 years old.” is the exact same thing as saying “No student is 8 years old.” In the finite case, the random adjective can be dropped without changing the meaning.

But once we expand the idea of probability to an infinite sample space, this equivalence is broken. It is tempting to rephrase the above statement about prime numbers as “No positive integer is prime” or “Every positive integer is composite” but that would be a false. So instead, we rephrase the statement as “Almost no positive integer is prime” or “Almost every positive integer is composite.” or keeping the random adjective: “random positive integers are composite/not prime.”

That means there's a difference between “positive integer are not prime” and “random positive integers are not prime.” The adjective, random, means something very important when your sample space (e.g. positive integers) is infinite; it can't just be dropped from the sentence without changing the meaning.

When the sample space is infinite, statements about random objects probably don't mean what you think they mean.

So there are theorems stated as “random (f.p.) groups have [property x]” or “almost every (f.p.) group has [property x]” but it would be wrong (yet funny) to type a bunch of 'random' letters for a group presentation and conclude that that group has [property x] because it was 'random.'

Here is a list of interesting properties about random objects that I've come across.

  • G. Cantor, 1874: random real numbers in \( [0,1] \) are irrational/transcendental.
  • B. L. van der Waerden, 1936: random integer polynomials are not solvable in radicals.
  • M. Gromov, 1993: random groups are word-hyperbolic.
  • P. Dani, 2008: random elements in (nonelementary) word-hyperbolic groups have infinite order.
  • Calegari-Walker, 2014: random groups have many surface subgroups. (This was the statement that inspired this post)
  • J. Maher, 2010: random walks in mapping class groups end on pseudo-Anosov elements.
  • Cumplido-Wiest, 2017: random elements in mapping class groups can be pseudo-Anosov.

What's more interesting is the question of constructing examples. For example, I can give you the easy diagonal argument that real numbers are uncountable but rational/algebraic numbers are countable, so irrational/transcendental numbers must exist. But I haven't given you an example of an irrational/transcendental number. Essentially, it is difficult to tell whether a given number is transcendental even though we know almost all numbers are. Similarly, it takes some work to know if a given integer polynomial is not solvable in radicals even though we know almost all integer polynomials aren't. Same thing goes for being a word-hyperbolic groups.

I found the fourth property while I was looking for a proof that all infinite word-hyperbolic groups had at least one infinite order element. So not only do they have one infinite-order element, almost all elements are infinite-order!

The last two properties listed illustrate how randomness can mean very different things. You would expect random walks to end on random elements but that is not necessarily the case. So we can know that random walks end on special elements without knowing whether random elements are special! At least, we can now say (via an unrelated argument) that random elements can be special, i.e., the probability of being special is not zero. As far as we know, it is possible for random walks to always end on special elements even though special elements are only say 'half' of all the elements.

I'd like to leave you with this question related to random objects and constructivism.

Is there a situation where we know that random objects have a given property but we still have no example of an object with said property?