Concept

Random function

A function from a finite set to itself chosen uniformly from all possible functions. Iterating it from any start must eventually cycle, and the typical tail and cycle lengths grow like the square root of the set's size.

Named by 2 essays across 2 fields — each of them below, with the objects they name alongside it.

Four seeds of the middle-square method, each until it repeats. Values against step for the four-digit seeds 6239, 1234, 5735, 4100 under the middle-square rule, each ending where a value repeats: after 111, 57, 31, 4 steps.

Square it and keep the middle

John von Neumann's first generator of random numbers squared a number and kept its middle digits. Followed from every four-digit seed, it never lasts more than 111 steps before a value repeats — a third of what the birthday problem allows a truly random rule — and one seed in five ends at zero for ever. A counter added before each squaring cures the collapse.

computation · Pseudorandomness

A function on nine points, and the tree with two marks it becomes. Left: a function on 9 points as arrows, with cycles through 2, 5, 7 and trees hanging into them. Right: the tree Joyal's rule makes from it, a path from head 7 to tail 2 with the same trees hanging below.

Every function is a tree with two marks

There are n to the n functions from n points to themselves, and n to the n − 2 trees on those points. André Joyal noticed in 1981 that the missing factor of n² is a choice of two points — a head and a tail — and that a function, read the right way, simply is a tree with a head and a tail. The reading turns Cayley's formula into one line and hands over a fact about random trees from the birthday problem.

discrete · Labelled trees

Named alongside it

The objects these essays reach for when they reach for this one.

Birthday problem Exhaustive search Bijection Collision Counting two ways Cycle Expectation Fixed point Iteration Labelled tree Orbit Periodic orbit

All concepts