# 15 - Describing events by logical propositions and combining probability spaces

## Combining probability spaces
Example: Tossing a coin and rolling a die
$S_1 = \{H,T\} \ Pr(\omega ) = \frac{1}{2}$
$S_2 = \{1,2,3,4,5,6\} \ Pr(\omega ) = \frac{1}{6}$
$S = S_1 \times S_2 = \{H1,H2,H3,H4,H5,H6,T1,T2,T3,T4,T5,T6\}$
$Pr(\omega_1 \wedge \omega_2 )= Pr(\omega_1 ) \times Pr(\omega_2 ) = \frac{1}{2} \times \frac{1}{6} = \frac{1}{12}$

**Lemma:** Let $A_1,...,A_n$ be a sequence of mutually independent events then:
- $Pr(A_1 \cap A_2 \cap ... \cap A_n) = Pr(A_1) \times Pr(A_2) \times ... \times Pr(A_n)$
- $Pr(A_1 \cup A_2 \cup ... \cup A_n) = 1 - (1 - Pr(A_1)) \times (1-Pr(A_2)) \times ... \times (1 - Pr(A_n))$ DeMorgan's Law
- This means that at least one event occur, the opposite would be that no events occur.
- $1 - Pr(\text{None of these occur})$
- $1 - Pr(\bar{A_1} \cap \bar{A_2} \cap ... \cap \bar{A_n})$
- Previous lemma stated that if $A \cap B$ are independent then $A \cap \bar{B}$ are indepedent
- The same applies here
- $1 - ((1 - Pr(A_1)) \times (1 - Pr(A_2)) \times ... \times (1 - Pr(A_n)))$

## Sequential circuits
Imagine we're building a small computer
Sequential circuits require that each part of a circuit works. If one part fails, the whole system fails

Let $C_i = \text{The ith circuit does not work} \ Pr(C_i) = P$
$C_1,..., C_n$ are mutually independent
Let $E = \text{The whole circuit works} = \bar{C_1} \cap \bar{C_2} \cap ... \cap \bar{C_n}$
$Pr(E) = Pr(\bar{C_1} \cap \bar{C_2} \cap ... \cap \bar{C_n}) = Pr(\bar{C_1}) \times Pr(\bar{C_2}) \times ... \times Pr(\bar{C_n})$
$= (1-P)^n$

## Parallel circuits
Parallel circuits can work if a part of the circuit fails

$C_i = \text{Core i does not work}$
$C_1,...,C_n$ are independent
$E = \text{At least one of the cores works}$
$\bar{E} = \text{None of the cores work}$
$E = C_1 \cup C_2 \cup ... \cup C_n$
$\bar{E} = C_1 \cap C_2 \cap ... \cap C_n$
$Pr(E) = 1 - Pr(\bar{E})$
$Pr(E) = 1 - Pr(C_1 \cap C_2 \cap ... \cap C_n)$
$Pr(E) = 1 - Pr(C_1) \times Pr(C_2) \times ... Pr(C_n)$
$= 1 - P^n$

## Data streams
Assumption: We have access to a function `rand(k)` that returns a uniformly random integer $\in \{1,2,...,k\} \ Pr(i) = \frac{1}{k}$
- Independence: Multiple calls to `rand()` produce independent results
- Ex:
- `x = rand(10)`
- `y = rand(20)`
- $Pr(x=5, y=7) = \frac{1}{10} \times \frac{1}{20}$

Data stream: $D_1, D_2, ..., D_n$
To much data to store
Want to return one uniformly random sample $S$ $Pr(S = D_i) = \frac{1}{n}$ for each $i \in \{1,2,...,n\}$

How can we get a good sample

S = 0
1 = 1
while (there is still data):
    D = get the next data
    if (rand(i) == 1):
        S = D
    i += 1
return S

$E_i = \text{We return} \ D_i$
$A_i = S \text{ stores } D_i \text{ at some point} \ Pr(A_i) = \frac{1}{i}$
$E_n = A_n = \frac{1}{n}$

$E_i = A_i \cap \bar{A_{i+1}} \cap \bar{A_{i+2}} \cap ... \cap \bar{A_{n}}$
$Pr(E_i) = Pr(A_i \cap \bar{A_{i+1}} \cap \bar{A_{i+2}} \cap ... \cap \bar{A_{n}})$
$=Pr(A_i) \times Pr(\bar{A_{i + 1}}) \times ... \times Pr(\bar{A_n})$
$=\frac{1}{i} \times (1- \frac{1}{i+1}) \times ... (1- \frac{1}{n})$
$=\frac{1}{i} \times (\frac{i+1-1}{i+1}) \times (\frac{i+2-1}{i+2})... (\frac{n-1}{n})$
$=\frac{1}{i} \times (\frac{i}{i+1}) \times (\frac{i+1}{i+2})... (\frac{n-1}{n})$
$=\frac{1}{i} \times (\frac{i}{i+1}) \times (\frac{i+1}{i+2})... (\frac{n-1}{n}) = \frac{1}{n}$

The $i$ terms all cancel each other out.

###### tags: `COMP2804` `Probability`