PA 8.2: Counting coin flips through simulation
- Due Apr 20, 2021 by 11:59pm
- Points 10
- Submitting a file upload
- File Types cpp
- Available after Apr 6, 2021 at 2pm
When completing this programming assignment, you may work with up to one other person. No groups of more than two are permitted.
Imagine flipping a (fair) coin. On each flip, it can land heads up or tails up with the same probability. What we want to know is, if we flip the coin n times, what is the expected length of the longest run of all heads or all tails? If we flip 10 times, should we be surprised to see 5 heads in a row at some point?
There is a formula to compute this number, but another way to arrive at it is empirically through simulation. That is, we will simulate 10,000 trials of flipping the coin n times (based on a user-provided n). In each trial, we will count the longest run of either heads or tails. For example, here are three trials and the size of their longest run:
H H T H H H T H T T -- 3
T H H T H H T T T T -- 4
T H H T H H T T H T -- 2
We will then average the counts from the 10,000 trials and that is the expected length of the longest run. (In the example above, which only has three trials, the average is 3; with 10,000 trials, you will wind up with a real number, e.g., 5.32).
To achieve this, you will need a program with a few functions. One function is in charge of simulating a single coin flip and should simply return whether it's heads or tails (an enum would work well here, but isn't necessary). Another function should take care of simulating a single trial of n flips (that number should be specified as a parameter) and should count and return the longest run of heads or tails in the trial. Finally, a third function should take care of running all the trials of n flips each (those two numbers should be specified as a parameter), averaging the longest run across the trials, and then returning that average. Main should call that last function and pass in the number of trials (use a const set to 10000).
Copy the following header and specifications checklist and paste it at the top of your source code. As you complete the specifications, fill in the [ ] next to that specification in the check list (e.g., like this: [x]). I will not grade submissions with missing specifications; please do not submit if you cannot check all of them off. This specs checklist is essentially a way for you to self grade before you submit your program.
// Name:
// Date:
// Partner:
//
// Specifications checklist for PA Option 2.1
//
// General specs:
// [ ] the header includes your name and anyone you worked with
// [ ] the header includes this specifications checklist with all completed
// specifications checked off: [x]
// [ ] the code is indented properly (inside of every block, code is indented
// one more tab)
// [ ] each chunk of code that "hangs together" (works toward a higher level goal):
// [ ] includes a brief, useful comment above it
// [ ] is separated from the next chunk by a blank line
// [ ] there are no really long lines of code or comments (if you have long
// lines, split them across multiple shorter lines)
// [ ] identifiers are well named
// [ ] the program compiles
// [ ] the program runs without crashing or hanging
// [ ] all output and prompts look clean (correct spelling, capitalization,
// nothing squished)
// [ ] all prompts make it clear what data the user is expected to enter and in
// what format and work as expected
// [ ] every function includes a JavaDoc above it that specifies all present
// parameters and return values.
// [ ] parameters are specified as pass by reference only when necessary
//
// Specific specs:
// [ ] the program prompts the user for the size of each trial
// [ ] three functions other than main are defined:
// [ ] a function to simulate flipping a coin (uses the rand() function)
// [ ] input: nothing
// [ ] output: heads or tails
// [ ] a function to simulate a trial of n coin flips
// [ ] input: n
// [ ] output: the longest run of heads or tails in the trial (whole number)
// [ ] a function to run a set of trials
// [ ] input: the number of trials to run, the number of flips per trial (n)
// [ ] output: the average longest run of heads or tails across all the trials (real number)
// [ ] the random number generator is properly seeded once in main using the current time
// [ ] the results are approximately aligned with the table of expected results at the
// bottom of the assignment description
Expected results (as these are simulations, your numbers will vary slightly, but you should be in the same ballpark):
Input (number of flips per trial) | Expected longest flip (ish) |
10 | 3.6 (ish) |
50 | 5.9 (ish) |
100 | 6.9 (ish) |
200 | 7.9 (ish) |
500 | 9.1 (ish) |
If you are working with a partner, both of you must submit individually.