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.)
\(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.
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]
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.
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.
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.>> 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
You should have a pa8 directory, containing:
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.)