By the end of this chapter, you will be able to:
Mastering these skills will help you make smart, data-driven decisions in the real world of computer science and business!
Probability theory relies on precise definitions of several fundamental terms. These include sample spaces, events, sets, and outcomes. Mastery of these concepts allows computer scientists to model and analyze random processes effectively, such as packet loss in networks or error rates in data transmission.
Sample spaces represent all possible outcomes of a random experiment, providing the universe over which probabilities are defined. In computer science, sample spaces can model everything from possible inputs to an algorithm to outcomes of randomized protocols.
The sample space is denoted by \( S \) and contains all individual outcomes \( s_i \). The probability of the entire sample space is always 1, reflecting certainty that some outcome in \( S \) will occur.
$$ P(S) = 1 $$
Example 1: A computer program generates a random integer between 1 and 5 inclusive. Find the sample space.
Given: Random integer from 1 to 5
$$ S = \{1, 2, 3, 4, 5\} $$
Answer: Sample space is {1, 2, 3, 4, 5}
Example 2: A network packet can be successfully transmitted (S) or lost (L). Define the sample space.
Given: Two possible outcomes: success or loss
$$ S = \{S, L\} $$
Answer: Sample space is {S, L}
Example 3: A hash function produces one of 8 possible hash values. List the sample space.
Given: Hash values from 1 to 8
$$ S = \{h_1, h_2, h_3, h_4, h_5, h_6, h_7, h_8\} $$
Answer: Sample space is {h_1, h_2, h_3, h_4, h_5, h_6, h_7, h_8}
Example 4: A user inputs a binary digit (0 or 1). Find the sample space.
Given: Binary digit input
$$ S = \{0, 1\} $$
Answer: Sample space is {0, 1}
Example 5: A random password generator creates a 2-character password from the set {A, B, C}. List the sample space.
Given: Password length 2, characters A, B, C
$$ S = \{ AA, AB, AC, BA, BB, BC, CA, CB, CC \} $$
Answer: Sample space has 9 elements as listed
An event is a subset of the sample space, representing one or more outcomes of interest. In computer science, events can correspond to particular system states, error occurrences, or specific outputs from an algorithm.
The probability of an event \( E \subseteq S \) is the sum of probabilities of the outcomes in \( E \).
$$ P(E) = \sum_{s_i \in E} P(s_i) $$
If outcomes are equally likely,
$$ P(E) = \frac{|E|}{|S|} $$
where \( |E| \) is the number of outcomes in the event and \( |S| \) the total number of outcomes.
Example 1: A fair 6-sided die is rolled once. Event \( E \) is rolling an even number. Compute \( P(E) \).
Given: \( S = \{1,2,3,4,5,6\} \), \( E = \{2,4,6\} \)
$$ P(E) = \frac{|E|}{|S|} = \frac{3}{6} $$
$$ P(E) = 0.5 $$
Answer: Probability of rolling even number is 0.5
Example 2: A program randomly selects a character from {A, B, C, D}. Event \( E \) is selecting a vowel. Find \( P(E) \).
Given: \( S = \{A, B, C, D\} \), vowel \( E = \{A\} \)
$$ P(E) = \frac{1}{4} = 0.25 $$
Answer: Probability of vowel is 0.25
Example 3: A packet transmission either succeeds (S) or fails (F). Event \( E \) is failure. Given \( P(S) = 0.9 \), find \( P(E) \).
Given: \( P(S) = 0.9 \), \( E = \{F\} \)
$$ P(E) = 1 - P(S) = 1 - 0.9 = 0.1 $$
Answer: Probability of failure is 0.1
Example 4: An algorithm outputs one of 5 possible results with equal probability. Event \( E \) is outputting either result 1 or 3.
Given: \( |S|=5 \), \( E = \{1,3\} \)
$$ P(E) = \frac{2}{5} = 0.4 $$
Answer: Probability of event \( E \) is 0.4
Example 5: A random bit string of length 3 is generated. Event \( E \) is the string contains exactly two 1's. Find \( P(E) \).
Given: \( |S| = 2^3 = 8 \), \( E = \{110,101,011\} \)
$$ P(E) = \frac{3}{8} = 0.375 $$
Answer: Probability of exactly two 1's is 0.375
Sets are fundamental collections of elements used to model sample spaces and events. In probability, set operations such as union, intersection, and complement describe combined or mutually exclusive events.
Key set operations in probability:
Probability of union for mutually exclusive events:
$$ P(A \cup B) = P(A) + P(B) $$
For general events:
$$ P(A \cup B) = P(A) + P(B) - P(A \cap B) $$
Complement rule:
$$ P(A^c) = 1 - P(A) $$
Example 1: A program randomly picks a digit from 1 to 5. Define events \( A = \{1,2\} \), \( B = \{2,3\} \). Find \( P(A \cup B) \), assuming equal likelihood.
Given: \( |S|=5 \), \( |A|=2 \), \( |B|=2 \), \( |A \cap B|=1 \)
$$ P(A) = \frac{2}{5}, \quad P(B) = \frac{2}{5}, \quad P(A \cap B) = \frac{1}{5} $$
$$ P(A \cup B) = \frac{2}{5} + \frac{2}{5} - \frac{1}{5} = \frac{3}{5} = 0.6 $$
Answer: Probability of \( A \cup B \) is 0.6
Example 2: Event \( C \) is a successful transmission with \( P(C) = 0.85 \). Find \( P(C^c) \).
Given: \( P(C) = 0.85 \)
$$ P(C^c) = 1 - 0.85 = 0.15 $$
Answer: Probability of failure (complement) is 0.15
Example 3: An algorithm outputs numbers 1 to 4 equally likely. Let \( D = \{1,3\} \), \( E = \{3,4\} \). Find \( P(D \cap E) \).
Given: \( |S|=4 \), \( D = \{1,3\} \), \( E = \{3,4\} \)
$$ P(D \cap E) = P(\{3\}) = \frac{1}{4} = 0.25 $$
Answer: Probability of intersection is 0.25
Example 4: Let \( F = \{2,4,6\} \) from \( S = \{1,2,3,4,5,6\} \). Find \( P(F^c) \).
Given: \( |S|=6 \), \( |F|=3 \)
$$ P(F) = \frac{3}{6} = 0.5 $$
$$ P(F^c) = 1 - 0.5 = 0.5 $$
Answer: Probability of complement is 0.5
Example 5: Events \( G = \{a,b\} \), \( H = \{b,c\} \) have probabilities \( P(G) = 0.3 \), \( P(H) = 0.4 \), \( P(G \cap H) = 0.1 \). Find \( P(G \cup H) \).
Given: \( P(G)=0.3 \), \( P(H)=0.4 \), \( P(G \cap H)=0.1 \)
$$ P(G \cup H) = 0.3 + 0.4 - 0.1 = 0.6 $$
Answer: Probability of union is 0.6
Outcomes are individual possible results of an experiment or random process. Each outcome in the sample space has an associated probability, and the collection of all outcomes defines the complete range of possibilities.
In computer science, outcomes might be specific bits received, algorithm outputs, or system states after an event.
The probability of an outcome \( s_i \) is \( P(s_i) \), satisfying:
$$ 0 \le P(s_i) \le 1, \quad \sum_{i} P(s_i) = 1 $$
Example 1: A fair coin toss has outcomes Heads (H) and Tails (T). Find \( P(H) \) and \( P(T) \).
Given: Two equally likely outcomes
$$ P(H) = P(T) = \frac{1}{2} = 0.5 $$
Answer: Each outcome probability is 0.5
Example 2: A biased coin has \( P(H) = 0.7 \). Find \( P(T) \).
Given: \( P(H) = 0.7 \)
$$ P(T) = 1 - 0.7 = 0.3 $$
Answer: Probability of Tails is 0.3
Example 3: A computer program randomly selects a number from 1 to 4. Outcome 3 has probability 0.1; remaining outcomes share equally the rest. Find \( P(1) \).
Given: \( P(3) = 0.1 \), total outcomes = 4
Remaining probability = \( 1 - 0.1 = 0.9 \)
Number of remaining outcomes = 3
$$ P(1) = \frac{0.9}{3} = 0.3 $$
Answer: Probability of outcome 1 is 0.3
Example 4: A network packet can be lost with probability 0.02 or received correctly with probability 0.98. Find \( P(\text{lost}) \).
Given: Probability lost = 0.02
Answer: Probability of lost outcome is 0.02
Example 5: A software test randomly selects one of 5 test cases with probabilities \(0.1, 0.2, 0.25, 0.15, 0.3\). Verify that these are valid probabilities.
Given: Sum = \(0.1 + 0.2 + 0.25 + 0.15 + 0.3 = 1.0\)
All probabilities between 0 and 1.
Answer: Probabilities are valid outcomes
A random bit string of length 4 is generated. List the sample space and find the total number of outcomes. (3 marks)
A computer randomly selects a number from 1 to 10. Event \( E \) is the number is divisible by 3. Calculate \( P(E) \). (4 marks)
In a network, the probability that a packet is lost is 0.05. What is the probability that the packet is received successfully? (3 marks)
Let \( A = \{1,2,3\} \) and \( B = \{3,4,5\} \) be events in a sample space of size 6 with equally likely outcomes. Find \( P(A \cup B) \) and \( P(A \cap B) \). (5 marks)
A random password consists of 3 characters chosen from {A, B, C}. How many outcomes are in the sample space? If event \( E \) is that the password contains exactly one B, find \( P(E) \). (5 marks)
Create a free account to open more of this chapter.
Free: practical guides, quick cards, workplace scenarios and more.
Create a free accountThis chapter introduced fundamental concepts in probability starting with key terminologies such as sample spaces, events, sets, and outcomes which form the basis for understanding probability theory. It then covered the probability axioms and addressed counting problems essential for calculating probabilities in different scenarios. The chapter progressed to permutations and combinations, providing methods to count arrangements and selections in various contexts. Conditional probability and the multiplication rule were explained to handle dependent events and their joint probabilities. Data representation techniques including histograms, pie charts, scatter plots, and bar graphs were discussed to visualize data effectively. Measures of central tendency such as the mean, mode, and median were presented to summarize data sets. Finally, the chapter explored measures of spread, namely variance and standard deviation, as well as measures of location including quartiles and percentiles, which describe data distribution and position within a data set.
A computer program has 4 possible outcomes after execution: success, failure, timeout, or error. Write down the sample space and find the probability of success if all outcomes are equally likely. (2 marks)
In a database query, 8 records are retrieved. How many different ways can you select 3 records to display on the main dashboard? (3 marks)
At the start of this chapter we promised you would be able to:
Tick each one you can genuinely do.
So, are you there yet?
You're competent when you can confidently do 50% or more of what this chapter promised.
Sign in to record how you're doing.