Is there a verifiable way to generate discrete random variables on the basis of an external event?

Question

Suppose that we want to generate a draw from the following distribution:

$P(X=0) = 0.5$

$P(X=1) = 0.5$

There are two constraints though:

(a) The draw has to be on the basis of an external event.

(b) Related to (a), the draw must be verifiable by a third party. In other words, a third party should be able to verify that my draw was in fact $X = 0$ (say).

Qn 1: Can such a system be devised and if so how?

Qn 2: Can the system be extended to discrete variables with more than 2 possible outcomes (like the roll of a dice)?

Qn 3: Similarly, can it be extended to continuous variables (e.g., the normal)?

Answer 1

Just as another source of verifiable randomness: random.org generates random numbers from atmospheric noise. They publish a daily file (most days) of random bits; the first digit of each day's file might prove suitably verifiable to your parties.

---

Update 2013-11-12: Access to these files is now restricted, but it looks like you can email random.org's operators to gain access:

Note: Access to the pregenerated files is currently restricted due to bandwidth considerations. Let us know (contact@random.org) if you require access.

Answer 2

Many countries have state lottery which is regularly audited, and whose results are announced online: e.g. UK national lottery. You just need to construct an appropriate function which maps this output space to your desired output.

A continuous distribution would be more tricky, but you could obtain a discrete approximation: in the UK case there are ${}^{49}C_6 \times 43$ = 601 304 088 equally likely outcomes, which, depending on context, could give sufficient granularity.

Answer 3

This reminds me of a question from Algorithms class a long time ago. Let the external event be a (preferrably continuous) random variable $Y$. To generate a value of $X$, take two independent observations of $Y$ and let $X$ be $1$ if the first observation of $Y$ is greater than the second, let it be $0$ if the second is greater than the first, and repeat the experiment if there is a tie. Obviously, this works better if $Y$ is continuous. If only a coinflip is available as a generator, one can let the number of consecutive heads before seeing a tail be the random variable $Y$. (The homework question, I believe, was how to turn a biased coinflip into an unbiased coinflip. One part of the homework was proving that the process would terminate...)

This obviously can be extended to the discrete case as well, although one may run into more difficulties with ties. If you have $n$ possible outcomes for $X$, take some $k$ such that $n$ divides $k!$ and then partition the $k!$ possible orderings of $k$ observations from $Y$ into equivalence classes for $X$.

edit: per @srikant's comment, an example of a possible generator of $Y$: (as anticipated by @andyW) Let $Z_i$ be the number of shares traded on a given highly-liquid ETF as reported by a given source over a fixed time period unambiguously indexed by $i$. Let $Y_i = \tan{(Z_i)},$ where the tangent function is computed by a fixed standard library (in a fixed revision of R, say, on a fixed platform.) Such a generator of $Y$ is pseudorandom enough for me. Other generators of $Z$ are also amenable to this process if they vary widely enough with respect to $2\pi$.

Answer 4

I didn't quite understand what you meant by "on the basis of an external event." But you can certainly flip a fair coin in a manner that a remote user can cryptographically verify.

Consider this algorithm:

1. Bob picks a uniformly random boolean value, TRUE or FALSE. He also chooses a large random number. He sends Alice the SHA-256 hash of the boolean value concatenated with the number. (E.g. he sends the hash of "TRUE|12345678".) Since Alice doesn't know the random number and the hash is one-way, Alice doesn't know the boolean value.
2. Alice flips a coin and sends Bob the value -- TRUE or FALSE.
3. Bob reveals the random number, and thus his own boolean value. Alice verifies that the boolean value and the random number indeed hash to the value she received earlier.
4. This final output of the coin flip is the exclusive-or of Alice's boolean value and Bob's boolean value.

With this algorithm, no party can cheat without the cooperation of the counterparty. If either party plays fairly, the output will be a uniform random boolean value.

(EDIT) I now understand the problem to mean you have no internal source of nondeterminism at all, so all randomness has to come from an external source and the algorithm has to be deterministic. In that case, we can still use cryptography to help.

How about taking the SHA-256 of the PDF version of The New York Times every day, or the SHA-256 of the volume and closing price of all the stocks in the Dow Jones Industrial Average in alphabetical order by ticker symbol, or really the secure hash of anything that can be mutually observed and that you can't influence. If you want just one bit, take the first bit of the SHA-256.

If you want a normal distribution, you could take the whole thing in two parts (128 bits, then 128 bits) as two uniform deviates and use the Box-Muller transform to get two normal deviates.

Answer 5

an easy way to generate symmetric bernoulli trials is to flip a coin twice. if the first toss is H and the second is T, say X = 1. if it's the other way round, say X = 0. if the two tosses match [2H or 2T], discard the outcome and continue. no matter what the bias of the coin, X will be symmetric bernoulli.