The only precise definition of "random" that seems possible is if every possible permutation of the list is equiprobable. Which means that the minimum number of bits of entropy you need is log2(100_000!), because if you had any less then there will be at least one permutation that is not derived from one of the seeds, and thus is not equiprobable.

That's a big number. Um... quick google search on "factorial approximation" shows that ln(100_000!) is about 100_000*ln(100_000)-100_000, and e is about 2, so you need about 100_000*ln(100_000) which is about 1.2 million bits.

That's really not all that much information -- but way more than a computer can typically provide in a short amount of time. It's not a language issue; in fact, it's more of a hardware issue. Just like us, computers can only perceive the world through external devices (senses), and so they can't "make up" bits of entropy (aka truly random numbers) on their own. They need some sort of device that feeds in bits of entropy gradually from thermal noise or whatever.

Linux implements this, in the form of /dev/random. It pulls entropy from IRQ timings, mouse movements, keyboard event interarrival times, and more stuff that I don't understand. I see one person who made his disks go crazy to measure the rate of entropy "production", and he saw 1-1.5 KB/sec. So that would take 20 minutes to come up with enough bits to randomize your list of 100_000 things. Not infeasible, though most applications would rather not wait that long!

Of course, such truly random numbers generally aren't distinguishable from good pseudorandom numbers, so I wanted to mention my favorite way of gauging randomness:

In the early, early days of the web, I stumbled across a site (I think it was an HTML site; can't remember for sure) with a random number contest. People would send in their opinions of the "most random number" between 1 and 100, and after a suitable period of time waiting for all submissions, the winner would be announced -- whichever number was chosen by the fewest submitters.

Works for me.

I work for Reactrix Systems, and am willing to admit it.

In reply to Re: Random Math Question by sfink
in thread Random Math Question by Limbic~Region

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.