In a recent team building exercise at work, a group of people (including myself) was asked to quantify themselves in various ways. For example: “What outdoor temperature do you prefer?” No one reveals their answer at first. Instead, each person places a card with their name on an unmarked line, one at a time. In this example, folks who prefer higher temperatures would place their names farther right; folks who prefer lower temperatures would place their names farther left. However, the line is unmarked and doesn’t have any units.
Once all the names are placed on the line, their values are revealed. For example, a group of six might have generated the following numbers, in order from left to right on the line: 60, 67, 65, 74, 70, 80.
The team’s score is the length of the “longest increasing subsequence.” In other words, it’s the maximum number of elements in the list you can keep such that they form an increasing subsequence. In the example above, you can remove the 67 and the 74 to get the following increasing subsequence with four numbers: 60, 65, 70, 80. There are a few other ways to get an increasing subsequence of length four, but there’s no way to get a sequence of length five or more, so the team’s score is four.
Suppose a total of four people are participating in this team building exercise. They all write down different numbers, and then independently place their names at random positions on the line.
On average, what do you expect the team’s score to be?
I considered teams of size $n$.
For the $k^\text{th}$ person in the team, denote their preferred temperature as $t_k$.
WLOG, assume $t_1 < t_2 < t_3 < \ldots < t_n$.
They will always have a maximum subsequence of $t_1$, which is the sequence.
$$\boxed{\text{average score} = 1}$$There are 2 possibilities:
There are 6 possibilities:
There are 24 possibilities:
Instead of four people, now suppose there are 10 people participating in the team building exercise. As before, they all write down different numbers, and then independently place their names at random positions on the line.
On average, what do you expect the team’s score to be?
Using $1 \le n \le 4$ from above, I noticed a few patterns. One way of looking at this problem is considering how adding a new team member (with the highest temperature preference, as stated above) creates a new sequence.
For any $n$:
Let the average maximum subsequence for $n$ team members be $EV_n$.
As a result of the above, $EV_n \lt EV_{n+1} \lt 2\cdot EV_n$.
Let the total number of maximum subsequence increases be $SI_{n+1}$.
$$EV_{n+1} = EV_n + \frac{SI_{n+1}}{(n+1)!}$$The number of maximum subsequence increases for $1 \le n \le 6$ is summarized below.
| $n$ | 1st | 2nd | 3rd | 4th | 5th | 6th | $SI_n$ | $EV_n$ |
|---|---|---|---|---|---|---|---|---|
| $1$ | $0$ | $1$ | $\frac{1}{1}$ | |||||
| $2$ | $0$ | $1$ | $1$ | $\frac{3}{2}$ | ||||
| $3$ | $0$ | $1$ | $2$ | $3$ | $\frac{12}{6}$ | |||
| $4$ | $0$ | $1$ | $3$ | $6$ | $10$ | $\frac{58}{24}$ | ||
| $5$ | $0$ | $1$ | $5$ | $15$ | $24$ | $45$ | $\frac{335}{120}$ | |
| $6$ | $0$ | $1$ | $8$ | $40$ | $75$ | $120$ | $251$ | $\frac{2261}{720}$ |
$SI_n$ is A006220.
The numerator of $EV_n$ is A003316.
I wrote code that did the following :
For $10$ team members,
$$\boxed{\text{average score} = \frac{15,730,705}{10!} \approx 4.33496}$$