144
$\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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .