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.