Identification of a curious function

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: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<i} \pi(j) < t. Let f_n(t) be the probability that a random \pi is pivotal. Then f(t) = \lim_{n \rightarrow \infty} f_n(t).

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.

This question was also asked on MO.


It is an example of a Singular Function (Generalized De Rahm curve).
You can try to identify the contraction maps.

Source : Link , Question Author : Yuval Filmus , Answer Author : islamm

Leave a Comment