During computation of some Shapley values (details below), I encountered the following function:
f\left(\sum_{k \geq 0} 2^{-p_k}\right) = \sum_{k \geq 0} \frac{1}{(p_k+1)\binom{p_k}{k}},
where p_0 > 0 and p_{k+1} > p_k for all k. In other words, the input to f is the binary expansion of a real number in the range [0,1], and the p_k correspond to the positions of 1s in the binary expansion.
For example, f(2^{-t}) = 1/(t+1), so f(1/2) = 1/2, f(1/4) = 1/3 and so on. More complicated examples are f(5/8) = f(2^{-1} + 2^{-3}) = 1/2 + 1/(4\cdot 3) = 7/12 and
f(2/3) = f\left(\sum_{k \geq 0}2^{-(2k+1)}\right) = \sum_{k \geq 0} \frac{1}{(2k+2)\binom{2k+1}{k}} = \frac{\pi}{\sqrt{27}}.
The function f is a continuous increasing function satisfying f(0) = 0, f(1) = 1, and f(1-t) = 1-f(t) for t \in [0,1]. It has vertical asymptotes at dyadic points.
Here is a plot of f:
Is the function f known?
Here is where f came from. Let n \geq 1 be an integer and let t \in [0,1]. For a permutation \pi of the numbers \{ 2^{-m} : 0 \leq m \leq n-1 \} satisfying \pi^{-1}(1) = i, we say that \pi is pivotal if $\sum_{j
For example, take n = 4. The permutation 1/8,1/2,1,1/4 is pivotal for t \in (5/8,1]. For all n \geq 2 we have f_n(1/2) = 1/2, since \pi is pivotal iff 1 appears before 1/2 in \pi. The general formula for f is derived in a similar way.
We leave it to the reader to figure out how f_n measures some Shapley value. The functions f_n are step functions with steps of length 1/2^{n-1}. They are left-continuous, and are equal to f at the breakpoints.
No comments:
Post a Comment