One can intuitively imagine picking a random natural number and ask to what extent the intuition can be axiomatized.
Using the axiom of choice, there is a total finitely additive (monotonic) averaging function $μ$ on sequences of nonnegative real numbers, extending $\lim_{n→∞} \frac{1}{n} \sum_{i=1}^{n} x_i$. Such $μ$ also yields a finitely additive non-atomic probability measure on $ℕ$. However, we work with $μ$ here since without countable additivity, the probability measure only suffices to recover $μ$ for sequences of bounded real numbers.
There does not appear to be a single natural choice of $μ$, but the lack of natural $μ$ is not obvious especially if we only need $μ$ for (for example) computable sequences, and any case we can ask which symmetry principles a hypothetical natural $μ$ would satisfy, and then consider their consequences.
Question: Is there literature on this topic?
Note: A survey on finitely additive non-atomic probability measures on $ℕ$ would also work even if it does not discuss naturalness. Among else, I am looking for which symmetry properties $μ$ can or cannot have. I am also interested in arguments (on either side) on whether natural preferred $μ$ exists for (for example) computable sequences.
Update: I had hoped that a good survey might answer these and more, but I also have two specific questions.
- Does $μ$ exist that satisfies the basic symmetry principles (especially (2)) below?
- If in addition CH (the Continuum Hypothesis) holds, is there such $μ$ that is also representable as described below in "$μ$ as a limit of measures"?
My notes are below.
Basic symmetry principles
Call a strictly monotonic sequence of natural numbers $n_1,n_2,...\,$ $μ$-equally spaced if there is a function $f:ℕ→ℝ_{>0}$ such that $μ(x_i:i∈ℕ) = μ(\frac{\sum_{j=n_k}^{n_{k+1}-1} f(j) \, x_j}{\sum_{j=n_k}^{n_{k+1}-1} f(j)}:k∈ℕ)$ (using 0 in place of $n_0$, but we do not care about finite initial segments).
For typical sequences used in practice, $μ$ is fixed if we assume the following basic symmetry principles (which are based on translation and scale invariance):
- For every $k>0$, $k,2k,3k,...$ is $μ$-equally spaced with constant $f$.
- For every $k>0$, $k,2k,4k,8k,...$ is $μ$-equally spaced with $f(n)=1/n \; (n>0)$.
Notes:
- (2) implies (1). The choice of the exponentiation base (i.e. 2) is immaterial.
- The summation process of recursively using (2) (what is its name?) corresponds to averaging using one of $1, 1/n, 1/(n \log n), 1/(n \log n \log \log n),...$ as weights.
- To augment (2), we can specify that $μ(x)=∞$ if $\sum \frac{x_n}{n^2}=∞$; with (2), using $n^2$ is equivalent to using $n^{\log n}$ or $n \log^{1+ε} n$.
- One also wants $μ(x)$ to be monotonic in $(\sum_{i=0}^n x_i : n∈ℕ)$.
$μ$ as a limit of measures: Under CH (or if the dominating number is $ω_1$), I think an appropriate $μ$ can be represented as a limit of a sequence of $ω_1$ unnormalized atomic measures $μ_α$ with $∀x:ℕ→ℝ_{≥0} \, \displaystyle{\lim_{α→ω_1}} μ_α^\inf (x) = \displaystyle{\lim_{α→ω_1}} μ_α^\sup (x)$ (with $∞=∞$ here) and $∀α ∀β \, (α<β<ω_1) \, ∀x:ℕ→ℝ_{≥0} \, μ_α^\inf (x) ≤ μ_β^\inf (x) ≤ μ(x) ≤ μ_β^\sup (x) ≤ μ_α^\sup (x)$, where $μ_α^\inf (x) = \displaystyle{\liminf_{n→∞}} \frac{\sum_{i=0}^{n} x_i μ_α(i)}{\sum_{i=0}^{n} μ_α(i)}$ and analogously with $μ_α^\sup$.
Fractional exponentiation: For appropriate $μ$, we can define the corresponding fractional exponentiation as follows. Let $p = μ([n,r) ∪ [2^n,2^r) ∪ [2^{2^n},2^{2^r}) ∪ ...)$ with $n<r<2^n$ (and using the indicator function for integers in the intervals), and define the $p$th iteration of exponentiation base 2 starting with $n$ to equal $r$. Thus, finding natural fractional exponential growth rates (see my old questions here and here) is a subquestion of finding natural $μ$. Unlike exponentiation, tetration base $a>1$ is not analytic except possibly for a single $a$, or rather if a definition of tetration base $a$ is analytic, then using it to define tetration base $b≠a$ gives a non-analytic function. Plausibly, there are no natural fractional exponential growth rates. However, that does not stop us from listing some desired symmetry principles for $μ$.
Further symmetry principles for $μ$: To the extent that we have canonical fundamental sequences for ordinals, we can postulate that $f_α$ gives $μ$-equally spaced values, where $f_α$ uses the fast-growing hierarchy of functions. We can also postulate that the extension (using $μ$) of $f_α$ to non-integral arguments and its inverse are smooth. Using this, for every $n$, $n, 2^n, 2^{2^n}, ...$ is $μ$-equally spaced. We can also postulate that appropriate nonrecursive functions (such as the iterated busy beaver function) give $μ$-equally spaced values.
An attempt at finding $μ$: One may try to define $μ$ (on a restricted class of sequences) by identifying a sufficiently pseudorandom process that produces unbounded integers. For example, given a random-enough sample, we can apply $\log_2$ until all values are in $[c,2^c)$, and then use the distribution of those values to define fractional exponentiation. However, I could not find any such pseudorandom processes. Even if we use $B^{-1}(B_2(n))$ where $B$ is the busy-beaver function, and $B_2$ is busy-beaver with $0'$ oracle, the resulting values need not be pseudorandom.
