> For the complete documentation index, see [llms.txt](https://shai-deshe.gitbook.io/understanding-blockdags-and-ghostdag/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://shai-deshe.gitbook.io/understanding-blockdags-and-ghostdag/supplementary-material/math/probability-theory/probability-spaces.md).

# Probability Spaces

A *probability function* $$\mathbb{P}$$ takes an event, and tells us how likely it is as a number from $$0$$ to $$1$$. For example, if I roll a (fair) die, the event $$A$$ that it came out four has probability $$\mathbb{P}\[A] = \frac{1}{6}$$.

What is the probability that it will be *either* three *or* four? Let $$A$$ be the event that it is three, and $$B$$ the event that it is four, then the event that it is *either* is denoted $$A\cup B$$. Note that it is impossible that die is *both* three *and* four, we call such events *disjoint*. Since $$A$$ and $$B$$ are disjoint, we get that the probability *either* happens is the *sum of probabilities* they do happen. There's a one in six chance to get three, and a one in six chance to get four, hence there's a *two* in six chance to get either. Or in math:

$$
\mathbb{P}\[A\cup B] = \mathbb{P}\[A]+\mathbb{P}\[B] = \frac{1}{6} + \frac{1}{6} = \frac{1}{3}\text{.}
$$

When events are not disjoint, we *cannot* sum them up like this. For example, the probability that the result is *odd* is three in six, or one-half. The probability that the result is *at most three* is also three in six, or one-half. So the probability that the result is *either odd or at most three* is half + half = one? Of course not: there is a positive probability that we roll a four, which is *neither* odd nor smaller than three. 

when summing the two we overlook the fact that a result can be *both* odd *and* at most three, making us count these events twice. We said that *three in six* are odd and *three in six* are at most three, but three and one are *both*. We *overcounted.*

**Exercise**: Given two events $$A$$ and $$B$$, let $$A\cap B$$ be the event that they *both* happen (if they are disjoint, then $$A\cap B$$ is the *empty event* $$\emptyset$$ that satisfies $$\mathbb{P}\[\emptyset]=0$$), convince yourself that

$$
\mathbb{P}\[A\cup B] = \mathbb{P}\[A] + \mathbb{P}\[B] - \mathbb{P}\[A\cap B]\text{.}
$$

<details>

<summary>Solution</summary>

Intuitively, we have that $$A\cap B$$ is all the events that are in both $$A$$ and $$B$$, so we count them once in $$\mathbb{P}\[A]$$ and a second time in $$\mathbb{P}\[B]$$, so we have to subtract them once to balance out the double counting.

Formally, we can write $$A' = A \setminus B$$  (that is $$A'$$ is the event that $$A$$ happened and $$B$$ *didn't*), So $$A\cup B = A' \cup B$$ but $$A'$$ and $$B$$ are *disjoint*, so we have:

$$\mathbb{P}\[A\cup B] = \mathbb{P}\[A' \cup B] = \mathbb{P}\[A'] + \mathbb{P}\[B]$$

However, we also have that $$A = A' \cup (A\cap B)$$, where the union is also disjoint, so we have that $$\mathbb{P}\[A] = \mathbb{P}\[A'] + \mathbb{P}\[A\cap B]$$, or equivalently that $$\mathbb{P}\[A'] = \mathbb{P}\[A] - \mathbb{P}\[A\cap B]$$.

Substituting this into the equation above we get

$$\mathbb{P}\[A\cup B] = \mathbb{P}\[A' ]  + \mathbb{P}\[B] = \mathbb{P}\[A]  + \mathbb{P}\[B]-\mathbb{P}\[A\cap B]$$

as needed.

</details>

## Atomic Events

We say that an event $$A$$ *contains* another event $$B$$, and denote $$B\subseteq A$$, if $$A$$ is *guaranteed* to happen *given* that $$B$$ happens. For example, the event $$X=4$$ is contained in the event that $$X$$ is even. An event is called *atomic* if it has positive probability, but it does not contain any other event that has positive probability. For example, a fair die has six atomic events, for each $$n=1,\ldots,6$$ we have the atomic event $$X=n$$.

It is conventional to call the set of atomic events $$\Omega$$. For example $$\Omega = {\omega\_1,\ldots,\omega\_6}$$ describes the atomic events of *any* six-sided die. The die doesn't have to be *fair*, but it does have to satisfy that each of its six sides has *some* probability to be the result.

**Exercise**: prove that any two different atomic events are disjoint

The set $$\Omega$$ is also commonly called the "sample space", as it describes all possible results of an experiment.

## Finite and Discrete Probability Spaces

Given a set of atomic events $$\Omega$$, we can endow them with a probability function a *probability function* $$\mathbb{P}$$ that assigns to each atomic event $$\omega\in\Omega$$ a number $$0<\mathbb{P}\[\omega]\le1$$. The pair $$(\Omega,\mathbb{P})$$ is called a *discrete probability space* if the probabilities of all atomic events sum to one. In other words, if *all events* can be described as a union of atomic events.

Note that since atomic events are disjoint, the definition of $$\mathbb{P}$$ naturally extends to all events, simply as the sum of atomic events that comprise them. For example, if we $$A$$ be the event that the result is at most three, then we have

$$
\mathbb{P}\[A]=\mathbb{P}\[\omega\_{1}\cup\omega\_{2}\cup\omega\_{3}]=\mathbb{P}\[\omega\_{1}]+\mathbb{P}\[\omega\_{2}]+\mathbb{P}\[\omega\_{3}]
$$

If we want to describe a *fair die*, we will define $$\Omega = {1,\ldots,6}$$ and $$\mathbb{P}\[n] = \frac{1}{6}$$ for any $$n=1,\ldots,6$$, and we will indeed get that the probability that the die is less than three is

$$
\mathbb{P}\[A]=\mathbb{P}\[\omega\_{1}\cup\omega\_{2}\cup\omega\_{3}]=\mathbb{P}\[\omega\_{1}]+\mathbb{P}\[\omega\_{2}]+\mathbb{P}\[\omega\_{3}]=\frac{1}{6}+\frac{1}{6}+\frac{1}{6}=\frac{1}{2}
$$

With a bit of thought, one can convince herself that if $$\Omega$$ is finite then any probability space over $$\Omega$$ is discrete. However, a space can be discrete also if $$\Omega$$ is infinite. For example, lets say I flip a fair coin util it lands on head, how many flips would it take? Well, for any positive integer $$n$$ there is *some* probability that it will take $$n$$ attempts. So our sample space is has an event for *any positive natural* numbe $$\Omega = {\omega\_1,\omega\_2,\ldots}$$.

The probability that a single flip of a fair coin will land on head is $$1/2$$. For it to take *exactly* two attempts means that the first flip landed on tails and the second landed on heads, which has a probability $$1/4$$ (as it is one of four equally likely results of flipping two coins). It would take *exactly three* attempts with probability $$1/8$$ and so on. The pattern is quite obvious: the probability it would take exactly $$n$$ flips is $$\left(\frac{1}{2}\right)^n$$, which we can more comfortable write as $$2^{-n}$$.

We said that the probabilities sum to one, and indeed if we let $$A\_n$$ be the event that it took $$n$$ flips, we get that

$$
\mathbb{P}\[\omega\_1] + \mathbb{P}\[\omega\_2] + \mathbb{P}\[\omega\_3] + \ldots = \frac{1}{2} +\frac{1}{4} + \frac{1}{8} + \ldots = 1
$$

as we can easily compute with the [geometric sum formula](/understanding-blockdags-and-ghostdag/supplementary-material/math/stuff-you-should-know/geometric-sums-and-series.md).

We can now ask ourselves, say, what is the probability this would take *at most ten tries*, and compute that the result is

$$
\sum\_{i=1}^{10}2^{-n} = 1-2^{-10} = \frac{1023}{1024} \approx 99.8%
$$

**Exercise**: prove a more generalized version of the equality above, namely that the probability it would take at most $$n$$ coin flips is $$1-2^{-(n-1)}$$. Hint, recall the *finite geometric sum formula*: for any $$q$$ we have that

$$
1+q+q^2 + \ldots +  q^n = \sum\_{k=0}^n q^k = \frac{1-q^{n+1}}{1-q}
$$

<details>

<summary>Solution</summary>

Setting $$q = \frac{1}{2}$$ we have that

$$\begin{aligned}\sum\_{k=1}^{n}\frac{1}{2^{k}} & =\sum\_{k=0}^{n}\frac{1}{2^{k}}-1\  & =\frac{1-\frac{1}{2^{n+1}}}{1-\frac{1}{2}}-1\  & =2\left(1-\frac{1}{2^{n+1}}\right)-1\  & =2-2\cdot\frac{1}{2^{n+1}}-1\  & =1-\frac{1}{2^{n}} \end{aligned}$$

</details>

We can even look at *infinite* unions. For example, we can ask ourselves what is the probability that it took us an *even* number of attempts? One can compute that this comes out to

$$
\sum\_{n=1}^{\infty}\omega\_{2n}=\sum\_{n=1}^{\infty}\frac{1}{2^{2n}}=\sum\_{n=1}^{\infty}\frac{1}{4^{n}}=\frac{1}{3}
$$

**Exercise**: prove the above inequality. Hint, recall the *infinite* geometric sum formula: if $$-1\<q<1$$ then

$$
1+q+q^2 + \ldots  = \sum\_{k=0}^\infty q^k = \frac{1}{1-q}
$$

**Remark**: When is a probability space not discrete? We won't talk about them much, and *definitely* not introduce them formally, but there could be *continuous probability spaces*. For example, we can uniformly sample *real number* between $$0$$ and $$1$$. One can easily see that the probability to sample any particular number is $$0$$. Worse yet, for *any* $$0\le a\<b \le 1$$ the event "we sampled a number between $$a$$ and $$b$$" is not atomic, as it strictly contains the event "we sampled a number between $$a'$$ and $$b'$$" whenever $$a\<a'\<b'\<b$$. So such events are never atomic, and a similar approach shows that, in fact, there are *no atomic events at all* in this space. This means that our definitions are too narrow to expend to the continuous case, and while that definitely can be done, we have no reason to do so.