8 pt 2

CP214: Discrete Structures

Chapter 7: Discrete Probability

Instructor: Dr. Shimaa Abdelmeguid

Outline of Topics

• Probability Theory

  • Independence

  • Bernoulli Trials

  • Random Variables

  • Expected Values

Probability Theory

Independence

• Definition:

  • The events E and F are independent if and only if the following equation holds:
    $p(E \cap F) = p(E) \cdot p(F)$

  • Furthermore, the conditional probability of E given F is defined as:
    $p(E | F) = \frac{p(E \cap F)}{p(F)} = p(E)$

  • Symmetrical property: If $p(E \cap F) = p(E) \cdot p(F)$, then $p(F | E) = p(F)$ as well.

Independence Examples

Example 1: Rolling Dice

• Let E be the event of rolling an even number with an unbiased die, while F is the event that the resulting number is divisible by three.

• Events defined as:

  • E = {2, 4, 6}

  • F = {3, 6}

  • $E \cap F = {6}$

• Calculate probabilities:

  • $p(E) = \frac{3}{6} = \frac{1}{2}$

  • $p(F) = \frac{2}{6} = \frac{1}{3}$

  • $p(E \cap F) = \frac{1}{6}$

• Verification:

  • $p(E \cap F) = p(E) \cdot p(F)$:

  • $\frac{1}{6} = \frac{1}{2} \cdot \frac{1}{3}$

• Conclusion: E and F are independent.

Example 2: Bit Strings

• Let E be the event where a random bit string of length four begins with a 1. Let F be the event the bit string contains an even number of 1s.

• Possible bit strings starting with 1:

  • {1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111}

• Possible bit strings with an even number of 1s:

  • {0000, 0011, 0101, 0110, 1001, 1010, 1100, 1111}

• Calculate probabilities:

  • Total strings = 16

  • $p(E) = p(F) = \frac{8}{16} = \frac{1}{2}$

  • $E \cap F = {1111, 1100, 1010, 1001}$

  • $p(E \cap F) = \frac{4}{16} = \frac{1}{4}$

• Verification:

  • $p(E \cap F) = 1/4 = (1/2)(1/2) = p(E) \cdot p(F)$

• Conclusion: E and F are independent.

Example 3: Family Children

• For a family with two children, let E be the event of having two boys (BB) and F be the event of having at least one boy (BB, BG, GB).

  • E = {BB}, p(E) = 1/4

  • F = {BB, BG, GB}, p(F) = 3/4

  • $E \cap F = {BB}, p(E \cap F) = 1/4$

• Independence check:

  • $p(E) \cdot p(F) = (1/4)(3/4) = 3/16$

• Conclusion: E and F are not independent since $1/4 <br>eq 3/16$.

Bernoulli Trials

Definition and Concepts

• A Bernoulli trial is defined as a random experiment with two possible outcomes, commonly referred to as a success (S) or failure (F).

• Let p be the probability of success, and q = 1 - p be the probability of failure.

• The relationship between probabilities dictates:

  • $p + q = 1$

• When conducting n independent Bernoulli trials, the probability of achieving exactly k successes is given by the formula:

  • $P(X = k) = C(n, k) p^k q^{n-k}$
    where C(n, k) represents the binomial coefficient, the number of ways to choose k successes from n trials.

Bernoulli Trials: Example and Calculation

Probability Calculation

• Consider the probability of obtaining two successes in five Bernoulli trials.

• Let’s denote:

  • Successful outcomes: S

  • Failing outcomes: F

• Example sequence: SSFFF

• Probability calculation for this specific sequence:

  • $p^2 q^3$

• Another possible sequence: FSFSF with the same logic leads to the same probability which is $p^2 q^3$.

• Total number of possible sequences with k successes in n trials is determined by the binomial coefficient C(n, k).

Example of a Coin Toss

• For a biased coin where the probability of heads (success) is 2/3, let's calculate the probability of exactly four heads in seven tosses.

• Total ways to get four heads among seven tosses is given by the binomial coefficient:

  • $C(7, 4)$

• The probability of each combination is:

  • $(\frac{2}{3})^4 (\frac{1}{3})^3$

• Therefore, the total probability is given by the product:

  • $P(X = 4) = C(7, 4) \left(\frac{2}{3}\right)^4 \left(\frac{1}{3}\right)^3 = \frac{560}{2187} \approx 0.2561$

Random Variables

Definition

• A random variable is defined as a function that maps outcomes from the sample space of an experiment to real numbers.

• It quantifies the outcomes for mathematical analysis.

Distribution of Random Variables

• Definition: The distribution of a random variable X over sample space S consists of pairs denoted as ${(r, P(X = r)) | r \in X(S)}$ where P(X = r) signifies the probability that X takes the value r.

Example of a Random Variable

• Illustrative example: Flipping a coin three times, let X(s) represent the number of heads.

• Outcomes defined:

  • X(HHH) = 3,

  • X(TTT) = 0,

  • X(HHT) = X(HTH) = X(THH) = 2,

  • X(TTH) = X(THT) = X(HTT) = 1.

Expected Values

Definition

• The expected value of a random variable is a statistical measure that provides a weighted average of the possible outcomes when an experiment is repeated many times.

• Each outcome contributes to the average based on its probability.

Calculation of Expected Values

• For a random variable with outcomes 1 and 2, where 1 occurs with P = 0.1 and 2 occurs with P = 0.9, the traditional arithmetic average is not sufficient as it neglects the probabilities.

• True average value is computed as a weighted sum:

  • $E(X) = 0.1 imes 1 + 0.9 imes 2 = 0.1 + 1.8 = 1.9$

• The generalized formula for the expected value is:

  • $E(X) = \sum_{s \in S} P(s) X(s)$

Examples of Expected Values

Example I: Coin Flips

• Flipping a fair coin three times:

• Sample space S contains 8 outcomes. The expected value of the random variable X, which counts how many heads appear, is calculated as:

  • $E(X) = \frac{1}{8} [X(HHH) + X(HHT) + X(HTH) + X(THH) + X(TTH) + X(THT) + X(HTT) + X(TTT)]$

  • After computation:

  • $E(X) = 1.5$

Example II: Fair Die

• Random variable X defines the outcome on a fair die. Each face shows values 1-6 with equal probabilities of $\frac{1}{6}$.

• Expected value calculated as:

  • $E(X) = \frac{1}{6} \cdot [1 + 2 + 3 + 4 + 5 + 6] = \frac{21}{6} = \frac{7}{2}$

Example III: Sum of Dice

• Random variable X denotes the sum of numbers when rolling two dice. The sample size yields 36 outcomes.

• Distribution analysis shows that while outcomes are equally likely, the values of X do not share equal probabilities.

• Probabilities of outcomes for specific X values:

  • $P(X = 2) = \frac{1}{36}$

  • $P(X = 3) = \frac{2}{36} = \frac{1}{18}$

  • $P(X = 4) = \frac{3}{36} = \frac{1}{12}$

  • $P(X = 5) = \frac{4}{36} = \frac{1}{9}$

  • $P(X = 6) = \frac{5}{36}$

  • $P(X = 7) = \frac{6}{36} = \frac{1}{6}$

  • $P(X = 8) = \frac{5}{36}$

  • $P(X = 9) = \frac{4}{36} = \frac{1}{9}$

  • $P(X = 10) = \frac{3}{36} = \frac{1}{12}$

  • $P(X = 11) = \frac{2}{36} = \frac{1}{18}$

  • $P(X = 12) = \frac{1}{36}$

• Expected value is calculated as:

  • $E(X) = 2 \cdot (\frac{1}{36}) + 3 \cdot (\frac{1}{18}) + 4 \cdot (\frac{1}{12}) + 5 \cdot (\frac{1}{9}) + 6 \cdot (\frac{5}{36}) + 7 \cdot (\frac{1}{6}) + 8 \cdot (\frac{5}{36}) + 9 \cdot (\frac{1}{9}) + 10 \cdot (\frac{1}{12}) + 11 \cdot (\frac{1}{18}) + 12 \cdot (\frac{1}{36}) = 7$

• Interpretation: Averaging repeated rolls yields an average sum of 7.

Theorem Relating to Expected Values

• Theorem:

  • If X and Y are random variables on a sample space S, and a and b are real constants:

  • $E(X + Y) = E(X) + E(Y)$

  • $E(aX + b) = aE(X) + b$

• Following this theorem, the expected value of a sum of two dice can be simplified using their individual expected values:

  • For two independent random variables X₁ and X₂ representing two dice, we find that:

  • $E(X₁) = E(X₂) = \frac{7}{2}$

  • Thus, $E(X₁ + X₂) = E(X₁) + E(X₂) = 7$

Summary of Key Topics

• Discussed concepts include:

  • Discrete Probability

  • Conditional Probability

  • Bernoulli Trials

  • Random Variables

  • Expected Values

End of Notes