Matpic
mathematics, in pictures
Concept

Recurrence relation

A rule giving each term of a sequence from the terms before it, with enough starting values to begin.

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

020406080024681012stepsstakethe table's limitruin00.2500.5000.750102.5057.5010starting stakechance of ruin0.58average length from 5: 35 stepsa fair game against a table of 12, started at 5: ruin comes with probability 0.583, which is 7 in 12and the game lasts 35 steps on average — the product of the two stakes, which is why a small player against a largeone is ruined quickly rather than slowly

Two barriers and a fair game

A fair walk between two absorbing barriers is ruined with a probability that is a straight line in the starting stake, and lasts for a number of steps that is the product of what each side can lose. Both facts come from the same two-line recurrence, and both are bad news for the smaller player.

probability · random walk the graphone edge deletedthe same edge contractedcoloursthe graphdeletedcontracted0000100020223618124488436518026080a four-cycle with one chord: every count is made by trying all k^4 assignments and checking each onethe graph needs 3 colours, and below that the count is not small — it is zero, which is what a countingversion of the question says instead of yes or no

Counting the colourings

Asking whether a graph can be coloured with four colours gives a yes or a no. Asking how many ways there are gives a polynomial — and the polynomial answers the first question, and several others nobody asked.

discrete · graph colouring

Named alongside it

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

Absorbing stateChromatic numberChromatic polynomialCountingDeletion contractionExpectationGamblers ruinGraph colouringMarkov chainMartingalePolynomialRandom walk

All concepts