Discrete Three terms

Sample space

a pair (S,P), where S is finite, nonempty set, and P: S→ R is a function that: P(s) > 0 for all elements in set S.

Modeling

converting a real-world problem in a mathematical framework. Uncertainty can be modeled with sample space, which makes probabilities, which makes predictions!

If S is a finite set of outcomes the uniform probability on S is the function:

P(s) = 1/ the cardinality of s for all s

Event

An event A is a subset of S, the probability of an event A is P(A)= the sum of all P(a).

If(s,p)

the elements of S are called outcomes, the subsets of S are called events, events and outcomes have probability which is a real number, possibility is undefined, do not use it.

A with an arrow on top of it

S-A (set complement) is the event that A does not occur.

Function

a relation f is called a function provided if (a,b) is an element of f and (a,c) is also an element of f, then b = c. Contrapositively, if b does not equal c than (a,b) and (a,c) are not an element of f or a function can not have two output values for one input value.

Function Notation

Let f be a function and let a be an object. The notation f(a) is defined

provided there exists an object b such that (a,b) is an element of f . In this case, f(a)equals b. Otherwise[there is no ordered pair of the form (a,_) in an element of f ], the notation f(a) is undefined. The symbols f(a) are pronounced “f of a.”

(Domain, Image)

Let f be a function. The set of all possible first elements of the ordered pairs in f is called domain and it is denoted as domain of f. The set of all possible second elements of an ordered pairs in f is called an image and is denoted as im f.

(f:A→ B)

Let f be a function and A and B be sets. We say that a function is A to B provided that dom f = A and im f is a subset of B.

Example: Sine function, the domain is all real numbers but the image is -1 <x< 1. We can write sine as function from all real numbers to all real numbers because the domain is all real numbers and the image is a subset of all real numbers. In set builder notation: {x is an element of R: -1<x<1}

To show f: A → B

To prove that f is a function from A to B. First, prove that f is a function, prove that dom f = A, and prove that im f is a subset of B.

The number of functions from A to B

Let A and B be finite sets with |A| = a and |B| = b. The number of functions from a to b is b^a

One-to-one or Injective

a function is one-to-one provided that wherever (x,b), (y,b) in f we must have x = y. In other words if x does not equal y than f(x) does not equal f(y). Alternatively, two inputs can not lead to the same output. I.e. the x² function is not one to one for all real numebrs.

The inverse relation of a function f is…

a function iff f is originally one to one

Prop 24. 15

Let both f and its inverse be function. Then the dom f = im f^-1, and im f = dom f^-1

Onto/Surjective

Let f: A → B, we say that if f is onto B provided that for every b in B there is an a in A so that f(a)=b. In other words, im f = B. Alternatively, every function in the codomain is mapped to a function in the domain.

Bijection

Let f: A→ B. We call f is a bijection provided it is both one to one and onto

Pigeonhole Principle

Let A and B be finite sets and let f: A → B. If |A|> |B|, then if f is not one to one.

Let A and B be finite sets with |A| = a and |B|=b

The number from functions from A to B is b^a. 2. if a < b, the number of one to one functions f: A→ B is b falling factorial a, 3. a >b the number of onto functions f: A→ B is (-1)^j(b choose j) (b-j)^a, If a = b the number of bijections f: A→ B is a! if a does not equal b the number of such functions is 0.

Composition of Function

Let A, B, and C be sets, where f: A→ B and g: B→ C, The the function g circle f is a function from A → C and g circle f (a) = g[f(a)] where a is a component of A.

Proving two functions are equal

Prove that dom f = dom g, Prove that for every x in their common domain f(x)=g(x)

Identity Function

The identity function on A is the function idA whose domain is A and for all a in A, idA(a)= (a,a)

Expectation

If X is a real valued random variable defined on the sample space (S,P) the expected value is the sum of all X(s)P(s)

Prop 34.4

E(X) = the sum of all a P(X=a) where a is a real number

Prop 34.7

Suppose X and Y are real variables defined in a sample space (S,P). Then E(X+Y) = E(X)+E(Y)

Linearity of Expectation

E(aX+bY) = aE(x) + bE(y)

Prop 34.9

E(cX) = cE(x)

Let X be a 0 to 1 random variable. Then E(x) = P(x=1)

Th 34.14

E(XY)= E(X)E(Y)

Variance

Var(x) = E [(X- E(X))]² or alternatively Var(x) = E[x²}-E[x²]

Markov Chain

an experiment with finitely many states with conditional probabilities of transition from one state to the others. Gives rise to a transition matrix which is an n x n matrix of nonnegative entries whose columns add up to one

A pair of tetrahedral dice are rolled. let X be the sum of the two numbers and Y their product. E(X) and E(Y)

1. Make a table of the values