# 10 - Randomization and probability

## Anonymous broadcasting

Scenario:

Three friends go on a trip, they bring a bottle of whisky. All three friends go an do their own thing and upon returning realize that someone drank the whisky. It could be a sinister person on the island, or it could be one of the friends. No one wants to outright admit that they stole the whisky

Anonymous broadcasting makes use of the XOR operator

- Say we have three friends $P_1, P_2$ and $P_3$.
- Each $P_i$ picks a random bit $b_i$
- Each $P_i$ whispers $b_i$ to $P_{i+1 \mod 3}$
- Each $P_i$ computes $t_i = b_{i - 1 \mod 3} \oplus b_i$
- 
- Each $P_i$ announces the value of $\tilde{t_i}$
- Each $P_i$ computes $\tilde{t_1} \oplus \tilde{t_2} \oplus \tilde{t_3}$
- $\tilde{t_1} \oplus \tilde{t_2} \oplus \tilde{t_3} = b_3 \oplus b_1 \oplus b_1 \oplus b_2 \oplus b_2 \oplus b_3$
- It should be noted that XORing a value with itself results in 0.
- So if no one drank the whisky, each $b_i$ should cancel it self and the result should be 0
- If someone did drink the whisky, then there would be a 1

Let's convince ourselves that this is truly anonymous

$P_1$ knows: $b_1, b_3, \tilde{t_1}, \tilde{t_2}, \tilde{t_3}$
but not $b_2$

$\tilde{t_3} = b_2 \oplus b_3 \oplus 1$ (if $P_3$ drank the whisky)
$\tilde{t_2} = b_1 \oplus b_2 \oplus 1$ (if $P_2$ drank the whisky)

Another way to think about this, since both cases are mutually excusive is

$\tilde{t_3} = b_2 \oplus b_3 \oplus X$ (For some $X \in [0,1]$)
$\tilde{t_2} = b_1 \oplus b_2 \oplus (1-X)$ (For some $X \in [0,1]$)

But $P_1$ doesn't know $X$ nor $b_2$. Because of this, $P_1$'s probability of determining who drank the whisky is no better than 50%

## Definitions
**Sample space:** Non-empty coutable set $S$
- Elements of $S$ are called *outcomes*
- Subsets of $S$ are called *events*

**Probability function on $S$**: $Pr : S \rightarrow [0,1] \text{ such that } \sum_{w\in S}Pr(w) = 1$

The sum of all possibilities is equal to 1 or 100%

**Probability space:** $(S, Pr)$ where $S$ is a sample sapce and $Pr$ is a probability function on $S$

All probabilities are betwen 0 and 1

Ex: Tossing a coin
$S = \{H, T\}, Pr(H) = Pr(T) = 0.5$

Ex: Toss two coins:
$S = \{HH, HT, TH, TT\}, Pr(HH) = Pr(HT) = Pr(TH) = Pr(TT) = 0.25$

Ex: Roll a 6-sided die
$S = \{1,2,3,4,5,6\}, Pr(1) = Pr(2) = Pr(3) = Pr(4) = Pr(5) = Pr(6) = \frac{1}{6}$

Ex: Roll two 6-sided die, one red and one blue
$S = \{(i,j) \text{ where } i,j \in \{1,2,3,4,5,6\}\}$, $|S| = 36$,
$Pr(i,j) = \frac{1}{36} \text{ for each } (i,j) \in \{1,2,3,4,5,6\}$

Building off the last example, we define an event for any $k \in \{2,...,12\}$
$A_k = \text{"The sum of the two dice is equal to k"}$
$A_4 = \{(1,3), (2,2), (3,1)\}$
$Pr(A_4) = Pr(1,3) + Pr(2,2) + Pr(3,1) = \frac{3}{36} = \frac{1}{12}$

For all others values of $k$, we draw a table


## Sum rule for probabilties

If $A$ and $B$ are disjoint (no elements in common) then
$Pr(A \cup B) = \sum_{\omega \in A \cup B} Pr(\omega) = \sum_{\omega \in A} Pr(\omega) + \sum_{\omega \in B} Pr(\omega) = Pr(A) + Pr(B)$

If $A_1, ..., A_n$ are pairwise disjoint then
$Pr(A_1 \cup ... \cup A_n) = Pr(A_1) + ... + Pr(A_n)$

Ex: What is the probability that the sum of two dice is even?
$Pr(A_2 \cup A_4 \cup A_6 \cup A_8 \cup A_{10} \cup A_{12} \cup) = Pr(A_2) + Pr(A_4) + Pr(A_6) + Pr(A_8) + Pr(A_{10}) + Pr(A_{12})$
$= \frac{1}{36} + \frac{3}{36} + \frac{5}{36} + \frac{5}{36} + \frac{3}{36} + \frac{1}{36} = \frac{18}{36} = \frac{1}{2}$

---
Another way of solving

$i + j$ is even if and only iff $i$ and $j$ are both even or $i$ and $j$ are both odd.

Define the event $A$ to be the event where $i$ and $j$ are both even
Define the event $B$ to be the event where $i$ and $j$ are both odd.

These two events are disjoint

$Pr(i + j \text{ is even}) = Pr(A \cup B) = Pr(A) + Pr(B) = \frac{|A|}{36} + \frac{|B|}{36} = \frac{9}{36} + \frac{9}{36} = \frac{18}{36} = \frac{1}{2}$

$A = \{i, j : i,j \in \{2,4,6\}\}, |A| = 3\times 3 = 9$
$B = \{i, j : i,j \in \{1,3,5\}\}, |B| = 3\times 3 = 9$

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