# Must every event have a probability?

Is it possible for an event to simply happen for which it is impossible to define any probability?
(Note: By "impossible" I don't mean just "impractical" -- I really mean that the event should not follow any probability distribution.)

Somewhat similarly: can a "random" number generator exist which does not follow any probability distribution?

-
In my measure theory class, the lecturer briefly mentioned how measure theory is the foundation of modern probability theory. The events are measurable sets and their probability is the measure of that set, so perhaps some unnatural type of event corresponds to an unmeasurable set. Hopefully someones answer to this will address this. – Ragib Zaman Nov 10 '11 at 11:05
I think the ''philosophy'' tag is appropriate for this question. – David Mitra Nov 10 '11 at 11:14
Probably the terminology in mathematics is the reverse of what you are saying. We start with a "sample space" $\Omega$, and then consider only some of the subsets, called "events", and assign probabilities to them. Other subsets, without probabilities, are not called "events". Now of course it is often the case (in mathematical statistics, for example) that we talk of an event such that the probability exists, but we don't know what it is. – GEdgar Nov 10 '11 at 12:54
The probability is given for sets of events, not just a single event. In case of the uniform probability on $[0,1]$, for example, any event (a point) is contained in a non-measurable set. That is, each event is contained in a set for which a probability is not defined. – André Caldas Nov 10 '11 at 14:27
@QiaochuYuan: Ah -- I meant it from a mathematical standpoint. i.e. I wasn't looking for something that is impractical, but something that's theoretically impossible to give a probability to. – Mehrdad Nov 10 '11 at 18:52

Consider the following situation. Fix a group $G$ and a subset $S$ of $G$. Pick an element of $G$ and ask yourself: What is the probability of getting an element of $S$?

Example 1: If $G$ is a finite group, then the unique natural intrinsic notion of probability is given by the cardinality of $S$ divided by the cardinality of $G$.

Example 2: If $G$ is compact, the unique natural thing to do is to look at the Haar measure of $S$.

Example 3: If $G$ is amenable, the unique natural thing to do is to look at the value that an invariant mean takes over $S$. Since there are might be many invariant means, this already leads to some ambiguity.

In general, it seems that what we need is just a measure on $G$ which leaves invariant the characteristic function of $S$.

Now, have a look here http://mathoverflow.net/questions/60247/when-is-non-amenablity-witnessed-by-a-single-non-measurable-set It is proved that there is a group $G$ and a subset $S$ such that there are NO measures on $G$ which leave invariant only the characteristic function on $S$. In my opinion, this is a case where it is not possible to define the probability of getting an element of $S$ when picking casually an element of $G$.

-
+1, although I'm a little hesitant about "picking an element of G" (how do you do that if it's infinite and uncountable, e.g. generating a random real number?). – Mehrdad Nov 10 '11 at 18:56
We can restrict to $G$ countable, since Moore's result linked above holds already for countable group. I don't know how to pick really an element: put your group into a box, close your eyes and pick an element.. :) – Valerio Capraro Nov 10 '11 at 22:51

You might be interested to read about Chaitin's constant $\Omega$, which is the probability that a randomly chosen computer program will eventually terminate (you may worry a bit about the idea of a 'randomly chosen' computer program, and you'd be right to, but trust me that it can be made precise).

Chaitin's constant is a well-defined probability, so it doesn't quite answer your question, but it is non-computable, in the sense that you can't write a computer program which will output the value of the constant.

With a little bit of thinking, the reason for this becomes clear: In order to compute the probability, you would have to examine every possible program and decide if it terminates or not. Obviously this is impossible as there are infinitely many programs, but let's say that we just have to examine a sufficiently large number $N$ of possible programs to get a good estimate of the probability.

Call the program we're currently examining A. That means that you need some other program B, which can look at A and decide in a finite amount of time if A will terminate or not. But Turing proved that it is impossible to write program B so that it works on every input A - that is, there is always an input A which will cause B to run forever. So as we demand more and more accurate estimates of $\Omega$ (i.e. we increase $N$) we will eventually come across an input that causes program B to run forever, meaning that we can never compute the value of $\Omega$.

-
You mean "an input that causes program B not to halt"? – joriki Nov 10 '11 at 13:28
Yes. Yes I do. Thanks. – Chris Taylor Nov 10 '11 at 13:51
Ah, I've actually already read about Chaitin's constant and the halting problem, but as you mention, it has a probability, even though you can't figure it out. I'm looking more for an event that cannot follow any probability distribution, but +1 anyway; this answer is useful. – Mehrdad Nov 10 '11 at 18:57