# Random Permutations and Expected Average Length of Cycles

*Brian Li*

*2020-05-27*

*MAT388 Random Permutations Mathematics*

## # What is a Cycle?

**Definition**: An **m-cycle** in

**Example 2.0**: Let

**Example 2.1**: Let **fixed point**. We express this permutation as

**Application 2.0**: A "perfect shuffle" is performed by splitting a deck of cards into exactly two halves and interlocking the cards so that the cards from the

- The top card from B ending up on the top in the shuffled deck (Faro In Shuffle)
- The top card from A ending up on the top in the shuffled deck (Faro Out Shuffle)

Surprisingly, these two methods yield very different outcomes. By applying Out Shuffle, we need to perform 52 identical shuffles to reach the starting position. However, if we apply Out Shuffle, we would only need 8 shuffles to accomplish the same goal. Let us examine these two shuffle method:

- By applying Fro In Shuffle (The top card from B ending up on the top in the shuffled deck), after one shuffle, we have:

```
(27 1 28 2 29 3 30 4 31 5 32 6 33 7 34 8 35 9 36 10 37 11 38 12 39 13 40 14 41 15 42 16 43 17 44 18 45 19 46 20 47 21 48 22 49 23 50 24 51 25 52 26)
```

The cycle in this case is:

```
(1 27 40 20 10 5 29 41 47 50 25 39 46 23 38 19 36 18 9 31 42 21 37 45 49 51 52 26 13 33 43 48 24 12 6 3 28 14 7 30 15 34 17 35 44 22 11 32 16 8 4 2)
```

As we can see, we have one giant cycle with length 52. This means that to get card 1 back in the top position, it has to travel through each of the other positions in the cycle. Thus we have to repeat the shuffle 52 times to get each of the cards back to their starting positions.

- By applying Faro Out Shuffle (The top card from A ending up on the top in the shuffled deck), after one shuffle, we have:

```
(1 27 2 28 3 29 4 30 5 31 6 32 7 33 8 34 9 35 10 36 11 37 12 38 13 39 14 40 15 41 16 42 17 43 18 44 19 45 20 46 21 47 22 48 23 49 24 50 25 51 26 52)
```

The cycle in this case is:

```
(1) (2 27 14 33 17 9 5 3) (4 28 40 46 49 25 13 7) (6 29 15 8 30 41 21 11) (10 31 16 34 43 22 37 19) (12 32 42 47 24 38 45 23) (18 35) (20 36 44 48 50 51 26 39) (52)
```

We can see that there are two cycles of length 1, one cycle of length 2 and six cycles of length 8. Since

**Theorem 2.0**: The expected length (average length) of the largest cycle in a random permutation of an

**Experiement**: We currently do not have a formal proof for theorem 2.0, so instead we attempt to verify the theorem with the help of a Python program. First, we will need a function that output all the cycles in a permutation:

```
def get_cycles(ordered_set, random_comb):
"""this function list out the cycles in a permutation"""
"""my logic:
outer loop:
inner loop:
find what the current item goes to
add that to the cycle
set "current item" to that
stop when you get to the first item
add a list containing those items to the list of cycles
start again with an item you haven't used yet
keep going until the lists are empty (or only have one item)"""
perm = [ordered_set, random_comb]
cycle_list = []
possible_beginnings= perm[0].copy()
while True:
if len(possible_beginnings)<2:
break
start = possible_beginnings[0]
current = start
new = perm[1][perm[0].index(start)]
possible_beginnings.remove(start)
if start == new:
continue
cycle = [start,new]
current = new
while True:
possible_beginnings.remove(current)
current = perm[1][perm[0].index(current)]
if current == start:
break
cycle.append(current)
cycle_list.append(cycle)
return cycle_list + [get_fixed_pts(ordered_set, random_comb)]
```

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

Using the above function we can produce cycles of permutations such as:

```
get_cycles([1,2,3,4],[2,4,3,1])
>>> [[1, 2, 4], [3]]
```

2

Using the above function, let us first graph a plot of "number of cycles vs. length of cycles" with

Having data like this, it becomes quite easy to compute the average, and even the mean and mode of cycle length. After running some functions, we achieve the following results for

```
average = 20.68594596830913
median = 9.0
mode = 2
```

2

3

Notice that average length =

## # Conclusion and Extension

In this post, we have discussed random permutation, cycles, derangment and how they might be connected to card tricks and shuffling. We would like to make a hypothesis and ask a question here:

**Hypothesis 1**: The mode of the largest cycle in a random permutation of an n-element set is

**Question 1**: What is the median of length of the largest cycle in a random permutation of an n-element set?

These two hypothesis are being made only from an experimental point of view, meaning that it is deducted from observation using computer programs. However, we have not figured out ways to mathematically prove the hypothesis and hopefully readers can contribute to such process.