# Log Stochastic Algebra

Peano-style, we start with the successor or increment function.

In LSA, error is stochastic, hence automatically uncorrelated, which is a useful property downstream.

For convenience we define LSA values as integers in [0,255], e.g. unsigned bytes.
We use $w$ to represent an arbitrary LSA value (e.g. a weight).
LSA implies a base, which here is always 2.

## Semantics

A LSA value represents the log value of a count.
The expected error distribution is uniform across the range (in the log domain of the stored values).
Two LSA values are required to have uncorrelated error distributions, without coordination.
Holding the expected log error fixed we seek the smallest possible representation.
We choose $[1, 2^{255}]$ as a range with ample headroom above the evidence range and below the absolute range, and with a natural and very convenient representation as a byte.

The above desiderata fully constrain the design.

(To formalize this a bit: assume a random variable X that is exponentially distributed over the range $[1, 2^{255}]$; stipulate that the representation has a fixed expected error in the log domain; guarantee that the errors are uncorrelated for any two values; guarantee that the representation in the log domain is minimal and that there is no external state; the rest of the design necessarily follows.)

## Increment

The value $w$ is incremented by sampling $w$ bits of entropy, and giving $w + 1$ with probability $1 / 2^w$.

## The Zero

We note that allocating a value and setting it to zero represents an event count of $2^0 = 1$.

In application, this implies that values are allocated only for events that are asserted to be possible (e.g. corresponding to Laplacian smoothing) if seen as forward-looking.
If taken as observation counts, it only allows the representation of events observed at least once.

## The Absolute

The maximal value 255 (notionally corresponding to $2^{255}$ recorded observations) represents the strongest possible belief within the system.
Practically this creates a separate regime in which doubt remains representable and the interpretation under probability theory remains well-behaved, with a buffer from the evidence-based regime.
This creates a defensible approach to integrating a-priori with empirical beliefs.

## Algebraic operations

Addition of two values requires sampling bits of entropy which is a function of the difference between them; at worst we require $\sum_{n=0}^{\infty} n/2^n = 2$ bits per addition operation (in expectation) as we only need to sample bits until the result is known.
(We can also write this as $\sum_{n=0}^{\infty}1/2^n$.
One sums the total bits weighted by probability, the other is each subsequent bit times its probability conditioned on the previous bits.)

Subtraction ($a - b, b < a$) is similar; degenerate subtraction reduces to 0 but also generally indicates that something is wrong and could be flagged as a warning depending on the application.

Multiplication and division reduce to addition and subtraction in the log domain.

## Relation to probability

LSA variables which form an event space are interpretable as probabilities via softmax.