Re: Q: Algorithm M vs. P of Knuth's book

From: Mok-Kong Shen (mok-kong.shen_at_t-online.de)
Date: 04/06/04 

Date: Tue, 06 Apr 2004 10:15:58 +0200

Bryan Olson wrote:

> Mok-Kong Shen wrote:
>
> > Bryan Olson wrote:
> >> Mok-Kong Shen wrote:
> >> > On the other hand, in common card games, a packet
> >> > of cards is permuted and then distributed to the players
> >> > (mod 4) in a sequential manner. (I have never played such
> >> > games but have observed this.) Do you think there is
> >> > certain 'bias' arising from the kind of arguments you
> >> > employed in comparing the two ways of shuffling in
> >> > our context that could eventually also be exploited
> >> > in card games? (I don't think so.) If not, why not?
> >>
> >> This strikes me as an extremely naive question. Card games
> >> assume a random permutation of the cards. Does he really not
> >> know the difference between a random sequence and a random
> >> permutation? How could he have read the reference he cited and
> >> still not know?
>
> > My point in the last section quoted is that a random
> > permutation, e.g. applied to cards, is good because
> > (trivially, by definition) it scrambles a sequence to
> > another sequence in such a manner that the relationship
> > between the two is hard to be determined for any purpose
> > of exploitation (e.g. by the card players). So, if one
> > has an output sequence from a PRNG, having subsequences
> > of it (of sufficiently large length, which will be
> > commonly larger than 52 of the card games) individually
> > scrambled (with Algorithm P) should be (as extrapolation
> > from the example of card games) good enough for our
> > purpose, even though it is, strictly speaking, non-perfect.
>
> Then I gave Shen too much credit when I called the question
> "extremely naive". Given what he now says his point was, the
> question about biases exploitable in card games was nonsensical
> garbage.
>
> Note that I am not snipping any mathematical or scientific
> justification of this "point"; there simply was none.

I don't understand you. Note that what you said of the
probabilities depends on the size of the array. As the size
of the arrays become larger, the effect you pointed out
becomes less significant for 'practical' purposes. (In the
'extreme' case, where all one needs is n scrambled units,
applying algorithm P with an array of size n is the only
best way of doing things, if I don't err.)

>
> > Note anyway that the PRNG used to shuffle (whether for
> > algorithm M or P) couldn't be 'perfect'. Further, while
> > Algorithm P is theoretically (i.e. with a 'perfect'
> > PRNG) perfect for 'its' purpose (i.e. scrambling restricted
> > to the region of the array), I am not yet sure that Algorithm
> > M is theoreticall perfect for 'its' purpose (i.e. referring
> > to an unbounded output sequence). So, any exaggerated
> > theoretical points in the present case possibly aren't
> > appropriate in the first place in my view.
>
> So why does he concoct such exaggerated theoretical terms? He's
> "not yet sure that Algorithm M is theoreticall perfect". Where
> does he get this stuff?

If I don't err, Knuth wrote somewhere that a problem with
Algorithm M is that it is barely susceptible to exact
analysis (or something in that vein). In contrast, Algorithm
P is conceptually simply understandable, isn't it?

>
> > Thus, returning
> > to the question I posed in my original article, I would
> > venture to say that for most practical situations the
> > effects of the two different ways of scrambling seem to be
> > comparable.
>
> So in favor of the algorithms in Knuth, we have some analysis
> indicating they are superior; for Shen's alternative, we have
> him venturing to say they seem comparable to him, with no
> justification and no sign of any effort examining the issue.

See above.

BTW, I like to note that you tend (as always) to put into
your comments a large proportion of 'personal' stuff. Are
you not able to express the scientific content of your
arguments in a way without such matters?? For that
unnecessarily increases the bandwidth. (It should be
possible to find scientific truth in a completely neutral
way.)

M. K. Shen
----------------------------------------

Should not we, then, exert ourselves to do good?

     (From Tai Shang Kan Ying Pien.
      Probable author: Ko Hung, 4th century A.D.)

Relevant Pages

  • Re: YAPL - Yet Another Programming Language
    ... array for an out of order pair, swapping them then checking the array ... Can the algorithm be re-written to avoid the goto and remain as clear. ... construct that makes one sequential pass through a sequence. ...
    (comp.programming)
  • Q: Algorithm M vs. P of Knuths book
    ... One could render a sequence of numbers (typically from ... a PRNG) in some sense more random by shuffling it through ... an array according to Algorithm M of Knuth vol.2. ...
    (comp.programming)
  • Q: Algorithm M vs. P of Knuths book
    ... One could render a sequence of numbers (typically from ... a PRNG) in some sense more random by shuffling it through ... an array according to Algorithm M of Knuth vol.2. ...
    (sci.crypt)
  • Compiled in D5.1 but fails on D6
    ... "answer the edit distance between the reciever and the, aComparand. ... An OSequence Comparison Algorithm ... The main change I've made is to ensure that array N is larger than array M, ...
    (comp.lang.smalltalk.dolphin)
  • Re: Chex Wat: Pi is "random" and "not predictable"?
    ... their output sequence. ... The fact is that an algorithm can also be used to ... first was about the probability of finding an apparent match. ... They may be matched within e at an infinite ...
    (talk.origins)
Quantcast