This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.
In this problem I'm going to give you the parameters of two PRNGs that generate random bits, to simulate heads/tails coin flips. You need to analyze their properties and compare/contrast how they work.
Sequence A is a mixed LCG with m=16384, a=301, and c=10841. However, it is modified from the standard LCG in the following way: For each output \(X_n\), we first take the floor of \(X_n\) divided by 128, and then output "heads" if that number is even and "tails" if it's odd.
So for example, with the seed \(X_0=3002\), the underlying Lehmer LCG sequence starts with
\[3002, 13323, 6984, 15873, 4486, 1255, 11764, \ldots\]
and by dividing each of these by 128 you can confirm that this would generate the sequence of coin flips starting with T, H, H, H, T, T, T.
Sequence B is a linear recurrence (LFSR) with m=2 and k=14. The multipliers are all 0 except \(a_9=1\), \(a_{11}=1\), \(a_{13}=1\), and \(a_{14}=1\). There is no need to really modify this PRNG since it already outputs 1's and 0's; we just define 0 to be "heads" and 1 to mean "tails".
Determine the basic properties of both of these sequences, as we discussed in class. Consider only the final output as a series of heads/tails values. What properties to both of these sequences share in common? In what ways are they different?
After listing these properties, briefly explain which method you think is better for the task of simulating random coin flips. Be specific in your evidence!