Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris
 
PerlMonks  

Re: Random Math Question

by Dominus (Parson)
on Oct 11, 2005 at 00:58 UTC ( [id://498993]=note: print w/replies, xml ) Need Help??


in reply to Random Math Question

Said Limbic~Region:
I figured that it would be nearly impossible to tell the difference between a "truly" randomization of the list and one that resulted from many of my re-orderings. ... Unfortunately, he didn't know of one at that moment.

Something I meant to say on IRC, but didn't get to, was that I don't think your question here was exactly well-posed. Suppose someone asked you if you would be able to distinguish a true random number from one that was only pseudo-random. Of course, you can't; the question isn't really sensical. The question they need to be asking in that case is whether you would be able to tell a sequence of random numbers from a sequence of pseudo-random numbers. And in that case the answer is that yes, methods for doing that are well-studied.

So the question I think you need to ask here is whether a sequence of arrays shuffled by your method would be distinguishable from a sequence of arrays shuffled into truly random orders. And having thought about it a little more (but just a little) I think the answer is probably yes; you could apply analogs of many of the usual statistical tests for randomness to such arrays, and find out that actually the method you were using wasn't very random at all.

Section 3.3 of Knuth's The Art of Computer Programming goes into these tests in great detail.

Setion 3.4.2 discusses random shuffling methods, including the Fisher-Yates algorithm, and then says:

R. Salfi has pointed out that Algorithm P cannot possibly generate more than m distinct permutations when we obtain the uniform U's with a linear congruential sequence of modulus m, or indeed whenever we use a recurrence Un+1 = f(Un) for which Un can take only m different values, because the final permutation in such cases is entirely determined by the value of the first U that is generated. Thus for example, if m = 232, certain permutations of 13 elements will never occur, since 13! ≅ 1.42 × 232.

This was exactly my concern when I originally said that generating truly random permutations was impossible with the pseudorandom generators supplied with most programming languages, including Perl. The space of permutations is just too big. However, Knuth continues:

Section 3.5 shows that we need not despair about this.
I haven't read section 3.5 in a long time, and I don't have time to pore over it now to figure out what Knuth meant by that, unfortunately. So I really don't know what the situation is.

Replies are listed 'Best First'.
Re^2: Random Math Question
by Limbic~Region (Chancellor) on Oct 11, 2005 at 12:17 UTC
    Dominus,
    So the question I think you need to ask here is whether a sequence of arrays shuffled by your method would be distinguishable from a sequence of arrays shuffled into truly random orders.

    Oh, I totally agree now that I have had a night's rest and a few good replies. It was one of those things where, in trying to make a convincing argument, I lost sight of the forest through the trees. As I indicated in another reply, I considered changing the method to change what elements appeared in each group for every iteration. Without that change, it should be easy to see that the re-ordering isn't random.

    I don't mind being wrong for the sake of a good discussion.

    Cheers - L~R

      Said Limbic~Region:
      As I indicated in another reply, I considered changing the method to change what elements appeared in each group for every iteration. Without that change, it should be easy to see that the re-ordering isn't random.
      As I kept saying on IRC, it doesn't matter how you change the method, because the results won't be random regardless of what method you choose. If you only have enough entropy to randomize 8 things, and you try to generate random permutations of 64 things, you are not going to be able to generate all possible permutations.

      You asked for a method that I could use to tell that your method wasn't working. Here's one: give me a sample of 200,000 of the "randomized" 64-element lists. You said "(Assume we have 64 elements in our list but only enough entropy to truly randomize 8)." Then I can tell there's something fishy because the sample you gave me will have lots of duplicate lists in it. You have only about log(8!) = 15.3 bits of entropy, so in the 200,000 items, there will be several that appear five times each. But the probability of such an occurrence in a truly random sample of 200,000 shuffled lists is about 10-356. So it'll be totally obvious that you're cheating.

      This will be true regardless of what clever method you are using to mix up the items. You can't get blood from a stone. As I said last night, what you're doing is like taking a 16-bit PRNG and then using it to generate 32-bit numbers by concatenating two 16-bit numbers together. If you hand someone a list of your "random" 32-bit numbers, it will be clear that they aren't really random.

        Dominus,
        I think you read more into what I was saying then I intended. Emphasis should have been on the fact that the process I outlined would be trivial to recognize as not being randomly distributed. The point of my reply was to say I recognize that not only was the process I outlined flawed but it wasn't even a good fake. Changing the process could make it harder to detect but that wasn't the point of my reply.

        Your proposal for determining the fake is in alignment with other responses. Unfortunately, it requires multiple lists to be generated where I was asking for only 1. 1 list is obviously not statistically valid so my question was flawed. For the benefit of others I am going to characterize the problem one more time but rest assured I have no argument with what you are saying.

        Cheers - L~R

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://498993]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others perusing the Monastery: (5)
As of 2024-03-28 15:22 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found