Problem 25

This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.

# Coin flipper comparison

Due: February 8
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".