Statisfaction

Clone wars inside the uniform random variable

Posted in General by Pierre Jacob on 25 September 2013

Hello,

In a recent post Nicolas discussed some limitation of pseudo-random number generation. On a related note there’s  a feature of random variables that I find close to mystical.

In an on-going work with Alex Thiery, we had to precisely define the notion of randomized algorithms at some point, and we essentially followed Keane and O’Brien [1994] (as it happens there’s an article today on arXiv that also is related, maybe, or not). The difficulty comes with the randomness. We can think of a deterministic algorithm as a good old function mapping an input space to an output space, but a random algorithm  adds some randomness over a deterministic scheme (in an accept-reject step for instance, or a random stopping criterion), so that given fixed inputs the output might still vary. One way to formalise it consists in defining the algorithm as a deterministic function of inputs and of a source of randomness; that randomness is represented by  a single random variable U e.g. following an uniform distribution.

The funny, mystical and disturbing thing is that a single uniform random variable is enough to represent an infinity of them. It sounds like an excerpt of the Vedas, doesn’t it? To see this, write a single uniform realization in binary representation. That is, for U \in [0,1] write

U = \sum_{k> 0} b_k 2^{-k}

with b_k = \mbox{floor}(2^k U) \mbox{ mod } 2. The binary representation is b_1b_2b_3b_4b_5\ldots

Realization of an uniform r.v. in binary representation

Realization of an uniform random variable in binary representation

Now it’s easy to see that these zeros and ones are distributed as independent Bernoulli variables. Now we put these digits in a particular position, as follows.

Same zeros and ones ordered in an increasing square

Same zeros and ones ordered in a triangle of increasing size

If we take each column or each row from the grid above, they’re independent and they’re also binary representations of uniform random variables – you could also consider diagonals or more funky patterns. You could say that the random variable contains an infinity of independent clones.

This property actually sounds dangerous now, come to think of it. I think it was always well-known but people might not have made the link with Star Wars. In the end I’m happy to stick with harmless pseudo-random numbers, for safety reasons.

About these ads

2 Responses

Subscribe to comments with RSS.

  1. Julyan Arbel said, on 2 October 2013 at 11:00

    This grid is also used to prove that natural numbers N and rational numbers Q are equinumerous (have the same cardinality), remember? like this one: http://serge.mehl.free.fr/anx/anx_gif/denomb3.gif
    Scary indeed!

  2. xi'an said, on 22 October 2013 at 18:57

    I am not that scared… And my computer even less.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 50 other followers

%d bloggers like this: