CMPU-145, Spring 2017
Lab 8
We've talked about probabilities in class, including the random
events generated by fair, and unfair coins. This lab is about unfair
coins! In particular, this lab is about simulating a biased, unfair
coin with a fair coin.
The last result you'll get in this lab--the expected value generated
in Problem 2--is a pretty interesting result! To get this result, we
will use binary decimal representations, as described in Problem 1
below.
For this lab, you'll also need the GEN-AND-TEST function. It is included
in the probability helper scheme file.
PROBLEM 1.
For this exercise, we will simulate the tossing of a biased coin
using the repeated tossings of a fair coin. For example, suppose
we want a coin that comes up HEADS 62.5% of the time (i.e.,
5/8ths of the time). In this case, we say that the BIAS of the coin
is 5/8ths. We may also say that 5/8ths is the BIAS FRACTION.
First, we write down the binary floating point representation of the
bias fraction, 5/8. It is: 0.10100000000000000000000....
(Why? For binary floating point, the places to the right of the
"point" are the "1/2 place", the "1/4 place", the "1/8
place", etc. Each place is 1/(2^n) or 2^-n for a positive
integer n. Since 5/8 = 1/2 + 0/4 + 1/8, the binary
floating point representation of 5/8 is 0.1010000000....)
Of course, as with decimal floating point, we typically don't bother
to write down the infinite string of zeros. Instead, we just write:
0.101.
It is helpful to know that the infinite string of 0s is there!!
(This will come in handy later on.)
Next, we'll use our fair coin to generate a sequence of 0s and 1s.
As long as that sequence of 0s and 1s matches the sequences of 0s
and 1s in the binary floating point representation of 5/8, we'll
keep tossing. But as soon as the fair coin generates a value
different from the digits in the bias fraction, we determine the
outcome as follows:
If the fair coin came out 0, when the corresponding
digit in the bias fraction was 1, then report HEADS.
Otherwise (i.e., fair coin was 1, when the corresponding
digit in the bias fraction was 0), report TAILS.
** Do you understand why this method results in HEADS with the
appropriate bias (5/8, in this case)? **
Here are some examples:
DIGITS for 5/8: 1 0 1 0 0 0 ...
RND_1: 0 <--- HEADS (because 0 < 1)
RND_2: 1 0 0 <--- HEADS (because 0 < 1)
RND_3: 1 1 <--- TAILS (because 1 > 0)
RND_4: 1 0 1 *STOP!* <--- TAILS (see below).
In the last example, we stop after three tosses---EVEN THOUGH ALL
THREE TOSSES MATCHED. Why? We take advantage of the fact that we
know that all of the rest of the digits after the first three are
zeros. We can also surmise that, sooner or later, our fair coin will
have to report a 1. At that point, we would see a mismatch between
the fair coin and the 0 in the unending list of zeros. Thus, we
would call the toss a TAIL (since 1 > 0). Since the result is known
in advance, there is no point in tossing the fair coin more than
three times---even if the first three tosses matched. The result
has to be TAILS. This special case will be used in what follows.
PART A.
Define a function, BIASED-TOSSER, that takes one input, INPUT-LIST,
that is a *finite* list of 0s and 1s representing a binary
floating point value. For example, INPUT-LIST would be (1 0 1) to
represent 5/8 (since 5/8 = 1/2 + 0/4 + 1/8). BIASED-TOSSER should
return a 1 with probability equal to the fraction represented by
INPUT-LIST; 0 otherwise. For example, if INPUT-LIST is (1 0 1), then
BIASED-TOSSER should return a 1 five-eighths of the time; 0
otherwise. (1 for heads; 0 for tails.)
MORE: If INPUT-LIST is empty...
This is the special case seen above in the RND_4
example, in which all the rest of the digits in the
binary representation of the bias fraction are zeros.
In this case, STOP without tossing any coins! Return
TAILS.
If INPUT-LIST is non-empty...
Use the built-in RANDOM function to simulate the
tossing of a fair coin. Use LET to store that value in
a local variable, because you'll need to refer to it
later on.
If the fair coin toss matches the first digit of INPUT-LIST,
then you need to keep tossing (i.e., make a recursive
function call).
If the fair coin toss does NOT match the first digit of
INPUT-LIST, then you must decide HEADS or TAILS, as
noted above.
PART B.
We want to use GEN-AND-TEST to collect statistics on the biased
coin tosser. However, recall that the "generate" function for
GEN-AND-TEST is not allowed to take any inputs. Thus, for this
part, you will create generate functions for several different
values of the bias fraction. Each one of the "generate" functions
can be used with GEN-AND-TEST.
The following expression uses BIASED-TOSSER to create a "generate"
function that tosses a biased coin with bias = 5/8:
(define bias-5-8
(lambda () ;; don't forget that you really need to have lambda.
(biased-tosser '(1 0 1))))
Use several TESTER expressions to demonstrate that your BIAS-5-8
function returns 1 about 5/8ths of the time.
Define a few other "generate" functions following the model above.
Use different lists of zeros and ones.
Next, define a "test" function, for use with GEN-AND-TEST. In this
case, we just want a function that returns #t if the input is a 1;
#f otherwise. My recommendation is to call your function IS-ONE?.
Problem 2.
Use expressions such as (gen-and-test 10000 bias-5-8 is-one?)
to test the biased coin generation function with bias = 5/8.
Use similar expressions to test coins with other biases.
Do the values match the bias?
Problem 2 part B.
Finally, use GEN-AND-TEST to estimate the value of the fraction
whose binary representation is: 0.101010101010101010101010101010...
As a base line, define a "generate" function for a biased :-) coin that
is 1/2 (i.e. list-half)
HINT: Define a "generate" function where INPUT-LIST = (1 0 1 0 ...)
This one shouldn't be too hard to recognize, especially
if you use a really large number of random trials.
(like one million!)
Part B's Successor function: What is the value of the fraction whose
binary representation is: 0.011011011011011011011... ?
HINT: The denominator of the fraction is less than 10!
-- What should INPUT-LIST be for a FAIR coin? (it's in the template file.)
PROBLEM 3: Estimating the Expected Value of the Number of Times
BIASED-TOSSER must toss the fair coin to determine a value.
First, define a function, called BIASED-COUNTER, that takes a single
input, INPUT-LIST, that is a list of 0s and 1s (as in BIASED-TOSSER).
BIASED-COUNTER should return the number of random coin tosses
that were required to generate a DEVIATION from the sequence of
0s and 1s in INPUT-LIST. As in BIASED-TOSSER, if INPUT-LIST is empty, it
represents an infinitely long list of 0s.
NOTE: For this function, we don't care whether the outcome is a
HEADS or TAILS, we just care how many tosses it took to
determine that. So the structure of your function can be
quite similar to BIASED-TOSSER...
Next, you can use the following function to compute the average
value of a large number of calls to BIASED-COUNTER. This average
will be our estimate of the expected value of the number of
tosses required by BIASED-TOSSER.
(define expected-biased-counter-value
(lambda (n INPUT-LIST)
;; accum is an "accumumulator", initially 0
(let ((accum 0))
;; run the loop for N trials...
((for (i n))
;; For each "trial", we simply call
;; BIASED-COUNTER and add its output to accum
;; Notice the use of the DESTRUCTIVE function "SET!"
;; which changes the value of accum!!! :o
(set! accum (+ accum (biased-counter INPUT-LIST))))
;; Finally, divide by N to get the desired AVERAGE
(/ accum n 1.0))))
Use it to estimate the expected value of BIASED-COUNTER
for several different INPUT-LISTs. Use N = 10000 or more. Much more.
Does the expected value depend on INPUT-LIST? If so, how?
================
When you are done, call me or one of the coaches over to look at your
work, and please submit your work electronically, as usual.