129
$\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.

$\endgroup$
  • 27
    $\begingroup$ It seems spiritually related to the inverse of Minkowski's question mark function. $\endgroup$ – Rahul Aug 18 '13 at 8:06
  • 2
    $\begingroup$ I get $[f(x)-1/2] = [f(x/2)-1/2] + [f((x+1)/2)-1/2]$. $\endgroup$ – Yuval Filmus Aug 18 '13 at 21:16
  • 3
    $\begingroup$ @BrunoJoyal Since $f(t) + f(1-t) = 1$, the integral is $\int_0^1 f(t) dt = 1/2$. $\endgroup$ – Yuval Filmus Apr 28 '14 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$ – Bruno Joyal Apr 28 '14 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 '14 at 19:30
3
$\begingroup$

It is an example of a singular function (generalized De Rahm curve).

You can try to identify the contraction maps http://www.linas.org/math/de_Rham.pdf

http://en.wikipedia.org/wiki/De_Rham_curve

https://www.encyclopediaofmath.org/index.php/Singular_function

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