tag.py

#!/usr/bin/env python3

import random

def simulate(num_players):
  players = { i : [] for i in range(num_players) }
  tags = 0
  while len(players) > 1:
    tags += 1
    (tagger, taggee) = random.sample(players.keys(), 2)
    players[tagger].append(taggee)
    players.update((freed, []) for freed in players[taggee])
    del players[taggee]
  return tags

def avg(f, trials):
  return sum(f() for i in range(trials)) * 1.0 / trials

for num_players in range(2, 20):
  print(num_players, avg(lambda: simulate(num_players), 1000))

timed output

2 1.0
3 3.018
4 7.078
5 15.953
6 30.996
7 64.136
8 136.031
9 254.142
10 492.412
11 1027.277
12 2020.237
13 4232.717
14 7942.278
15 16759.458
16 32543.98
17 66329.466
18 129592.514
19 250361.027
2252.90user 0.00system 37:32.91elapsed 100%CPU (0avgtext+0avgdata 10108maxresident)k
0inputs+0outputs (0major+1067minor)pagefaults 0swaps