15110 Fall 2012 [Touretzky/Kaynar]

Programming Assignment 9 - due Wednesday, October 31

Note: You are responsible for protecting your solutions to these problems from being seen by other students either physically (e.g., by looking over your shoulder) or electronically. (More information can be found in the instructions for Programming Assignment 2.)

[2 pts] The Linear Congruential Random Number Generator (LCG), which we covered in class, creates random numbers using the formula:
\(x_{i+1}=(ax_i+c) \text{ mod } m,\)
That is, if you know the \(i\)^th random number \(x_i\), then you can compute the next number in the sequence \(x_{i+1}\) using the formula. Another pseudo random number generator is the Blum Blum Shub (BBS) pseudorandom number generator. (The Blums are faculty members here at Carnegie Mellon University!) Blum Blum Shub uses the formula
\(x_{i+1}=x_i^2 \text{ mod }m \)
to compute a new pseudorandom number based on a previous one, with certain restrictions on the seed \(x_0\) and modulus \(m\). In general, compared to LCG, BBS is slower, but provides higher quality random numbers that can not be predicted without first factoring \(m\), which is hard when \(m\) is the product of two large prime numbers. An example of an \(m\) that satisfies the requirements is 2006591449, which is the product of the prime numers 44771 and 44819.
1. Write a Ruby function bbs_seq(x0,n) (in bbs_seq.rb) that returns an array of \(n\) pseudorandom numbers starting with \(x_0 \) and ending with \(x_{n-1}\), generated using the Blum Blum Shub algorithm starting with a seed of \(x_0\) and \(m\) of 2006591449. Note that you are not asked to make \(m\) a parameter of your function, which means you should use 2006591449 directly in your code. Example usage:
```
>> bbs_seq(1320173001,10)
=> [1320173001, 1250489923, 1654713313, 317068542, 1414597374, 1257516709, 1036152133, 891491908, 1351900575, 896699609]
```
2. Write a Ruby function roll_10_sided(n) (in roll_10_sided.rb) that uses a pseudorandom number sequence generated by calling the function you wrote in Part a to implement a 10 sided die. Given an argument \(n,\) the function roll_10_sided(n) returns a sequence with \(n\) numbers in the range 0 to 9. You can create such a 10 sided die using the rightmost digits of numbers in a BBS sequence. In order to seed the function from part a, use the integer representation of the current time (i.e. use the expression Time.now.to_i ). Note that the current time may not meet the requirement for the the BBS algorithm to generate a high quality sequence (we did not specify that requirement in the question). If you observe a sequence that does not match your expectations for a random sequence, you need not be concerned about this for the purposes of this question.
  Example usage:
```
>> roll_10_sided(10)
=> [0,8,3,2,9,3,6,0,5,6]
>> roll_10_sided(10)
=> [7,4,1,0,9,5,3,9,1,2]
```
[2 pts] In this question we're going to make a biased coin. Normally we assume that a coin is a binary random variable with equal probability of coming up heads or tails. We can model this in Ruby by calling rand(2) and treating a result of 1 as heads and 0 as tails. But suppose we want to model a coin that comes up heads 60% of the time. One way to do this is to provide for 10 random values, say 0 through 9. A fair coin would treat any value from 0 to 4 as tails, and 5 to 9 as heads. If we instead set our tails threshold at 3, then the last six values (4 to 9) will be treated as heads, giving this outcome a 6/10 = 60% probability.
1. Write a function biased_coin that comes up heads 75% (not 60%) of the time.
2. Write a function biased_hist that uses the RandomLab histogram feature (discussed in the textbook) to plot a histogram of heads and tails outcomes for 100 tosses of your biased coin. You will have to do include RandomLab to access the histogram methods.
  Note that when any histogram bin gets too tall, the entire histogram is automatically rescaled so that the highest bin is only about half way to the top. You may see the histogram rescaled several times when biased_hist runs, but the ratio of bin heights is always correct.
[3 pts] The binomial distribution. Even with a perfectly fair coin, you should not expect 10 toin cosses to always produce 5 heads and 5 tails. As covered in an earlier problem set, the number of distinct sequences from \(n\) tosses is \(2^n\), and the number of heads \(k\) in any sequence will be between 0 and \(n\). So if we toss a fair coin 10 times, there's a good chance we'll see 5 heads and 5 tails, but a decent chance we'll see 6 heads and 4 tails (or vice versa), and a non-negligible chance of 7 heads and 3 tails. About once in every 1024 times we will even see a string of 10 heads and no tails. The probability of \(k\) heads is given by the \(k\)th number in row \(n\) of Pascal's triangle, divided by \(2^n\). This probability distribution is known as the binomial distribution.
1. Write a function num_heads(n) that flips a fair coin and returns the number of heads encountered in \(n\) tosses. Hint: you will need to write a loop to toss the coin \(n\) times.
2. Suppose we want to explore the distribution of outcomes for trials with ten tosses of a fair coin. The number of heads in a trial will be between 0 and 10, so there are 11 possible outcomes. Write a function fair_binomial that constructs an 11 bin histogram and plots 1500 trials. Notice that the result looks like a normal distribution. (The normal distribution, or "bell curve", is the limit of a binomial distribution as the number of trials grows to infinity.)
[1 pt] Binomial distribution with a biased coin.
1. Write a function biased_heads(n) that works like num_heads(n) but uses your biased coin.
2. Write a function biased_binomial that works like fair_binomial but uses biased_heads(n) to generate the trials.
[2 pts] The variable @@drawing.counts contains the counts of the histogram, represented as a hash table. Write a function print_counts that, when called after generating a histogram, displays the counts as a table, one bin per line, and returns nil. Here is an example of calling print_counts after running biased_binomial:
```
>> print_counts
Bin    Count
0      0
1      0
2      1
3      3
4      23
5      75
6      236
7      369
8      393
9      316
10     84
=> nil
```
Hint: use a loop to iterate through the bin numbers 0 through 10. Retrieve each bin count from the hash table and print it; use a tab to line your numbers up in columns. Missing hash table values will return nil, which should be reported as 0.

Submission

You should have a pa8 directory, containing:

bb_seq.rb
roll_10_sided.rb
biased_coin.rb
biased_hist.rb
num_heads.rb
fair_binomial.rb
biased_heads.rb
biased_binomial.rb
print_counts.rb

Zip up your directory and upload it using the autolab system. (The autolab system will accept submissions beginning on Friday until the deadline Tuesday night.)