GoKawiilIn the very first post of this blog, I described a new measure of disorder which I called \(\mathit{Amp}\). I started its construction process by introducing what I dubbed the pairwise order of a sequence as follows:
A few days ago I went back to one of the simplest possible tools in the domain: a three-way comparator for two values: \[\mathit{comp}(x, y)= \begin{cases} 1 & \text{ if } x \lt y\\ -1 & \text{ if } x \gt y\\ 0 & \text{otherwise} \end{cases}\] Nothing ground-breaking so far, it’s similar to a negation of the sign function applied to the difference of two real numbers. Let’s apply it to all adjacent pairs of elements of a sequence of elements \(X\): Still fairly boring if I’m being honest. We will call that new sequence the pairwise order of the sequence for the rest of the article.
Today’s article is all about showing that this so-called pairwise order is, in fact, maybe not all that boring.
Definition(s) and properties
The definition above was spot-on when talking about the sign function and three-way comparisons. The “negation” part however felt a bit confusing upon rereading it: it seems to arbitrarily consider \(x - y\) instead of \(y - x\) without being explicit about it. I would rather describe it again as the sequence made of the sign function applied to the difference operator over a sequence of elements:
\[\forall X_i \in \mathbb{R}, \mathit{Order}(X) = \langle \text{sgn } (\Delta X)_i \vert 1 \le i < \lvert X \rvert \rangle\]
That new definition gets rid of the “negation” part, and the direction of the subtraction implicitly follows the definition of the difference operator.
When I showed the article to a friend, she immediately described the pairwise order it as “discrete derivative”. It also accurately matches the intuition of the tool, even though I managed to write the whole thing without ever thinking of derivatives. After all, the general definition is not about numbers but considers anything satisfying a strict weak ordering, as is usual in the realm of comparison sorts.
A few obvious properties of the pairwise order immediately emerge from its definition:
Its size: \(\lvert \mathit{Order}(X) \rvert = \lvert X \rvert - 1\).
... continue reading