# 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.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://shai-deshe.gitbook.io/understanding-blockdags-and-ghostdag/supplementary-material/math/probability-theory/probability-spaces.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.