statistics of random permutations.sagews

Here is some code for analyzing the questions raised in your first Sage homework.

#############################
# 1. Average number of cycles
#############################
# we will look at SymmetricGroup(n) for various values of n
nValues = [5,10, 20, 50, 100, 200, 1000]
nTrials = 500 #we will take 500 samples of random permutations for each n

for n in nValues:
    
    G = SymmetricGroup(n)
    total = 0 # sum of cycle lents 
    for _ in range(nTrials):
        t = G.random_element()
        tc = t.cycle_tuples()
        total += len(tc) #add to total
    avg = float(total/nTrials)  #compute average
    averageCycleLengths.append(avg) #store average in list
    # now print results
    print n, avg

5 1.256 10 1.892 20 2.562 50 3.358 100 4.362 200 5.07 1000 6.516

# It looks vaguely logarithmic, as Sarah M. observed.

#############################
# 2. Probability of derangement
#############################

# A permutation is a derangement if it has no fixed points.  So we need a fixed point calculator function
def nFixedPts(perm,n):
    #it is understood that perm is an element of SymmetricGroup(n) 
    nFP=0 #this is the output which we will iterate
    for i in [1..n]:
        if perm(i)==i: 
            nFP += 1
    return nFP
    
# Now we do the same statistical analysis with the same values of n as in the previous problem
nValues = [5,10, 20, 50, 100, 200, 1000]
nTrials = 500 #we will take 500 samples of random permutations for each n

for n in nValues:
    G = SymmetricGroup(n)
    total = 0 # the number of derangements
    for _ in range(nTrials):
        t = G.random_element()
        if nFixedPts(t,n)==0: #a derangement!
            total += 1
    avg = float(total/nTrials)  #compute fraction of derangements
        
    # now print results
    print n, avg

5 0.39 10 0.338 20 0.362 50 0.382 100 0.356 200 0.394 1000 0.37

# Notice the surprising fact that the fraction of permutations that are derangements appears to be around 0.38 or so, independent of n!

#############################
# 3. average number of fixed points
#############################

#we already have the fixed point calculator function, so we can just apply it using virtually the same code.

nValues = [5,10, 20, 50, 100, 200, 1000]
nTrials = 500 #we will take 500 samples of random permutations for each n

for n in nValues:
    G = SymmetricGroup(n)
    total = 0 # the sum of number of fixed points
    for _ in range(nTrials):
        t = G.random_element()
        total += nFixedPts(t,n)
    avg = float(total/nTrials)  #compute average number of fixed points
        
    # now print results
    print n, avg

5 1.034 10 1.028 20 0.94 50 1.024 100 1.036 200 0.978 1000 0.926

# Once again, a surprising result:  the average number of fixed points seems to be 1, no matter what n is!