Sharedstatistics of random permutations.sagewsOpen in CoCalc
Author: Paul Zeitz
Views : 4

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!