Discrete Probability Part One
----
This is the note i made to learn discrete probability crash course made by Dan Boneh.

----
U is a finite set which i this example would be U={0,1}^n

Probability Distribution
----

P over U is a function P: U -> [0,1] such that all the sum of elements probability should be equal to 1

Example

P: 00 01 10 11 

00 = 1/2 

01 = 1/8 

10 = 1/4 

11 = 1/8 

//in total it would be equal to 1.

1. Uniform Distribution
P(x) = 1/|U| (U numbers in the universe)

Example

P: 00 01 10 11 
 
 00 = 1/4 
 01 = 1/4 
 10 = 1/4 
 11 = 1/4 
    

The probability is distributed equally by the distribution.

2. Point Distribution
P(x0) = 1
inverted Ax not equal to x0 would be P(x) = 0. Means the other elements inside x which is not x0 will be assigned 0.

putting all the weight into a single point which is x0.

Example

P: 00 01 10 11 

00 = 0
01 = 0
10 = 1 //The single point that is being weighted
11 = 0

So the probability of `10` is 1 and others would be 0 in this case.

Distribution Vector
The distribution could be made into a vector representation like

(P(000),P(001),P(010),...,P(111)) which they represent a 3 bit representation this vector will be captured by a representation of 8 real number.

Events
------

- For a set A subset of a U (universe): Pr[A] = total sum of the entire weight of x in the set A.

Note: Pr[U] = 1 (unifrom distribution)

so in this case the result of Pr[A] is [0,1]

The set A is called an ** event** which is a probability of that event.

Example

U = {0,1}^8 

|U| = 256 

A = {all x in U such that lsb2 (Least significant bit) = 11} subsets of the universe 

01011010 = this is not inside the set since lsb2 = 11 

01011011 = this is inside the set since it contains 11 

for the uniform distribution on {0,1}^8: Pr[A] = 1/4 

The reason for this to be 1/4 

since we know that |U| = 256 

1/4 of 256 is 64 which ends with 11 

64 * 1/256 (1 over the universe) = 1/4

The Union Bound
----

So in a union bound means that for events A1 and A2 which is the subset of U.

Pr[A1 Union A2] =< Pr[A1] + Pr[A2]

since if Pr[A1] + Pr[A2] is being added there would be a double sum intersection from both side which would increase or equal to the probability compared when its being union bound.

even if both A1 and A2 is bieng disjoint which would look like this

n = disjoint

A1 n A2 = where their intersection is empty , in that case if we look into the sum the probability that either Pr[A1 U A2] = Pr[A1] + Pr[A2].

So remember if the both union is ever disjoint it would be equality but if no disjoint it would be Pr[A1 Union A2] =< Pr[A1] + Pr[A2].

Example

A1 = {all x in {0,1}^n s.t. lsb2(x) = 11} ; A2 = {all x in {0,1}^n s.t. msb2(x) = 11}

which here it would be joint 
lsb = least significant bit 
msb = most significant bit 

Pr[lsb2(x) = 11 or msb2(x) = 11] = Pr[A1 U A2] =< 1/4 + 1/4 = 1/2 

Random Variables
----
The definition of a random variable is X is a function X:U -> V which V is a set

Example

X:{0,1}^n -> {0,1} where the set of universe is mapped into {0,1}
X(y) = lsb(y) which {0,1} belongs to 

For the unifrom distribution on U:

Pr[X = 0] = 1/2 , Pr[X = 1] = 1/2

The question is what is the probability of X outputs 0 and the probability of X outputs 1 ? The answer would be half and half

why is that ?

U                V
lsb=0            0

lsb=1            1


Where there is a half half probability that if they were to pick a string unformly at random the probability that we choose a string that has its least significant bits of 0 would be 1/2 thats why the random variable output is 0

The Uniform Random Variables
----

Let U be some set which for example would be U = {0,1}^n

we can write this to become r(random variable) <--R-- U to denote a uniform random variable over U

so if this where to be place into a simpler perspective it would look like

for all a elements in the U (Universe) the probability of Pr[r = a] = 1/|U|

formally, r is the identity function: r(x) = x for all x element in the U (Universe)

a simple excercise given on the course is that

let r be a uniform random variables on {0,1}^2

Define the random variable X = r1 + r2

Then Pr[X=2] = ?

The hint given here is Pr[X=2] = Pr[r = 11] (1 and 1 not eleven)

The probability here would be 1/4 since there is a possibility where its 00 , 01 , 10 and 11 which if its added only 1 + 1 can become 2. and since its uniform so it would be 1/4.

Pr[X=2] = 1/4

Randomized Algorithms
----

Deterministic algorithm where if the the same inputs are given it would return the same output. Even if no matter how many times the algorithm is being run even if the inputs is the same it would output the same.

inputs = m

outputs = A(m)

Randomized Algorithm is that it would take in the similar way of a deterministic algorthm where y <--- A(m) but for randomized algorithm it would be y <--- A(m ; r) where r is an implicit argument and always random every time its being run. r <---R--- {0,1}^n.

So if this algorithm is being run it would first take in the m as input and the newly generated r and it would spit the first output. The second time it runs it would take in the newly generated r and it would spit a new different output from the first output.

Output is a random variable
y <--R-- A(m)

Example

takes in a message 'm'

and the implicit input 'k'

A(m ; k) = E(k, m) , y <--R-- A(m) (random value)