Pseudocode for Probability and Simulation Revision Notes for VCE SSCE Mathematical Methods

Pseudocode for Probability and Simulation

Introduction to computer simulation for probability

Using a computer to carry out probability simulations allows us to conduct many more trials than we could do by hand. This means we can obtain much more accurate estimates of required probabilities.

Pseudocode is an informal notation used to describe algorithms in a way that is easy for humans to understand, regardless of which programming language will eventually be used. In probability work, we use pseudocode to describe two types of algorithms:

Simulation algorithms that estimate probabilities by running many random trials
Exact calculation algorithms that systematically check all possible outcomes when manual counting would be too time-consuming

infoNote

The power of computer simulation lies in its ability to perform thousands or millions of trials in seconds, giving us highly accurate probability estimates that would be impractical to obtain through physical experiments.

Algorithms for simulation

Key pseudocode functions

For probability simulations, we use two essential pseudocode functions to generate random values:

The random() function

This generates a random real number in the interval $(0, 1)$ . The generated number could be any value between $0$ and $1$ , but will never be exactly $0$ or $1$ .

The randint(n, m) function

This generates a random integer between $n$ and $m$ inclusive. Both endpoints are included in the possible outcomes. For example, randint(1, 6) simulates rolling a standard die, as it can produce any integer from $1$ to $6$ .

chatImportant

Understanding the difference:

random() produces continuous values (decimals) in the range $(0, 1)$
randint(n, m) produces discrete values (whole numbers) from $n$ to $m$ inclusive

Choose randint for simulations involving dice, cards, or other scenarios with distinct outcomes. Use random() when you need continuous random values.

Worked example: Estimating probability of rolling a six

lightbulbExample

Worked Example: Simulating the Probability of Rolling a Six

Problem: Describe a simulation algorithm to estimate the probability of obtaining a six when a fair die is rolled.

Algorithm:

input N
count ← 0
for i from 1 to N
    outcome ← randint(1, 6)
    if outcome = 6 then
        count ← count + 1
    end if
end for
estimate ← count/N
print estimate

How this algorithm works:

We need to set up several variables to track what happens during our simulation:

N stores the number of times we will roll the die (this is our input)
outcome stores the result of each individual roll
count keeps a running tally of how many sixes we have obtained

The algorithm uses a for loop to simulate rolling the die $N$ times. A for loop is perfect here because we know exactly how many times we want to repeat the process.

In each pass through the loop, we:

Generate a random integer between $1$ and $6$ using randint(1, 6) to simulate one die roll
Check if the outcome equals $6$
If it does, add $1$ to our count

After all $N$ rolls are complete, we calculate the probability estimate using:

\text{estimate} = \frac{\text{count}}{N}

This gives us the proportion of rolls that resulted in a six, which estimates the true probability.

infoNote

When this algorithm runs on a computer, the output will be slightly different each time due to the random nature of the simulation. For example, running the algorithm with $N = 100\,000$ might produce outputs like $0.16655$ , $0.16670$ , $0.16599$ , and $0.16726$ on different runs. These all cluster around the true probability of $\frac{1}{6} \approx 0.1667$ .

Worked example: Average rolls needed to get a six

lightbulbExample

Worked Example: Finding the Average Number of Rolls

Problem: Describe a simulation algorithm to estimate the long-term average for the number of rolls of a die that it takes to first get a six.

Algorithm:

sum ← 0
for i from 1 to 1000
    outcome ← 0
    count ← 0
    while outcome ≠ 6
        outcome ← randint(1, 6)
        count ← count + 1
    end while
    sum ← sum + count
end for
print sum/1000

How this algorithm works:

This algorithm is more complex because we need to track two different things: the number of rolls in each individual trial, and the total across all trials.

We use these variables:

outcome stores the result of the current roll
count keeps track of the number of rolls in the current trial
sum keeps a running total of the number of rolls required across all trials

The algorithm uses a for loop to simulate $1000$ separate trials. This gives us enough data to estimate the long-term average.

Within each trial, we use a while loop to keep rolling until we get a six. A while loop is appropriate here because we don't know in advance how many rolls it will take. The loop continues as long as outcome ≠ 6 (the outcome is not equal to $6$ ).

Inside the while loop:

We roll the die using randint(1, 6)
We increment the count by $1$
If the outcome is $6$ , the while loop ends

After each trial completes, we add the number of rolls required (stored in count) to our running total (sum).

Finally, we calculate the average by dividing the total number of rolls across all trials by the number of trials:

\text{average} = \frac{\text{sum}}{1000}

chatImportant

For loops vs While loops:

Use a for loop when you know exactly how many iterations you need
Use a while loop when you need to continue until a specific condition is met

Algorithms for calculating exact probabilities

While simulation gives us estimates, we can also use algorithms to calculate exact probabilities when there are too many outcomes to count manually.

Consider rolling dice: with two dice, there are only $36$ equally likely outcomes, which we can count by hand. However, with three dice, there are $216$ outcomes, and with four dice, there are $1296$ outcomes. When dealing with such large numbers of equally likely outcomes, we can use a computer algorithm to systematically check all possibilities and calculate the exact probability.

Worked example: Three dice sum probability

lightbulbExample

Worked Example: Calculating Exact Probability for Three Dice

Problem: Three dice are rolled and the sum of the three numbers on the uppermost faces is recorded. Describe an algorithm to find the probability that this sum is between $7$ and $14$ inclusive.

Algorithm:

total ← 0
count ← 0
for i from 1 to 6
    for j from 1 to 6
        for k from 1 to 6
            total ← total + 1
            if 7 ≤ i + j + k ≤ 14 then
                count ← count + 1
            end if
        end for
    end for
end for
print count/total

How this algorithm works:

Let $i$ , $j$ , and $k$ represent the numbers shown on the three dice. We use three nested for loops to systematically examine all possible combinations of values.

The variables track:

count keeps a running tally of outcomes $(i, j, k)$ where $7 \leq i + j + k \leq 14$
total keeps a running tally of all possible outcomes $(i, j, k)$

The three nested loops work together:

The outer loop runs through all possible values of $i$ from $1$ to $6$
For each value of $i$ , the middle loop runs through all possible values of $j$ from $1$ to $6$
For each combination of $i$ and $j$ , the inner loop runs through all possible values of $k$ from $1$ to $6$

This structure ensures we examine every possible outcome exactly once.

For each combination, we:

Increment the total count by $1$
Check if $7 \leq i + j + k \leq 14$
If this condition is true, increment the count by $1$

The total number of outcomes is:

6 \times 6 \times 6 = 216

The algorithm calculates the exact probability as:

\text{Pr}(7 \leq i + j + k \leq 14) = \frac{\text{count}}{\text{total}} = \frac{22}{27}

This is an exact answer, not an estimate, because we have systematically checked every single possible outcome.

infoNote

Nested loops for multiple events: Each independent random event (each die) gets its own loop layer. For three dice, we need three nested loops; for four dice, we would need four nested loops.

Remember!

bookmarkSummary

Key Points to Remember:

Simulation algorithms use random functions to estimate probabilities by running many trials; the more trials you run, the more accurate your estimate becomes
Two key functions enable simulations: random() generates random real numbers in $(0, 1)$ , while randint(n, m) generates random integers between $n$ and $m$ inclusive
For loops are used when you know how many iterations you need, while while loops continue until a specific condition is met
Exact probability algorithms systematically examine all possible outcomes using nested loops; this is useful when there are too many outcomes to count by hand
Probability estimates from simulations are calculated as:

\frac{\text{count}}{\text{total}}

where count is the number of successful outcomes and total is the number of trials

Pseudocode for Probability and Simulation (VCE SSCE Mathematical Methods): Revision Notes