https://youtube.com/watch?v=OkmNXy7er84

cheaters.py

from random import random

people = 1
limit = 500000

while True:
	total = 0

	for iteration in range(limit):
		# Mutate
		choice = [0] * people
		for pointer in range(people):
			choice[pointer] = -1 if random() < 0.5 else 1

		# Count
		leaves = 0
		for pointer in range(people):
			if choice[(pointer - 1 + people) % people] < choice[(pointer + 1 + people) % people]:
				total += 1

	print(people, ":", total / limit)

	people += 1

notes.md

Firstly, the problem comes from the sponsor spot at the end of this video: https://youtube.com/watch?v=OkmNXy7er84

My intuition was that we don't really care much about the fact it is a circle, it just makes things easier. Really, all we care about if the node to the left if pointing away from us, and the node to the right is pointing away from us. If both are true then the current node is a leaf node, regardless of where it's pointing.

Given this, the left node has a 1/2 chance of pointing away from us, and the right node has a 1/2 chance of pointing away from us. Therefore, the probability of any given node being a leaf is 1/2 × 1/2 = 1/4.

Now we can just multiply the number of nodes in the circle by 1/4 to get the expected number of cheaters who aren't being copied from.

out.log

$ python3 cheaters.py | tee out.log
1 : 0.0
2 : 0.0
3 : 0.750094
4 : 1.000394
5 : 1.25038
6 : 1.500518
7 : 1.749778
8 : 2.000854
9 : 2.250044
10 : 2.500292
11 : 2.748766
12 : 3.000906
13 : 3.250236
14 : 3.498972
15 : 3.748704
16 : 3.999564