142
$\begingroup$

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 $1$s 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.

$\endgroup$
11
  • 27
    $\begingroup$ It seems spiritually related to the inverse of Minkowski's question mark function. $\endgroup$
    – user856
    Aug 18, 2013 at 8:06
  • 2
    $\begingroup$ I get $[f(x)-1/2] = [f(x/2)-1/2] + [f((x+1)/2)-1/2]$. $\endgroup$ Aug 18, 2013 at 21:16
  • 4
    $\begingroup$ @BrunoJoyal Since $f(t) + f(1-t) = 1$, the integral is $\int_0^1 f(t) dt = 1/2$. $\endgroup$ Apr 28, 2014 at 0:54
  • 3
    $\begingroup$ @Yuval: Based on the evidence, I conjecture that the higher moments are also rational. (I'm joking, but due to the apparent high degree of symmetry of your function, part of me wouldn't even be surprised - and the rest of me would be delighted!) $\endgroup$ Apr 28, 2014 at 1:12
  • 2
    $\begingroup$ @Yuval, I saw something similar when reviewing election strategies (as in Politics) in an election where people vote for a list of candidates, there is a number of places to be elected $N$ (say a senate), and lists get as many places as percentage votes won: $places = floor(N P_l)$. The tricky part was that there is a remanent after allocating all lists, as one cannot allocate a fraction of a place, an allocation then was from greatest residual to lowest. So, what's the best strategy, split the party in many lists or nominate a single one? Plotting, we arrive at something similar. $\endgroup$
    – carlosayam
    Jun 2, 2014 at 19:30

1 Answer 1

5
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.