Permutation cycles
Patrick D. Rockwell
As I understand it, if you have a set (1...K)
the probability that a permutation on this set will have a cycle
whose size is at least K/2 is H(2K)-H(K) and as K goes to infinity,
H(2K)-H(K) goes to ln(2).
What if you wanted to know the probability of a permutation
on this set having a cycle that is at least K/3?
would that be H(3K)-H(2K)?
If the answer is yes, then, if you wanted the probability
of such a cycle being equal to 2K/3, then would it be
H(3K)-H(K)?
Thanks for any information on this.
Henry
>... if you wanted the probability
> of such a cycle being equal to 2K/3, then would it be
>
> H(3K)-H(K)?
No, since H(3K) - H(K) > 1 for K >= 4
and so is not a probability
Similarly ln(3) = 1.0986... > 1
Patrick D. Rockwell
Ok, but what about the first part of my question. Would
H(3K)-H(2K) be the probability that a cycle on the set (1...K)
is at least K/3 in size? If not, can anyone tell me how to get
that probability? From what I've seen, H(a*K)-H(b*K) =
ln(a/b) as K goes to infinity.
I'm interested in this because I love probability and I found
an interesting problem at
http://en.wikipedia.org/wiki/Random_permutation_statistics#One_hundred_prisoners
It's called the "One Hundred Prisoners" problem which is a classic
problem in
random permutation statistics.
Henry
> On Nov 10, 3:27 am, Henry <s...@btinternet.com> wrote:
>
> > On 10 Nov, 05:23, "Patrick D. Rockwell" <prockw...@thegrid.net> wrote:
>
> > >... if you wanted the probability
> > > of such a cycle being equal to 2K/3, then would it be
>
> > > H(3K)-H(K)?
>
> > No, since H(3K) - H(K) > 1 for K >= 4
> > and so is not a probability
>
> > Similarly ln(3) = 1.0986... > 1
>
> Ok, but what about the first part of my question. Would
> H(3K)-H(2K) be the probability that a cycle on the set (1...K)
> is at least K/3 in size? If not, can anyone tell me how to get
> that probability? From what I've seen, H(a*K)-H(b*K) =
> ln(a/b) as K goes to infinity.
>
> I'm interested in this because I love probability and I found
> an interesting problem at
>
>
> It's called the "One Hundred Prisoners" problem which is a classic
> problem in
> random permutation statistics.
You might want to look at
http://www.research.att.com/~njas/sequences/A126074
and
http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/challenges/December2006.html
(and its solution)
It is much easier to calculate and approximate these numbers where you
are looking at a longest cycle which is more than half the total,
since there cannot be more than one of them.
As for H(n), this is about ln(n) + 0.5772... ("gamma") for large n, so
H(m)-H(n) is about ln(m/n) for large m and n.
Patrick D. Rockwell
> On 10 Nov, 23:39, "Patrick D. Rockwell" <prockw...@thegrid.net> wrote:
>
>
>
>
>
> > On Nov 10, 3:27 am, Henry <s...@btinternet.com> wrote:
>
> > > On 10 Nov, 05:23, "Patrick D. Rockwell" <prockw...@thegrid.net> wrote:
>
> > > >... if you wanted the probability
> > > > of such a cycle being equal to 2K/3, then would it be
>
> > > > H(3K)-H(K)?
>
> > > No, since H(3K) - H(K) > 1 for K >= 4
> > > and so is not a probability
>
> > > Similarly ln(3) = 1.0986... > 1
>
> > Ok, but what about the first part of my question. Would
> > H(3K)-H(2K) be the probability that a cycle on the set (1...K)
> > is at least K/3 in size? If not, can anyone tell me how to get
> > that probability? From what I've seen, H(a*K)-H(b*K) =
> > ln(a/b) as K goes to infinity.
>
> > I'm interested in this because I love probability and I found
> > an interesting problem at
>
> >http://en.wikipedia.org/wiki/Random_permutation_statistics#One_hundre...
>
> > It's called the "One Hundred Prisoners" problem which is a classic
> > problem in
> > random permutation statistics.
>
> You might want to look athttp://www.research.att.com/~njas/sequences/A126074
> (and its solution)
>
> It is much easier to calculate and approximate these numbers where you
> are looking at a longest cycle which is more than half the total,
> since there cannot be more than one of them.
>
> As for H(n), this is about ln(n) + 0.5772... ("gamma") for large n, so
>
> - Show quoted text -
Well, according to the wikia page that I listed,
Pk[probability that there is a cycle of length k] is 1/k so, my
reasoning
is that if you wanted to know the probability of
p(there is a cycle >k), then for 12 variables, it would be
1/12+1/11+1/10+1/9
which is equal to H(12)-H(8)
The page is here.
http://en.wikipedia.org/wiki/Random_permutation_statistics
They did it for k=2 to get the probability of there being a cycle
greater than n/2.
Chip Eastham
>
> They did it for k=2 to get the probability of there being a cycle
> greater than n/2.
For clarity, the Wikipedia article calculates the
probability that a permutation of 2n things has a
cycle of length greater than n.
Notice that for n < i,j <= 2n, i not equal to j,
the event that a permutation contains a cycle of
length i is mutually exclusive of the event of
a cycle of length j; both cannot occur. Thus the
addition of probabilities applies.
When one asks about chances that a permutation of
3n things has a cycle of length greater than n, the
corresponding events are not mutually exclusive,
and their probabilities cannot be added to obtain
the chance of their disjunction.
The effect is that some cases would get double
counted if we proceed naively as before. Indeed
the double counting produces H(3n) - H(n) tending
to ln(3), which as Henry points out is greater
than 1.
Notice that the example you last gave involved a
permutation of 12 items, and you wrote that "it
would be":
1/12+1/11+1/10+1/9 = H(12) - H(8)
This is neither an example of H(3n) - H(n) nor
H(2n) - H(n). Instead you seem to be asking for
a probability a permutation contains a cycle of
length more than 2/3rds the number of items. If
that is your intent, then mutual exclusion will
apply (two-thirds being more than one-half).
regards, chip
Patrick D. Rockwell
>
> - Show quoted text -
Actually, I should have specified that my intent was
H(3n)-H(2n) where n=4 in the example that I gave.
The formula they gave on the wikipeida page for
P(There is a cycle > N) for 2N objects is
C(2n,k)*(k!/k)*(2n-k)!/(2n!) = 1/k
I looked at it and realized that if you replace the 2 with S (for
size)
the formula would still reduce to (1/k), but I guess I still made an
error in my reasoning somewhere.
Chip Eastham
Hi, Patrick:
Well, that works then (since 2n > 3n/2).
The argument only fails when the lower limit
on cycle length drops below half the number
of items permuted:
Pr(random permutation of 3n items has cycle
of length more than 2n) =
H(3n) - H(2n) --> ln(3/2) ~= 0.405465...
as n tends to infinity.
regards, chip