7.2 Probability theory Flashcards
Let S be the sample space of an experiment with a finite or countable number of outcomes. We
assign a probability p(s) to each outcome s. We require that two conditions be met:
(i) 0 ≤ p(s) ≤ 1 for each s ∈ S
(ii) ∑ p(s) = 1.
s∈S
What if the sample space is infinite?
∑ s∈S p(s) is a convergent infinite series.
Integral Calculus is used to study
Probability Distribution?
The function p from the set of all outcomes of the sample space S is called a probability
distribution.
what is p? (I know)
probability distribution is the mathematical function that gives the probabilities of occurrence of different possible outcomes for an experiment.
Unifrom distribution
probability assignment
Suppose that S is a set with n elements. The uniform distribution assigns the probability 1∕n
to each element of S.
The probability of the event E :
Definition 2 using definition 1 :
The probability of the event E is the sum of the probabilities of the outcomes in E. That is,
p(E) = ∑ p(s).
s∈E
(Note that when E is an infinite set, ∑
s∈E p(s) is a convergent infinite series.)
selecting an element of S at
random.:
The experiment of selecting an
an element from a sample space with a uniform distribution is called selecting an element of S at
random.
Probabilities of Complement and Union :
It stays valid, think in terms of Def 2 of sec 7.2.
If E1, E2, … is a sequence of pairwise disjoint events in a sample space S, then
p(⋃ Ei) is?
i
If E1, E2, … is a sequence of pairwise disjoint events in a sample space S, then
p(⋃ Ei) = ∑i p(Ei).
i
(Note that this theorem applies when the sequence E1, E2, … consists of a finite number or a
countably infinite number of pairwise disjoint events.)
Conditional Probability:
Let E and F be events with p(F) > 0. The conditional probability of E given F, denoted by
p(E ∣ F), is defined as
p(E ∣ F) = p(E ∩ F) / p(F) .
Independent Events:
The events E and F are independent if and only if
p(E ∩ F) = p(E)p(F).
When
two events are independent, the occurrence of one of the events gives no information about the
probability that the other event occurs.
Types of Independences:
The events E1, E2, … , En are pairwise independent if and only if p(Ei ∩ Ej) =p(Ei)p(Ej) for all pairs of integers i and j with 1 ≤ i < j ≤ n.
These events are
mutually independent if p(Ei1 ∩ Ei2 ∩ ⋯ ∩ Eim ) = p(Ei1)p(Ei2) ⋯ p(Eim ) whenever
in , j = 1, 2, … , m, are integers with 1 ≤ i1 < i2 < ⋯ < im ≤ n and m ≥ 2.
Bernoulli trial :
Each performance of an experiment with two possible outcomes is
called a Bernoulli trial, after James Bernoulli, who made important contributions to probability
theory. In general, a possible outcome of a Bernoulli trial is called a success or a failure.
If p
is the probability of a success and q is the probability of a failure, it follows that p + q = 1.
The probability of exactly k successes in n independent Bernoulli trials
THEOREM:
prove it too.
The probability of exactly k successes in n independent Bernoulli trials, with probability of
success p and probability of failure q = 1 − p, is
C(n, k)p^(k q)^(n−k).
Considered as a function of k, we
call this function the binomial distribution.
b(k; n, p) = C(n, k)pkqn−k.
e sum of the probabilities that there are k successes when n independent Bernoulli
trials are carried out, for k = 0, 1, 2, … , n, equals?
b(k; n, p) = (p + q)^n = 1
Random Variable :
A random variable is a function from the sample space of an experiment to the set of real
numbers. That is, a random variable assigns a real number to each possible outcome.
Remark: Note that a random variable is a function. It is not a variable, and it is not random!
The distribution of a random variable X on a sample space S is?
Definition 7:
The distribution of a random variable X on a sample space S is the set of pairs (r, p(X = r))
for all r ∈ X(S), where p(X = r) is the probability that X takes the value r. (The set of pairs
in this distribution is determined by the probabilities p(X = r) for r ∈ X(S).)
The Birthday problem?
solve it too
What is the minimum number of people who need to be in a room so that the probability that at least two of them have the same birthday is greater than 1∕2?
Probability of a collision in hashing function
solve it. page 487
Deterministic algorithms:
These proceed in same way whenever given the same input.
Probabilistic Algorithms:
why use them?
These make random choices at one or more steps.
Need: when deterministic algo has huge number (or unknown number) of possible cases.
Monte Carlo Algorithms :
A class of probabilistic algorithms, for decision problems.
Gives answers, but small probability remains that these might be incorrect, however this probability decreases with more tests.
At each step possible response are true or unknown.
True : no more iterations required, and is true.
Unknown: Ans could be true or false.
ans is false if every iteration yields unknown.
If correct answer is false then algorithm will produce unknown for all iterations.
If correct answer is true, then it will yield true or unknown.
Monte carlo
probability of incorrect answer?
if the correct answer is
“true,” then the algorithm could answer either “true” or “false,” because it may be possible that
each iteration produced the response “unknown”.
We will show that this possibility becomes extremely unlikely as the number of tests increases.
Suppose that p is the probability that the response of a test is “true,” given that the answer
is “true.” It follows that 1−p is the probability that the response is “unknown,” given that the
answer is “true.” Because the algorithm answers “false” when all n iterations yield the answer
“unknown” and the iterations perform independent tests, the probability of error is (1−p)^n.
When p ≠ 0, this probability approaches 0 as the number of tests increases.
Consequently, the probability that the algorithm answers “true” when the answer is “true” approaches 1.
Probabilistic Primality testing
Read it.
the probabilistic method:
THE PROBABILISTIC METHOD If the probability that an element chosen at random
from a S does not have a particular property is less than 1, there exists an element in S with
this property
TH 4
after revising chapter 4
