Introduction to and Discrete summary.ppt

discrete probability introduction

1. Summary 3
•Discrete Probability (sections 5.1 - 5.2)
–Experiments, outcomes, and sample space
•Use counting techniques to determine sample space
•p(s) for each sS
–0  p(s)  1 for each sS

sS p(s) = 1
–If all outcome are equally probable, then p(s) = 1/|S|
–Events and event probability
•E  S, P(E) = |E|/|S| or P(E) = 
sE
p(s)
•Use counting techniques to determine samples in E
•Complementary event: P(E) = 1 – P(-E).

2. –Conditional probability P(E|F)
•Definition: probability of E, given F (or in subspace F S)
•Relation to joint probability
–P(E|F) = P(EF)/P(F) or P(E|F) = |EF|/|F|
–P(EF) = P(E|F)P(F) = P(F|E)P(E)
–Inclusion-exclusion rule:
P(EF) = P(E) + P(F) – P(EF)
–Independence
•Events E and F are independent of each other if
P(E|F) = P(E) (E’s probability not depending on F)
•P(EF) = P(E) + P(F) –P(E)P(F)

3. –Bernoulli Trials
•Experiment with two outcomes, s and f,
•p = P(s), q = P(f) = 1– p (therefore p + q = 1)
•n independent trials with k s (and n – k f)
C(n, k)p
k
q
n-k

4. •Relations (sections 7.1 – 7.5)
–Definitions.
•(Binary) relation R from A to B: R  AB: ordered pairs
•Relation R on A: R  AA
•n-ary relation R  A
1A
2…A
n
•Functions are special cases of relations.
–Properties of relations
•Reflexive/irreflexive
•Symmetric/asymmetric/antisymmetric
•Transitive
•Properties reflected in graph and matrix representations
–Combining relations: R
1
 R
2
, R
1
 R
2
, R
1
– R
2
, SR.

5. –Equivalence relations
•Definition: reflexive, symmetric and transitive.
•Equivalence class: [a]
R
–For all b, if bRa, then b  [a]
R
–aRb

iff

[a] = [b] iff [a]  [b]  
–not aRb

iff

[a]  [b] iff [a]  [b] = 
•Partition of a set:
(i) A
i
  for iI
(ii) A
i  A
j = , if i  j
(iii) 
iI A
i = S
•All equivalence classes of R on A partition A.

6. –Representing relations
•Set of ordered pairs:
–{(a, b)| aRb for all (a, b)  AB}
•0 – 1 matrix
–m
ij
= 1, if (a
i
, b
j
)R, and
–m
ij = 0, if (a
i, b
j)R.
•Directed graph: (V, E)
–V = A  B ( or V = A if R is on A)
–(a, b) E iff (a, b) R
•Be able to convert between the three representations

7. •Graphs (sections 8.1 – 8.4)
–Definitions.
•Simple, undirected and directed graphs.
•Degree (indegree, outdegree) of vertex
•Loop, isolated and pendant vertices
•Special graphs
Complete, cycle, bipartite, and complete bipartite, n-cube
•Subgraph
–Adjacency
•For undirected graphs:
vV deg(v) = 2|E|
•For directed graphs: 
vV deg
-
(v) = 
vV deg
+
(v) = |E|

8. –Representing graphs
•Adjacency matrix
–a
ij
= 1 if {v
i
, v
j
} is an edge of G; and
–a
ij
= 0 otherwise.
–Connectivity
•Path, path length, simple path, circuit
•A (undirected) graph is connected if there is a path
between any pair of vertices
•Strong and weak connected directed graphs
•Connected components of a graph

9. Types of Questions
•Conceptual
–Definitions of terms
–True/false
–Simple questions
•Problem solving
–Work with small concrete example problems
•Proofs
–Simple theorems or propositions
–Possible proof methods
•Induction
•Directed proof
•Proof by contradiction