Inigo

Let me explain. No, there is too much. Let me sum up. ~ Inigo Montoya, The Princess Bride

An inigo or decaying history is a structure providing a stochastic summary over a sequence of objects. The main operations on an inigo are insertion of new objects and iteration over a summarized sequence of objects. Inigos were first documented by David M. Barbour [1] in 2013 and subsequently named by W. Allen Short.

Intuition

An inigo is a list of objects with a size bound. Insertion and iteration work as expected while the inigo is not full. However, once it is full, an inigo will respond to insertions by forgetting a previously-inserted object. All interesting properties of the inigo come from customizing which object is forgotten.

When the most recent insertion is forgotten, the inigo stores the oldest history. Dually, when the oldest insertion is forgotten, the inigo stores the newest history. In this sense, inigos generalize ring buffers.

We can use a PRNG to sample over the inigo from several standard distributions. Barbour originally proposed an exponential distribution, which turns inigos into exponentially-long summaries. Barbour also proposed combining adjacent objects instead of mere forgetting, as long as the combination can be computed quickly and stored in the same space as the original object; over the exponential distribution, this acts as an antialiasing filter. More generally, any gamma distribution can be used to give an exponentially-long summary which is weighted towards recent events when the parameter α < 1 or less-recent events when α > 1; α = 1 gives the exponential distribution.

Implementations

• In Python by Corbin: [2]