CMPU-145, Spring 2013 Lab 10 April 29, 2013 For this lab, you will need the GEN-AND-TEST function defined in the file: "asmt5-helper.txt". So be sure to download that file from the lab10 directory. And be sure to include the expression (load "asmt5-helper.txt") at the beginning of your lab10 definitions file. PROBLEM 1. Recall from class that we discussed how to 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. I.e., each place is 1/(2^n) for some 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 in decimal floating point, we typically don't bother to write down the infinite string of zeros. Instead, we just write: 0.101. **> But we'll keep in mind 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. 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. Therefore, we know 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, LISTY, that is a *finite* list of 0s and 1s representing a binary floating point value. For example, LISTY 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 LISTY; 0 otherwise. For example, if LISTY is (1 0 1), then BIASED-TOSSER should return a 1 five-eighths of the time; 0 otherwise. (1 for heads; 0 for tails.) HINT: If LISTY 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 LISTY 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 LISTY, 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 LISTY, then you must decide HEADS or TAILS, as discussed 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 () (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. Call your function, IS-ONE?. PART C. 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. Finally, use GEN-AND-TEST to estimate the value of the fraction whose binary representation is: 0.101010101010101010101010101010... HINT: Define a "generate" function where LISTY = (1 0 1 0 ...) HINT: This one shouldn't be too hard to recognize, especially if you use a really large number of random trials. Okay, do another! 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 LISTY be for a FAIR coin?? PROBLEM 2: 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, LISTY, 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 LISTY. As in BIASED-TOSSER, if LISTY 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 estimate-biased-counter-exp-value (lambda (n listy) ;; ACC is an "accumulator", initially 0 (let ((acc 0)) ;; Use DOTIMES to run N trials (dotimes (i n) ;; For each "trial", we simply called ;; BIASED-COUNTER and add its output to ACC ;; Notice the use of the DESTRUCTIVE function SET! ;; which changes the value of ACC!!! :o (set! acc (+ acc (biased-counter listy)))) ;; Finally, divide by N to get the desired AVERAGE (/ acc n 1.0)))) Copy-and-paste this function into your definitions window. Then use it to estimate the expected value of BIASED-COUNTER for several different LISTYs. Use N = 10000 or more. Does the expected value depend on LISTY? If so, how?