nchn27's blog

Cycles in a classic team-building activity
By nchn27, history, 5 years ago, In English

A common team-building activity goes like this:

There are N people, each holding hands with two other distinct random people.

How many expected cycles are there? Is there a name for this problem? Can anybody link related math or computer science resources?

  • Vote: I like it
  • +14
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Suppose each person is a vertex and every hand is an edge, and we can also assume that every right hand holds someone else's left hand. If the right hand is a directed edge outwards of the vertex (left hand inwards), we can see that this problem is equal to the expected number of cycles in a permutation, which is easier to google.

→ Reply
»
5 years ago, # |
  Vote: I like it +20 Vote: I do not like it

As Noam527 correctly pointed out, this is equivalent to having random permutation. If you focus on cycle containing one you can easily see that for every k=1,..., n there is $$$\frac{1}{n}$$$ probability it has length $$$k$$$. From that you can easily derive that expected number of cycle is $$$H_n = \frac{1}{1} + \frac{1}{2} + \ldots + \frac{1}{n}$$$.

→ Reply
»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

In such team-building exercises, there is normally a check to make sure there are no cycles of size 2 or 3 before starting (usually to increase the difficulty). How would we tackle the problem from here?

→ Reply