Re: Compare two methods of random permutations

Date	2013-05-15 07:11 -0700
From	Patricia Shanahan <pats@acm.org>
Newsgroups	comp.programming
Subject	Re: Compare two methods of random permutations
References	(6 earlier) <kmsu34$gog$1@news.albasani.net> <54db95d6-bb50-4f91-8080-da2dcfb94624@a16g2000pbu.googlegroups.com> <kmu7qe$fba$1@news.albasani.net> <5fc07033-c260-4f44-99e8-1341596b5182@h9g2000pbr.googlegroups.com> <925e0863-2757-4c0f-881b-b169be8d5c35@h9g2000pbr.googlegroups.com>
Message-ID	<csSdndTRgvcICg7MnZ2dnUVZ_vednZ2d@earthlink.com> (permalink)

Show all headers | View raw

On 5/14/2013 3:06 PM, James Dow Allen wrote:
> On May 15, 4:19 am, James Dow Allen <jdallen2...@yahoo.com> wrote:
>> On May 15, 3:46 am, Mok-Kong Shen <mok-kong.s...@t-online.de> wrote:
>>
>>> I am confused. In which follow-up did you mention your code?
>> https://groups.google.com/group/comp.programming/msg/38c32bb27f26201a...
>>
>> James
>
> And, the reason I've been brusque or snippy in this thread is that
> I EXPLAINED THIS TO YOU FOUR YEARS AGO, with you refusing to
> take a few seconds to understand it.
> https://groups.google.com/group/comp.programming/msg/da8573d12cad698f?dmode=source
>
> You claimed then the method didn't work.
> You were wrong then.  You're still wrong.
> Shall be bet money?

The objection back then was "Anyway, I doubt the usefulness of % here,
since, if t is uniformly distributed in [0, n-1], then for m<n the
values t mod m wouldn't be uniformly distributed in [0, m-1]
in general, if I don't err."

That seems to me to be a good point. Suppose, for example that n is 16,
and m is 7. The results of the % for each value of t are:

0 -> 0
1 -> 1
2 -> 2
3 -> 3
4 -> 4
5 -> 5
6 -> 6
7 -> 0
8 -> 1
9 -> 2
10 -> 3
11 -> 4
12 -> 5
13 -> 6
14 -> 0
15 -> 1

Three inputs map to each of 0 and 1, but only two inputs map to each of
the other values. If t were uniformly distributed over [0,15] then t%7
would not be uniformly distributed.

The % method does work correctly if m is a factor of n.

java.util.Random contains code to correct for this effect in its
nextInt(int).

Patricia

Thread

Compare two methods of random permutations Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-05-08 23:35 +0200
  Re: Compare two methods of random permutations James Dow Allen <jdallen2000@yahoo.com> - 2013-05-11 21:31 -0700
    Re: Compare two methods of random permutations Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-05-13 08:07 +0200
      Re: Compare two methods of random permutations James Dow Allen <jdallen2000@yahoo.com> - 2013-05-13 02:34 -0700
  Re: Compare two methods of random permutations Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-05-13 08:01 +0200
  Re: Compare two methods of random permutations bob <bob@coolfone.comze.com> - 2013-05-13 08:26 -0700
    Re: Compare two methods of random permutations James Dow Allen <jdallen2000@yahoo.com> - 2013-05-13 11:42 -0700
      Re: Compare two methods of random permutations bob <bob@coolfone.comze.com> - 2013-05-16 13:46 -0700
    Re: Compare two methods of random permutations Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-05-13 21:09 +0200
      Re: Compare two methods of random permutations bob <bob@coolfone.comze.com> - 2013-05-13 12:57 -0700
        Re: Compare two methods of random permutations Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-05-13 22:59 +0200
          Re: Compare two methods of random permutations bob <bob@coolfone.comze.com> - 2013-05-13 15:28 -0700
            Re: Compare two methods of random permutations Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-05-14 10:54 +0200
              Re: Compare two methods of random permutations James Dow Allen <jdallen2000@yahoo.com> - 2013-05-14 05:32 -0700
                Re: Compare two methods of random permutations Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-05-14 22:46 +0200
                Re: Compare two methods of random permutations James Dow Allen <jdallen2000@yahoo.com> - 2013-05-14 14:19 -0700
                Re: Compare two methods of random permutations James Dow Allen <jdallen2000@yahoo.com> - 2013-05-14 15:06 -0700
                Re: Compare two methods of random permutations Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-05-15 10:16 +0200
                Re: Compare two methods of random permutations James Dow Allen <jdallen2000@yahoo.com> - 2013-05-15 03:54 -0700
                Re: Compare two methods of random permutations Patricia Shanahan <pats@acm.org> - 2013-05-15 07:11 -0700
                Re: Compare two methods of random permutations James Dow Allen <jdallen2000@yahoo.com> - 2013-05-15 11:04 -0700
                Re: Compare two methods of random permutations James Dow Allen <jdallen2000@yahoo.com> - 2013-05-15 11:06 -0700
                Re: Compare two methods of random permutations Patricia Shanahan <pats@acm.org> - 2013-05-15 12:55 -0700
                Re: Compare two methods of random permutations "Chris Uppal" <chris.uppal@metagnostic.REMOVE-THIS.org> - 2013-05-16 06:10 +0100
                Re: Compare two methods of random permutations pacman@kosh.dhis.org (Alan Curry) - 2013-05-16 06:57 +0000
                Re: Compare two methods of random permutations "Chris Uppal" <chris.uppal@metagnostic.REMOVE-THIS.org> - 2013-05-16 09:26 +0100
                Re: Compare two methods of random permutations James Dow Allen <jdallen2000@yahoo.com> - 2013-05-16 01:35 -0700
                Re: Compare two methods of random permutations Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-05-17 14:11 +0200
                Re: Compare two methods of random permutations James Dow Allen <jdallen2000@yahoo.com> - 2013-05-17 08:13 -0700
                Re: Compare two methods of random permutations Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-05-19 11:06 +0200
                Re: Compare two methods of random permutations James Dow Allen <jdallen2000@yahoo.com> - 2013-05-19 03:14 -0700
                Re: Compare two methods of random permutations Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-05-19 13:26 +0200
                Re: Compare two methods of random permutations James Dow Allen <jdallen2000@yahoo.com> - 2013-05-19 04:59 -0700
                Re: Compare two methods of random permutations Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-05-19 14:13 +0200
                Re: Compare two methods of random permutations James Dow Allen <jdallen2000@yahoo.com> - 2013-05-19 05:52 -0700
                Re: Compare two methods of random permutations Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-05-19 15:06 +0200
                Re: Compare two methods of random permutations James Dow Allen <jdallen2000@yahoo.com> - 2013-05-19 06:50 -0700
                Re: Compare two methods of random permutations Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-05-19 16:14 +0200
                Re: Compare two methods of random permutations James Dow Allen <jdallen2000@yahoo.com> - 2013-05-19 08:11 -0700
                Re: Compare two methods of random permutations Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-05-19 17:15 +0200
                Re: Compare two methods of random permutations Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-05-19 17:24 +0200

csiph-web