Блог пользователя nchn27

Автор nchn27, история, 5 лет назад, По-английски

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?

  • Проголосовать: нравится
  • +14
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

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.

»
5 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

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}$$$.

»
5 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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?