7.2 Probability theory

Question 1

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:

Answer 1

(i) 0 ≤ p(s) ≤ 1 for each s ∈ S

(ii) ∑ p(s) = 1.
s∈S

Question 2

What if the sample space is infinite?

Answer 2

∑ s∈S p(s) is a convergent infinite series.

Integral Calculus is used to study

Question 3

Probability Distribution?

Answer 3

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.

Question 4

Unifrom distribution

probability assignment

Answer 4

Suppose that S is a set with n elements. The uniform distribution assigns the probability 1∕n
to each element of S.

Question 5

The probability of the event E :

Definition 2 using definition 1 :

Answer 5

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.)

Question 6

selecting an element of S at

random.:

Answer 6

The experiment of selecting an
an element from a sample space with a uniform distribution is called selecting an element of S at
random.

Question 7

Probabilities of Complement and Union :

Answer 7

It stays valid, think in terms of Def 2 of sec 7.2.

Question 8

If E1, E2, … is a sequence of pairwise disjoint events in a sample space S, then

p(⋃ Ei) is?
i

Answer 8

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.)

Question 9

Conditional Probability:

Answer 9

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) .

Question 10

Independent Events:

Answer 10

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.

Question 11

Types of Independences:

Answer 11

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.

Question 12

Bernoulli trial :

Answer 12

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.

Question 13

The probability of exactly k successes in n independent Bernoulli trials

THEOREM:

prove it too.

Answer 13

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.

Question 14

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?

Answer 14

b(k; n, p) = (p + q)^n = 1

Question 15

Random Variable :

Answer 15

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!

Question 16

The distribution of a random variable X on a sample space S is?

Definition 7:

Answer 16

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).)

Question 17

The Birthday problem?

solve it too

Answer 17

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?

Question 18

Probability of a collision in hashing function

Answer 18

solve it. page 487

Question 19

Deterministic algorithms:

Answer 19

These proceed in same way whenever given the same input.

Question 20

Probabilistic Algorithms:

why use them?

Answer 20

These make random choices at one or more steps.

Need: when deterministic algo has huge number (or unknown number) of possible cases.

Question 21

Monte Carlo Algorithms :

Answer 21

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.

Question 22

Monte carlo

probability of incorrect answer?

Answer 22

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.

Question 23

Probabilistic Primality testing

Answer 23

Read it.

Question 24

the probabilistic method:

Answer 24

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

Question 25

TH 4

Answer 25

after revising chapter 4