Lab: Randomness and simulation

Assigned
Wednesday, Oct 31, 2018
Due
Lab writeups are due at 10:30pm on the day of the next class meeting. For example, a Wednesday lab is due at 10:30pm on Friday. Each lab writeup will be announced at the end of class on a lab day.
Summary
In this laboratory, you will explore the random procedure, its use in simulating simple games, and its use in making “unpredictable” texts.

Preparation

a. Make sure that you have the latest version of the csc151 package.

b. Copy the code from the reading into your definitions pane. You should include roll-a-die, roll-dice, random-elt, and the various procedures for generating sentences.

Exercises

Exercise 1: Counting odds

Write a recursive procedure, (count-odd-rolls n) that counts the number of odd numbers that come up when rolling n six-sided dice.

> (count-odd-rolls 10)
7
> (count-odd-rolls 10)
2
> (count-odd-rolls 10)
6
> (count-odd-rolls 10)
5

Please use direct recursion to implement count-odd-rolls. Your procedure should look something like

(define count-odd-rolls
  (lambda (n)
    (cond
      [(zero? n)
       0]
      [(odd? (roll-a-die))
       ...]
      [else
       ...])))

Exercise 2: Sevens or elevens

Consider the problem of rolling a pair of dice n times and counting the number of times that either a seven (7) or an eleven (11) comes up.

a. What is wrong with the following pair of procedures that are intended to accomplish this task?

;;; Procedure:
;;;   pair-a-dice
;;; Parameters:
;;;   [None]
;;; Purpose:
;;;   Roll two six-sided dice and find their sum.
;;; Produces:
;;;   roll, an integer
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   2 <= roll <= 12
;;;   Across multiple calls, the various rolls have the same probabilities 
;;;     as we would get from rolling two dice.
(define pair-a-dice
  (lambda ()
    (+ (roll-a-die) (roll-a-die))))

(define tally-seven-eleven
  (lambda (n)
     (cond 
       [(<= n 0) 
        0]
       [(or (= (pair-a-dice) 7) (= (pair-a-dice) 11))
        (+ 1 (tally-seven-eleven (- n 1)))]
       [else 
        (tally-seven-eleven (- n 1))])))

Hint: How many times should we roll a pair of dice to find out how many sevens or elevens come up in n rolls? Add an expression using display to the pair-a-dice procedure so that you can count how many times it is called.

(define pair-a-dice
  (lambda ()
    (display "Rolling ...") (newline)
    (+ (roll-a-die) (roll-a-die))))

If that isn’t enough of a hint, read the notes on this problem.

b. Write a correct version of tally-seven-eleven.

Exercise 3: Flipping a coin

a. Write a zero-parameter procedure, (heads?) that simulates the flipping of a coin. The heads? procedure should return #t (which represents “the coin came up heads”) half the time and #f (which represents “the coin came up tails”) about half the time.

> (heads?)
#f
> (heads?)
#f
> (heads?)
#t
> (heads?)
#f
> (heads?)
#t

b. Write a procedure, (count-heads n), that simulates the flipping of n coins (using heads? to simulate the flipping of each coin) and returns the number of times the coin is heads. You will likely find the following form useful.

(define count-heads
  (lambda (n)
    (let kernel ([count 0] 
                 [remaining n])
       (cond
         [(zero? remaining)
          count]
         ...))))

c. Use count-heads to explore the distribution heads? gives by counting the number of heads you get in 100 flips, 1,000 flips, and 10,000 flips.

Exercise 4: Choosing names

Suppose we have a list of names, students, that represents all of the students in a class.

(define students
  (list "Andi" "Brook" "Casey" "Devin" "Drew" "Dylan" "Emerson" "Frances"
        "Gray" "Harper" "Jamie" "Kennedy" "Morgan" "Phoenix" "Quinn" "Ryan"))

a. Write a procedure, (random-student), that randomly selects the name of a student from the class.

b. Write a procedure, (random-pair), that randomly picks one student from students, then another, and then puts them together into a list.

c. What are potential problems with using (random-pair) to select partners from the class?

Exercise 5: Generating sentences

a. Using the sentence procedure, generate about five different sentences.

b. Add a few names, verbs, adjectives, and nouns to expand the range of sentences, then generate five new sentences.

Exercise 6: Non-uniform distributions

All of the procedures we’ve written so far assume that we have a uniform distribution (of dice faces, verb occurrences, or whatever). But many distributions are not uniform. Consider, for example, a bag of M&M Candies. According to Josh Madison,

I checked out M&M’s web site. According to it, each package of Milk Chocolate M&M’s should contain 24% blue, 14% brown, 16% green, 20% orange, 13% red, and 14% yellow M&M’s.

We might represent that distribution in Scheme as a list of “color + frequency” lists.

(define m&m-colors
  (list (list "blue" 24)
        (list "brown" 14)
        (list "green" 16)
        (list "orange" 20)
        (list "red" 13)
        (list "yellow" 14)))

a. You may have noted that these numbers don’t add up to 100. Write a procedure, (total-frequency tallies), that adds up the second numbers in a list of the form above.

> (total-frequency m&m-colors)
101
> (total-frequency '((a 3) (b 5) (c 2) (d 8)))
18

b. Write a procedure, (one-m&m), that “randomly” chooses an M&M color according to the distribution above. You should use (random 101) and then pick which color depending on its value.

> (one-m&m)
"blue"
> (one m&m)
"orange"

c. Write a procedure, (lots-of-m&ms n), that makes a list of n randomly chosen M&M colors.

> (lots-of-m&ms 20)
'("brown"
  "green"
  "red"
  "orange"
  "blue"
  "red"
  "blue"
  "blue"
  "yellow"
  "yellow"
  "brown"
  "brown"
  "red"
  "orange"
  "blue"
  "green"
  "blue"
  "red"
  "blue"
  "orange")

d. Explore the distribution you actually get using tally-all and a large n. For example,

> (tally-all (lots-of-m&ms 1000))

Exercise 7: Non-uniform distributions, revisited

Consider the following procedure.

(define select-from-distribution
  (lambda (tallies)
    (let ([choice (random (total-frequency tallies))])
      (let kernel ([selector choice]
                   [remaining tallies])
        ; (display (list 'kernel selector remaining)) (newline)
        (let* ([entry (car remaining)]
               [entry-frequency (cadr entry)])
          (if (< selector entry-frequency)
              (car entry)
              (kernel (- selector entry-frequency)
                      (cdr remaining))))))))

a. What does this procedure seem to do?

b. Uncomment the display line and call (select-from-distribution m&m-colors) a few times.

c. Explain, in your own words, how select-from-distribution works.

d. There’s no check to ensure that remaining is nonempty. Why doesn’t the code need such a check?

For those with extra time

Extra 1: Generating mediocre text

The select-from-distribution procedure selects “randomly” from an unequally distributed set of values. One unequally distributed set of values we’ve encountered recently is the set of tallies of words in a book.

> (define bronte-words (file->words "/home/rebelsky/Desktop/pg1260.txt"))
> (length bronte-words)
192630
> (define bronte-tallies (tally-all bronte-words)) ; Warning!  This is *slow*.
> (length bronte-tallies)
13828

We could poorly simulate an author by selecting words randomly according to that distribution.

> (select-from-distribution bronte-tallies)
"Anybody"
> (select-from-distribution bronte-tallies)
"they"

Write a procedure, (new-sentence n tallies), that generates a new sentence of the appropriate length using the distribution given in the tally.

> (new-sentence 20 bronte-tallies)
"thoughts I snoring with pleasure past no quiescence brought laugh be sake he her man in I at had to "
> (new-sentence 20 bronte-tallies)
"had rode want record and a raised sparkling patience introduced no been might jetty very or four that was that "

Extra 2: Improving text generation

Suggest a few techniques that could be used to improve the generation of text.

Notes

Notes on Exercise 2: Sevens or Elevens

If there are n rolls that we want to count, we should only roll the dice n times. However, you will find that tally-seven-eleven does somewhere between n and 2n calls. Why? Because the “is it seven or eleven” test potentially rolls the dice twice, once to see if the roll is seven and, if not, one more time to see if the roll is eleven.

Return to the exercise.