This is the archived website of SI 486H from the Spring 2016 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.

Problem 33

Coin flipper comparison

Due: February 9
Points: 3

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

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

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".

Your analysis

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!