Home

Learn How to Think with Karel the Robot. Chapter 12. Randomness and Probability

Chapter 12
Randomness and Probability

In this chapter you will learn:

  • Why is randomness useful in computing.
  • How to generate random integers using the function randint.
  • How to use the function randint to simulate rolling dice.
  • How to calculate the minimum and maximum of a given set of numbers.
  • How to generate random Booleans using the function rand.
  • How to use the function rand to simulate coin toss.
  • How to calculate simple probabilities.
  • How to use randomness to solve difficult tasks.

12.1. Why is randomness useful in computing

Random numbers are used for many applications starting with gambling and creating unpredictable results in computer games. But one of the major applications of randomness is in cryptography. Cryptography is used to secure data for safe transfer via Internet, to secure data storage, and other tasks. Creating a reliable data encryption requires numbers that nobody can guess. Think about it - if a deterministic (non-random) algorithm was used to encrypt your data, then at least the author of the algorithm would always be able to break it, read your emails, enter into your bank account, or steal your identity.

Randomness is also very important for scientific and engineering simulations. For example, imagine that an engineer computes the strength of a bridge. He or she knows that all the physical properties of the underlying materials such as the quality of the concrete and of the steel come with some amount of uncertainty. Therefore, many computations with varying parameters must be done to ensure that this uncertainty is taken into account. These methods are called Monte Carlo Methods. picture

12.2. Generating random integers

Karel can generate random integers using the function randint which was already mentioned in Section 11.12 (page 973). In summary, calling randint(m, n) returns a random integer between m and n (including m and n). Calling the function with just one argument as in randint(n) is the same as calling randint(1, n). Let’s see some examples.

First, let’s use a repeat loop to generate and display 10 random integers between -1 and 1:

1repeat 10 
2  print(randint(-1, 1))

Output:

PIC

The following program generates 10 random integers between 1 and 100:

1repeat 10 
2  print(randint(100))

Output:

PIC

12.3. Karel is rolling a die

When rolling a die, one obtains a random integer between 1 and 6. The same can be done by calling randint(1, 6) or just randint(6). Today, Karel is curious how many attempts it will take him to throw a six. Here is the corresponding program:

1n = 0 
2die = -1 
3while die != 6 
4  die = randint(6) 
5  print(die) 
6  inc(n) 
7print(~Attempts needed:~, n)

Output:

PIC

Wow, that was quick! Beginner’s luck, probably. Let’s try this one more time!

PIC

12.4. Placing objects at random locations

Karel stands in the Southwest corner of the maze, facing East:

PIC

He carries one light bulb in his backpack, and his task is to place it at a random location in the maze. The maze is 15 squares wide and 12 squares tall. Here is a program which will do it:

1x = randint(0, 14) # number of steps to make in the East direction 
2y = randint(0, 11) # number of steps to make in the North direction 
3repeat x 
4  go 
5left 
6repeat y 
7  go 
8put

Let’s execute the program two times. Keep in mind that the light bulb will not be visible because it will be beneath Karel at the end:

PIC

PIC

Figure 12.1: *

Karel’s final positions after executing the last program two times.

12.5. Building a random skyline

Today, Karel has 60 light bulbs in his bag, and his task is to use them to build a skyline.

PIC

Figure 12.2: *

Karel’s new task is to build a skyline.

The skyline will consists of 10 columns of bulbs of random heights between one and six, such as this one:

PIC

Figure 12.3: *

Random skyline.

This is the corresponding program:

1repeat 10 
2  # Generate a random integer between 1 and 6: 
3  n = randint(1, 6) 
4  # Build one column: 
5  left 
6  repeat n 
7    put 
8    go 
9  # Turn around: 
10  right 
11  right 
12  # Return back to the bottom: 
13  while not wall 
14    go 
15  # Get ready for the next column: 
16  left 
17  go

Let’s execute the program once more to show that the robot will create a different skyline:

PIC

Figure 12.4: *

Executing the program one more time.

12.6. Calculating the maximum

One important task in computer science is to calculate the maximum of a given sequence of values. Let’s take a look at a sample sequence 3, 4, 2.

As the first step, create a new variable named (for example) maximum, and initialize it with some value which is less than the lowest value in the sequence:

1maximum = 0

If you do not know how to safely choose a value which is below all values in the sequence, it is possible to take any value from the sequence. Usually it is easiest to take the first one:

1maximum = 3

We will take, for example, the initial value maximum = 0. Here is the algorithm:

Step 1:

  • The current value of maximum is 0.
  • Take the next value in the sequence: m = 3
  • Is m greater than maximum? (m is 3, maximum is 0)
  • Yes, therefore m is the new maximum: maximum = m
  • After this step, the value of maximum is at 3.

Step 2:

  • The current value of maximum is 3.
  • Take the next value in the sequence: m = 4
  • Is m greater than maximum? (m is 4, maximum is 3)
  • Yes, therefore m is the new maximum: maximum = m
  • After this step, the value of maximum is at 4.

Step 3:

  • The current value of maximum is 4.
  • Take the next value in the sequence: m = 2
  • Is m greater than maximum? (m is 2, maximum is 4)
  • No, therefore maximum stays unchanged.
  • After this step, the value of maximum is at 4.

There are as many steps as there are values in the sequence. Now let’s apply this algorithm to measure the height of a random skyline!

12.7. Measuring the height of a skyline

Karel’s next task is to measure the height of a random skyline which is formed by 10 columns of light bulbs. The height of the skyline is the height of the tallest column.

PIC

Figure 12.5: *

Karel is measuring the height of a random skyline.

To solve this task, the robot will employ the algorithm from the previous section. We will initialize maximum with 0, and measure the height m of each column. If m > maximum, he will update maximum to m. Otherwise he will leave maximum unchanged. Here is the corresponding program, enhanced with control prints to reveal in more detail what is happening:

1# Initialize the maximum with 0: 
2maximum = 0 
3# Loop over all columns: 
4repeat 10 
5  # Measure the height of the next column: 
6  m = 0 
7  left 
8  while bulb 
9    inc(m) 
10    go 
11  # Turn around: 
12  right 
13  right 
14  # Return back to the bottom: 
15  while not wall 
16    go 
17  # Get ready for the next column: 
18  left 
19  go 
20  # If m > maximum, update maximum to m: 
21  if m > maximum 
22    print(m, ~>~, maximum, ~therefore updating maximum to~, m) 
23    maximum = m 
24  else 
25    print(m, ~<=~, maximum, ~therefore maximum not updated~) 
26# Display maximum at the end: 
27print(~Height of the skyline is~, maximum)
picture

For the skyline shown above, the program will produce the following output:

PIC

12.8. Measuring the height of a building

Today Karel needs to measure the height of an unknown building. The building is formed by columns of crates.

PIC

Figure 12.6: *

Karel is measuring the height of a building.

This task is different from the previous one because Karel cannot go inside the building (crates are obstacles). Instead, he will use the Second Maze Algorithm (right-handed version) to climb on the crates. He will initialize maximum with 0. After each step along the crates he will measure his gpsy coordinate m. Note that gpsy is the height of the column below Karel. If m is greater than maximum, then he will update maximum with m. This is the corresponding program:

1maximum = 0 
2# Use the Second Maze Algorithm: 
3while not home 
4  right 
5  while wall or crate 
6    left 
7  go 
8  m = gpsy 
9  if m > maximum 
10    print(m, ~>~, maximum, ~therefore updating maximum to~, m) 
11    maximum = m 
12  else 
13    print(m, ~<=~, maximum, ~therefore maximum not updated~) 
14print(~Height of the building is~, maximum)

And here is the output:

PIC

12.9. Calculating the minimum

Calculating the minimum of a sequence of numbers is another important task in computer science. In Section 12.6 (page 1016) you learned how to calculate the maximum. Calculating the minimum is almost the same, with two differences:

  • The initial value of minimum must be greater to or equal than any value in the sequence. Alternatively, one can take the first value of the sequence.
  • The value of minimum will be updated if the new value m is less than minimum.

Let us illustrate the algorithm on a sample sequence 7, 9, 5. We will initialize the value of minimum with 10:

Step 1:

  • The current value of minimum is 10.
  • Take the next value in the sequence: m = 7
  • Is m less than minimum? (m is 7, minimum is 10)
  • Yes, therefore m is the new minimum: minimum = m
  • After this step, the value of minimum is at 7.

Step 2:

  • The current value of minimum is 7.
  • Take the next value in the sequence: m = 9
  • Is m less than minimum? (m is 9, minimum is 7)
  • No, therefore minimum stays unchanged.
  • After this step, the value of minimum is at 7.

Step 3:

  • The current value of minimum is 7.
  • Take the next value in the sequence: m = 5
  • Is m less than minimum? (m is 5, minimum is 7)
  • Yes, therefore m is the new minimum: minimum = m
  • After this step, the value of minimum is at 5.

There will be as many steps as there are values in the sequence. Now let’s apply this algorithm to measure the clearance of an unknown cave! picture

12.10. Measuring the clearance of a cave

Today, Karel is exploring a cave. In order to know whether all his equipment will pass through it, he wants to first measure the clearance (minimum height between the floor and the ceiling).

PIC

Figure 12.7: *

Karel is measuring the clearance of a cave.

He will use the algorithm from the previous section. Since the maximum height of the maze is 12 grid squares, a good initial value for minimum is 12:

1minimum = 12 
2while not home 
3  # Measure the height of the current column: 
4  m = 1 
5  left 
6  while not wall 
7    inc(m) 
8    go 
9  # Turn around 
10  right 
11  right 
12  # Get back down: 
13  while not wall 
14    go 
15  # Get ready for the next column: 
16  left 
17  go 
18  # Update the minimum if M < minimum: 
19  if m < minimum 
20    print(m, ~<~, minimum, ~therefore updating minimum to~, m) 
21    minimum = m 
22  else 
23    print(m, ~>=~, minimum, ~therefore minimum not updated~) 
24print(~Clearance of the cave is~, minimum)

Output:

PIC

12.11. Generating random Booleans

Karel has a function rand which returns either True or False with a 50 % probability. In other words, there is the same chance of returning True or False.

For illustration, let’s call the function rand 10 times and display the result:

1repeat 10 
2  print(rand)

Output:

PIC

12.12. Karel is tossing a coin

Calling the function rand is the same as tossing a coin. Today Karel does not know whether he should go to cinema or read a book. The following program which simulates a coin toss will help him decide:

1heads = rand 
2if heads 
3  print(~I got heads, so I will go to the cinema.~) 
4else 
5  print(~I got tails, so I will read a book.~)

Output:

PIC

So, Karel decided to go to the cinema today!

12.13. Calculating probabilities

This is easy. Probability is just the number of favorable outcomes divided by the number of all possible outcomes. Let’s return to the coin toss for a moment.

PIC

What is the probability of getting heads? The number of favorable outcomes is 1, the number of all possible outcomes is 2. Therefore, the probability of getting heads is 1/2 which is 0.5. It is possible to report probabilities in percent, by multiplying the result by 100. Hence, the probability of getting heads is 50 %.
picture

Now let’s say that we toss the coin twice.

PIC   PIC

What is the probability of getting heads both times? Well, there are four possible outcomes: Getting heads in the first toss and the second, getting heads in the first toss and tails in the second, getting tails in the first toss and heads in the second, and getting tails both times. But only 1 outcome is favorable - that’s the first one (heads and heads). Therefore, the probability of getting heads in both cases is 1 / 4 = 0.25, or 25 %.

Next, what is the probability of getting a 6 on a die? There is 1 favorable outcome:

PIC

The number of all possible outcomes is 6:

PIC

Therefore, the probability of getting a six is 1/6 which is approximately 0.17 or 17 %.

As a last example, let’s roll the dice two times. What is the probability of the sum of the points being at most three? Well, that’s easy. There are 36 possible outcomes: 1 in the first roll and 1 in the second, 1 in the first roll and 2 in the second, ..., 1 in the first roll and 6 in the second. That’s six. Then 2 in the first roll and 1 in the second, 2 in the first roll and 2 in the second, ..., 2 in the first roll and 6 in the second. That’s another six. There are four more sets of six, for getting 3, 4, 5, 6 in the first roll. Hence 6 times 6 is 36.

What is the number of favorable outcomes? Well, the sum can never be 1 because in each roll the minimum is 1. So the minimum score is 1 + 1 = 2. The score of three can only be obtained as 1 + 2 or 2 + 1. Hence, there are 3 favorable outcomes. In summary, the probablity of getting a score of at most three in a double roll is 3 / 36 = 1 / 12. This is approximately 0.08 or 8 %.

12.14. Probability of events vs. their frequency

The probability of an event only is an approximate indicator for the frequency of that event. For example, the probability of getting heads when tossing a coin is 50 %. But this does not mean that one gets heads exactly one time when tossing the coin twice. Let’s get Karel’s help to explain this in more detail.

Today, Karel has many ribbons in his bag and he wants to split them into two parts. He will be tossing a coin to do that. When he gets heads (True), he will place a ribbon on the left. When he gets tails (False), he will place a ribbon on the right.

PIC

Figure 12.8: *

Karel wants to split the contents of his bag into two parts.

He will use the following program, starting with 20 ribbons:

1repeat 20 
2  if rand 
3    left 
4    go 
5    go 
6    put 
7    right 
8    right 
9    go 
10    go 
11    left 
12  else 
13    right 
14    go 
15    go 
16    put 
17    left 
18    left 
19    go 
20    go 
21    right

Will he get 10 on the left and 10 on the right?

And here is the result - 12 ribbons on the left and 8 on the right!

PIC

Let’s do this again, now with 100 ribbons (the number of repetitions on line 1 will be changed to 100). When the program finishes, there are 44 ribbons on the left and 56 on the right:

PIC

And one last time, let’s do the same with 500 ribbons. The result is - 238 ribbons on the left and 262 on the right:

PIC

You can observe one very interesting thing here. If the exact half is the perfect outcome, then the first time the result was 2 ribbons off (12 instead of 10), the second time the result was 6 ribbons off (44 instead of 50), and the last time the result was 12 ribbons off (238 instead of 250). That number seems to be growing. But to be fair, one has to make it proportional to the number of events - which means to divide it by the number of coin tosses. Hence, in the first case we obtain 2 / 20 = 0.1, in the second case 6 / 100 = 0.06, and in the third case 12 / 500 = 0.024.

This number is the relative discrepancy between the frequency of the event and its predicted probability. As you can see, the value steadily decreases from 0.1 to 0.06 to 0.024. In other words, the relative frequency of the event is getting closer to its predicted probability. In mathematics, this is called the Law of Large Numbers (LLN). If you are interested, you can find more about it on Wikipedia. picture

12.15. Karel and random walks

The Boolean function rand allows us to do very interesting things. Such as - we can let Karel make random walks in the maze! What does it mean? Instead of just letting him make one step forward, we can let him make the step forward with probability 50 %. The other 50 % we can split between turning left and turning right. In other words, he will turn left with probability 25 % or right with probability 25 %. This is the corresponding program (the number of steps can be changed as needed):

1repeat 100      # make 100 steps 
2  if rand       # go straight with probability 50% 
3    if not wall 
4      go 
5  else          # the else branch is executed with probability 50% 
6    if rand     # turn left with probability 25% 
7      left 
8    else        # turn right with probability 25% 
9      right

As you can see, we also added a check for a wall on line 3 - without it, the robot would crash into a wall in no time. Here is the maze where we will try this program out:

PIC

Figure 12.9: *

Karel’s initial position.

And here you can see where Karel went when the program was executed:

PIC

Figure 12.10: *

The trace of Karel’s random walk.

Notice a few "dead ends". They occur when Karel turns twice in a row and goes back.

12.16. Using randomness to solve difficult tasks

Some tasks are very difficult to solve using deterministic (non-random) algorithms.

PIC

Figure 12.11: *

Karel needs to collect two rugs at unknown positions.

This maze is not suitable for the maze algorithms we know. The First Maze Algorithm fails to find the rugs (green line) and so does the Second Maze Algorithm (red line).

PIC    PIC

Figure 12.12: *

Both the First and Second Maze Algorithms fail.

Both these algorithms actually get into an infinite loop. One possible solution is to let Karel walk randomly in the maze until he finds the rugs. Well, for simplicity, let us have him stop after he finds the first one. Here is the corresponding program:

1while empty     # repeat until you find the first rug 
2  if rand       # go straight with probability 50% 
3    if not wall 
4      go 
5  else          # the else branch is executed with probability 50% 
6    if rand     # turn left with probability 25% 
7      left 
8    else        # turn right with probability 25% 
9      right 
10  if rug        # if you find a rug, collect it 
11    get

This works. Use the Karel App in NCLab to re-create the maze, and try it yourself!

12.17. Review questions

QUESTION 12.1. Which of the following areas of computing benefit from randomness?

A
logic
B
cryptography
C
game design
D
scientific computing

QUESTION 12.2. What function in Karel is used to generate random integers?

A
random
B
rint
C
randomint
D
randint

QUESTION 12.3. What is the equivalent of rolling a die?

A
randint(1, 6)
B
randint(0, 6)
C
randint(1, 7)
D
randint

QUESTION 12.4. What is the maximum of the numbers 3, 9, 6, 7, 2?

A
2
B
3
C
7
D
9

QUESTION 12.5. If maximum is the current value of the maximum, and the next value is m, what condition is used to update maximum?

A
if m > maximum
B
if m < maximum

QUESTION 12.6. What is the minimum of the numbers 3, 9, 6, 7, 2?

A
2
B
3
C
7
D
9

QUESTION 12.7. If minimum is the current value of the minimum, and the next value is m, what condition is used to update minimum?

A
if m > minimum
B
if m < minimum

QUESTION 12.8. When tossing a coin, what is the probability of getting heads?

A
50 %
B
0.5
C
5.0
D
100 %

QUESTION 12.9. When tossing a coin two times, what is the probability of getting heads both times?

A
50 %
B
25 %
C
0.5
D
0.25

QUESTION 12.10. When rolling a die, what is the probability of getting a 3?

A
1/6
B
3/6
C
1/2
D
1

QUESTION 12.11. When rolling a die, what is the probability of getting an even number?

A
1/2
B
1/6
C
1/3
D
0

QUESTION 12.12. When rolling a die two times, what is the probability of getting a combined score of 2?

A
0
B
1/2
C
1/18
D
1/36

QUESTION 12.13. A favorable event has probability 50%, and we do 10 experiments. How many times will the favorable event occur?

A
5 times
B
4 times
C
6 times
D
This is impossible to say.

Table of Contents

Created on September 27, 2018 in Karel.
Add Comment
Cancel
0 Comment(s)

Your Comment

By posting your comment, you agree to the privacy policy and terms of service.