Pseudorandomness contest, Round 1

post by Eric Neyman (UnexpectedValues) · 2020-12-13T03:42:10.654Z · LW · GW · 20 comments

This is a link post for https://ericneyman.wordpress.com/2020/12/13/pseudorandomness-contest-round-1/

Contents

  Round 1: Pseudorandom number generation
  Round 2: Distinguishing real and fake randomness
  Grading
  Prizes
  More details
  How to participate
  Questions?
None
21 comments

I’ve decided to run a pseudorandomness contest — a reverse Turing test of sorts, if you will. Winners will get to send some of my money to a charity of their choice! Here’s how it’s going to work:

Round 1: Pseudorandom number generation

Should you choose to take part, you will have 10 minutes to come up with a sequence of 150 bits (i.e. zeros and ones). The deadline for doing so is Saturday, December 19th 11:59 ET. You will use the form linked at the bottom of this post for submission. (But read the rest of this post first.)

You may not use a computer or any other resources. For example, you may not use a watch to try to generate random numbers (though you can use one to keep track of the time remaining). No using books, or calculators, or deriving random bits from cracks in the ceiling, etc. The only exception is: you may use Notepad (or something similar) to write down your sequence of bits as you come up with them (but not for scratchwork — everything besides writing down your bits must be done in your head). I recommend this website so you can keep track of how many bits you have. (You may not use a counter that tells you how many of each bit you have.) You may use anything you currently have stored inside your head. You may not memorize anything in advance of participating, though you are allowed to think in advance about general strategy (without writing anything down). [Edit 1: Please do not look up strategies; any thinking you do in advance should be your own.] [Edit 2: Think about the rules this way -- ideally you'd be doing this in a uniformly blank room with a computer where the only things you can do are type 0, type 1, backspace, and go to some point in the string you have already typed, as well as see how much time you have left and how many bits you have already typed.]

Round 2: Distinguishing real and fake randomness

If there are n entries in Round 1, I will use a computer to come up with n sequences of 150 random bits. I will post all 2n sequences in a random order in a Google sheet. You will have as much time as you want (subject to a deadline — probably a week or so after I post the Google sheet) to try to figure out which sequences were generated by a human and which by a computer. Then, for every sequence you will submit a probability that that sequence was made by a computer (i.e. “truly” random).

You may use any resources you want to complete this task, e.g. write a computer program or do research on the Internet. The only restriction is: you may not use a program written by someone else for this (or a similar) purpose. You also may not collaborate with other contest participants. (These details are subject to change, but this will be the basic format.)

Grading

Participants in Round 2 will be graded using Brier’s quadratic scoring rule, which means that they will be incentivized to report their true probabilities. Participants in Round 1 will be graded based on the average probability-of-being-generated-by-a-computer assigned to their string by Round 2 participants. The higher this number, the better a participant did.

Prizes

Prizes will be of the form “I will donate $X to a charitable organization of your choice”, subject to my approval (e.g. I won’t donate to the Trump Foundation). At least $75 will be donated to charity through this contest, and at least $150 (possibly more) if both rounds end up with 10 or more participants. (This means that by participating, you’re causing more money to go to charity in expectation!) I haven’t decided exactly how that will be distributed, but my inclination is to give more prize money to Round 2 winners, since that round is more time-consuming.

More details

• People may participate in both rounds. In fact, participants in Round 1 will have a small advantage in Round 2, since they will be able to say 0% for the string they submitted.
  • To make the contest incentive-compatible, in Round 2 you will be able to indicate which string from Round 1 is yours. The probability you submit for that string (i.e. probably 0%) will not count toward your Round 1 grade (so your Round 2 submission doesn’t penalize your Round 1 submission).
  • Probabilities in Round 2 will be normalized in some way to add to n, so that there isn’t an incentive to say 0 to everything if you’re really keen on winning Round 1.
• In Round 1, the rules allow you to e.g. use the digits of Pi to come up with random numbers. You’re allowed to do this, but I advise you against it because Round 2 participants will be on the lookout!

How to participate

Use this form! (I ask for your email address so you can get a receipt with your submission, so I can let you know when Round 2 is available, and so I can contact you if you win a prize. Email addresses will be kept private.)

Questions?

Comment below my blog post!

20 comments

Comments sorted by top scores.