During computation of some Shapley values (details below), I encountered the following function:
f(∑k≥02−pk)=∑k≥01(pk+1)(pkk),
where p0>0 and pk+1>pk 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 pk 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⋅3)=7/12 and
f(2/3)=f(∑k≥02−(2k+1))=∑k≥01(2k+2)(2k+1k)=π√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∈[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≥1 be an integer and let t∈[0,1]. For a permutation π of the numbers {2−m:0≤m≤n−1} satisfying π−1(1)=i, we say that π is pivotal if $\sum_{j
For example, take n=4. The permutation 1/8,1/2,1,1/4 is pivotal for t∈(5/8,1]. For all n≥2 we have fn(1/2)=1/2, since π is pivotal iff 1 appears before 1/2 in π. The general formula for f is derived in a similar way.
We leave it to the reader to figure out how fn measures some Shapley value. The functions fn are step functions with steps of length 1/2n−1. They are left-continuous, and are equal to f at the breakpoints.
No comments:
Post a Comment