6
$\begingroup$

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)?

$\endgroup$
  • 1
    $\begingroup$ what do you mean by 'verify'? does this mean the third party controls the external event? this would contradict the pmf here. $\endgroup$ – shabbychef Sep 21 '10 at 2:39
  • $\begingroup$ Obviously the third party should not control the external event for the question to make sense. As an example of what I mean, suppose we agree that the protocol is this: If it rains tomorrow in New York X=0 otherwise X=1. The draw is based on an external event and is verifiable in the sense that someone can check if it really rained post-facto. $\endgroup$ – user28 Sep 21 '10 at 2:58
  • $\begingroup$ How about white noise that you could record on some unused radio band? $\endgroup$ – TakenItEasy Sep 7 '14 at 21:18
6
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Tangent: Dirk Eddelbuettel wrote an R package (cran.r-project.org/web/packages/random/index.html) to access random numbers. Not verifiable, however. $\endgroup$ – Matt Parker Sep 22 '10 at 5:27
  • $\begingroup$ This works perfectly. $\endgroup$ – user28 Sep 22 '10 at 12:56
  • $\begingroup$ I can't access those text files... it requires username and password. $\endgroup$ – Muhd Nov 12 '13 at 2:22
  • $\begingroup$ Thanks for pointing that out, @Muhd. Looks like you can email for access, but this does make the files less useful. $\endgroup$ – Matt Parker Nov 12 '13 at 19:21
6
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ What would be a specific example for an external event that I could use for $Y$? $\endgroup$ – user28 Sep 21 '10 at 13:58
  • 1
    $\begingroup$ As an example I first thought of old numbers games where they used some decimal point of specific stock reports in the news paper. Of course you would worry about the true randomness of this metric though, so I imagine there are better examples. $\endgroup$ – Andy W Sep 21 '10 at 15:31
  • $\begingroup$ All you need is an accessible integer or collection of integers to work as seed to a pseudo-random generator and possibly as number of iterations of said pseudo-random generator. From which you can generate any distribution, discrete or continuous. $\endgroup$ – Xi'an Oct 18 '15 at 20:14
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I thought the meaning of 'external event' was clear. To clarify, because of the constraints imposed on the protocol, the external event should be the source of the random generation and the draw must be verifiable. Your answer addresses verifiability but not the external event part. Nevertheless, +1 for an interesting answer. Out of curiosity, doesn't the algorithm breakdown if both Bob and Alice cheat and report a value (0 or 1 as they choose) without flipping a coin? $\endgroup$ – user28 Sep 22 '10 at 19:09
  • $\begingroup$ Hi Srikant, yes, the algorithm requires at least one honest party. You have no internal source of randomness at all? Then you could take 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, or the really the secure hash of anything that can be mutually observed and that you can't influence. If you want one bit, take one bit of the SHA-256. If you want a normal distribution, take the whole thing (256 bits) as a uniform deviate and use the Box-Muller transform to get a normal deviate. $\endgroup$ – Keith Winstein Sep 23 '10 at 2:47
  • $\begingroup$ Yes, your modification using the hash of NYT/stock prices should also work although it has the one weakness of requiring at least 1 honest party. Interesting way to approach the issue. $\endgroup$ – user28 Sep 23 '10 at 3:06
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ But the question is: how would you verify that to someone on the other side of the world? See item b) in the question. $\endgroup$ – Matt Parker Sep 22 '10 at 5:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy