Re: Expected average cycle length...

From: Ariel Shaqed (ascolnic_at_checkpoint.com)
Date: 09/20/04 

Date: 20 Sep 2004 14:31:45 +0300

Bryan Olson <fakeaddress@nowhere.org> writes:

> Giorgio wrote:
> > given an RC4/n function the expected average cycle length is 2^M-1,
> > being M the internal memory size
>
> That's not really known. 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.

I believe this is not really true. First, only one permutation has
cycle length 1 (the identity). But it really is a nonuniform
distribution. For instance, in S4 (permutations on 4 elements), the
cycle lengths are (permutations written as cycles):

len=1: id

len=2: (12) and similar (6 possibilities), (12)(34), (13)(24),
(14)(23), total 9

len=3: (123) and similar (6 possibilities)

len=4: (1234) and similar (8 possibilities)

By my count, the expected cycle length on 4 elements is 2.875.

[...] 

-- 
This message may contain confidential and/or proprietary information, and
is intended only for the person/entity to whom it was originally addressed.
The content of this message may contain private views and opinions which do
not constitute a formal disclosure or commitment unless specifically stated.

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...
    ... cycle lengths are equally likely. ... RC-4 is far from a random permutation, ... The index variables always start the same, ...
    (sci.crypt)
  • Re: Expected average cycle length...
    ... > in a random permutation of N elements, all N cycle lengths are ... Using the first definition, for the case of S4, you get 1.92. ... To me, the second definition seems more reasonable, since we want to know ...
    (sci.crypt)
Quantcast