Re: Expected average cycle length...

From: Johannes Borgström (johannes.borgstroem_at_epfl.ch)
Date: 09/21/04

  • Next message: Wannabee: "Re: 9-15-04" 
    Date: 21 Sep 2004 10:23:58 +0200

    This night, Bryan Olson wrote:
    > Johannes Borgström wrote:
    > > This afternoon, Ariel Shaqed wrote:
    > > > Bryan Olson writes:
    > > > > Starting from a random point in a
    > > > > random permutation of the M-bit vectors, all of the 2^M possible
    > > > > cycle lengths are equally likely. Thus the expected cycle length
    > > > > is (1 + 2^M) / 2 = 2^(M-1) + 1/2.
    >
    > Note that I phrased it to keep the notation of the preceding
    > post. More simply and generally: starting from a random point
    > in a random permutation of N elements, all N cycle lengths are
    > equally likely

    To me, this is still confusing. Do you mean the average
    "over all cycles
     of its length"
    or
    "over all permutations and elements
     of the length of the cycle the element is in"?
    or
    "over all permutations
     of the average cycle length of that permutation"

    Or something else?

    Using the first definition, for the case of S4, you get 1.92.
    With the second, you get 2.333...
    With the third, it is 2.291666...
    (barring calculation errors)

    How did you compute the following?
    > Make that 2.5.

    To me, the second definition seems more reasonable, since we want to know
    how long we expect to wait until we return to the current state.

    (And yes, this does not take into account the actual algorithm.)

    Best regards,
            /Johannes 

    -- 
Johannes Borgström                                 Cell: +41 765 77 03 21
Research Assistant at EPFL.I&C.LAMP.2              Work: +41 21 693 64 83
GCS/M d- s+:+ a- C++(++++) UBLS++ P+ L+ E+>++ W++ N++ o? K? w-(---) O- V?
M-(+) PS++ PE- Y++ PGP- t-- 5? X- R+ tv-- b+++@ DI+ D+ G e+++$>++++ h+ y?
  • Next message: Wannabee: "Re: 9-15-04"

    Relevant Pages

    • Re: "Interleave" permutation algorithm?
      ... So what would be a good in-place algorithm for this permutation? ... (defun interleave (vector) ... processing the vector cycle by cycle and avoiding storing moving ... (defun iota (count &optional start step) ...
      (comp.programming)
    • Re: Rearranging based on permutation of indices
      ... When you have a permutation, you can see it as a bunch of disjoint ... (loop; this loop returns the minimum i ... was in the permutation of the cycle. ... (defun permute-cycle (vector permutation cycle) ...
      (comp.programming)
    • Re: looking for random array reshuffling algorithm
      ... >) based on n and reverse it back to n and is as ... >) chaotic as possible and has a very big cycle period. ... >- A permutation can be subdivided into a number of cycles. ... Right now i use a sequence of pre-defined functions to ...
      (comp.programming)
    • Re: Expected average cycle length...
      ... > random permutation of the M-bit vectors, ... > cycle lengths are equally likely. ... First, only one permutation has ... the expected cycle length on 4 elements is 2.875. ...
      (sci.crypt)
    • Quantcast