Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What's the best way to test this?

I'm going through the EdgeCase Ruby Koans. In about_dice_project.rb, there's a test called "test_dice_values_should_change_between_rolls", which is straightforward:

  def test_dice_values_should_change_between_rolls
    dice = DiceSet.new

    dice.roll(5)
    first_time = dice.values

    dice.roll(5)
    second_time = dice.values

    assert_not_equal first_time, second_time,
      "Two rolls should not be equal"
  end

Except for this comment that appears there:

# THINK ABOUT IT:
#
# If the rolls are random, then it is possible (although not
# likely) that two consecutive rolls are equal.  What would be a
# better way to test this.

Which (obviously) got me thinking: what is the best way to reliably test something random like that (specifically, and generally)?

like image 805
Matthew Groves Avatar asked Jan 17 '10 22:01

Matthew Groves


People also ask

What are some symptoms of the COVID-19 Omicron variant?

Omicron was first detected in November 2021 and has become the most dominant strain of COVID-19. Common symptoms are typically less severe than other variants and include cough, headache, fatigue, sore throat and a runny nose, according to the researchers.

Which COVID-19 tests are more accurate PCR or antigen tests?

PCR tests are more accurate than antigen tests. "PCR tests are the gold standard for detecting SARS-CoV-2," says Dr. Broadhurst. "It is the most accurate testing modality that we have.

When should you take a COVID-19 PCR test instead of a rapid antigen test?

“PCR would be chosen where there is a low likelihood of having the virus, but we want to be certain the patient doesn't have it. Antigen would be chosen if there is a high probability the patient has the virus (i.e. is experiencing symptoms), and we need to screen the patient as positive or negative,” Heather said.

What is the most accurate diagnostic test to detect COVID-19?

Reverse transcription polymerase chain reaction (RT-PCR)-based diagnostic tests (which detect viral nucleic acids) are considered the gold standard for detecting current SARS-CoV-2 infection.


2 Answers

IMHO most answers so far have missed the point of the Koan question, with the exception of @Super_Dummy. Let me elaborate on my thinking...

Say that instead of dice, we were flipping coins. Add on another constraint of only using one coin in our set, and we have a minimum non-trivial set that can generate "random" results.

If we wanted to check that flipping the "coin set" [in this case a single coin] generated a different result each time, we would expect the values of each separate result to be the same 50% of the time, on a statistical basis. Running that unit test through n iterations for some large n will simply exercise the PRNG. It tells you nothing of substance about the actual equality or difference between the two results.

To put it another way, in this Koan we're not actually concerned with the values of each roll of the dice. We're really more concerned that the returned rolls are actually representations of different rolls. Checking that the returned values are different is only a first-order check.

Most of the time that will be sufficient - but very occasionally, randomness could cause your unit test to fail. That's not a Good Thing™.

If, in the case that two consecutive rolls return identical results, we should then check that the two results are actually represented by different objects. This would allow us to refactor the code in future [if that was needed], while being confident that the tests would still always catch any code that didn't behave correctly.

TL;DR?

def test_dice_values_should_change_between_rolls
  dice = DiceSet.new

  dice.roll(5)
  first_time = dice.values

  dice.roll(5)
  second_time = dice.values

  assert_not_equal [first_time, first_time.object_id],
    [second_time, second_time.object_id], "Two rolls should not be equal"

  # THINK ABOUT IT:
  #
  # If the rolls are random, then it is possible (although not
  # likely) that two consecutive rolls are equal.  What would be a
  # better way to test this.
end
like image 62
Mark Glossop Avatar answered Sep 22 '22 22:09

Mark Glossop


I'd say the best way to test anything that involves randomness is statistically. Run your dice function in a loop a million times, tabulate the results, and then run some hypothesis tests on the results. A million samples should give you enough statistical power that almost any deviations from correct code will be noticed. You are looking to demonstrate two statistical properties:

  1. The probability of each value is what you intended it to be.
  2. All rolls are mutually independent events.

You can test whether the frequencies of the dice rolls are approximately correct using Pearson's Chi-square test. If you're using a good random nunber generator, such as the Mersenne Twister (which is the default in the standard lib for most modern languages, though not for C and C++), and you're not using any saved state from previous rolls other than the Mersenne Twister generator itself, then your rolls are for all practical purposes independent of one another.

As another example of statistical testing of random functions, when I ported the NumPy random number generators to the D programming language, my test for whether the port was correct was to use the Kolmogorov-Smirnov test to see whether the numbers generated matched the probability distributions they were supposed to match.

like image 36
dsimcha Avatar answered Sep 20 '22 22:09

dsimcha