12
$\begingroup$

Fix $k \in \mathbb{N}$, $k \geq 1$. Let $p \in [0,1]$ and $x = (x_0, \ldots, x_k)$ be a $(k+1)$-dimensional real vector, and define $$S(p,x) = -x_0^2 + \sum_{i=0}^k {k \choose i} p^i (1 - p)^{k - i} \cdot (x_i - p)^2.$$ Experiments show that for small values of $k$ $$\exists x \in \mathbb{R}^{k+1} \,.\, \forall p \in [0,1] \,.\, S(p,x) = 0.$$ In other words, there are $x_i$'s such that $S(x,p)$ is identically zero as a polynomial in $p$.

For a given $k$ we can expand $S(x,p)$ as a polynomial in $p$ and equate the coefficients to $0$. For $k = 2$ we get \begin{align*} 0&=0 \\ -x_0^2-2 x_0+x_1^2&=0 \\ 2 x_0-2 x_1+1&=0 \\ \end{align*} and this has two solutions: $$x = (\frac{1}{2} (-1-\sqrt{2}),\frac{1}{2},\frac{1}{2} (3+\sqrt{2}))$$ and $$x = (\frac{1}{2} (-1+\sqrt{2}),\frac{1}{2},\frac{1}{2} (3-\sqrt{2})).$$ For $k = 1, 2, 3, 4, 5, 6, 7$ there are $1, 2, 4, 8, 14, 28, 48$ solutions respectively, according to Mathematica. According to OEIS this is A068912, "the number of $n$ step walks (each step $\pm 1$ starting from $0$) which are never more than $3$ or less than $-3$." This is kind of interesting because the problem arises in statistics, see John Mount's blog post for background.

Question: Is there a solution for every $k$?

Addendum: John says he wants soltions in $[0,1]^{k+1}$...


Here is the relevant Mathematica code:

s[k_, p_, x_] := Sum[Binomial[k, i] * p^i* (1 - p)^(k - i)* (Subscript[x, i] - p)^2, {i, 0, k}]  Subscript[x, 0]^2
xs[k_] := Table[Subscript[x, i], {i, 0, k}]
system[k_, p_, x_] := Thread[CoefficientList[s[k, p, x], p] == 0]
solutions[k_] := Solve[system[k, p, x], xs[k], Reals]

To see the system of equations for $k = 4$, type

system[4, p, x] // ColumnForm

To see the solutions for $k = 4$, type

solutions[4]

To make a table of counts of solutions up to $k = 7$, type

Table[{k, Length@solutions[k]}, {k, 1, 7}] // ColumnForm
$\endgroup$
  • $\begingroup$ In other words, we have a family of one-sheeted hyperboloids $$ \sum_{i=1}^k {k \choose i} p^{i-1} (1 - p)^{k - i-1}(x_i-p)^2 - \frac{1}{1-p}(x_0-(p-1))^2 = 1 $$ in $\mathbb{R}^{k+1}$ parametrised by $p \in [0,1]$ and we want to know whether there is a point lying in all of them at once. $\endgroup$ – Vít Tuček Aug 1 '14 at 13:09
  • 1
    $\begingroup$ The polynomial $S(p,x)$ is actually divisible by $p$, which means that we have a well defined mapping $\mathbb{R}^{k+1} \to \mathbb{R}^{k+1}$. This allows us to use topological methods such as this one: en.wikipedia.org/wiki/… $\endgroup$ – Vít Tuček Aug 1 '14 at 13:32
  • 1
    $\begingroup$ Did you try to express $S(p,x)$ in terms of Bernstein basis? Can Mathematica handle that at least for some small $k$? $\endgroup$ – Vít Tuček Aug 1 '14 at 13:40
  • $\begingroup$ Always $x_k=1\pm x_0$, so for solutions in $[0,1]^{k+1}$ it must be that $x_k=1-x_0$. This can continue to $x_{k-1}$ and so on, but I don't know how to see that it remains real, let alone in $[0,1]$. $\endgroup$ – Brendan McKay Aug 2 '14 at 4:11
6
$\begingroup$

The solutions described via the link http://winvector.github.io/freq/explicitSolution.html (posted in one of the earlier answers) can be given by the following formula: $$ x_i=\frac{(k-2i)\sqrt{k}+(2i-1)k}{2k(k-1)}=\frac{1}{2(1+\sqrt{k})}+\frac{i}{\sqrt{k}(1+\sqrt{k})}. $$ Note that (when $k$ is fixed):

  • $x_i$ is an increasing function of $i$, and we have $$ x_0=\frac{1}{2(1+\sqrt{k})}, \quad x_k=\frac{1+2\sqrt{k}}{2+2\sqrt{k}}, $$
    so all these numbers are between 0 and 1.

  • Moreover, we have $x_i=a+bi$, so $S(p,x)$ can be represented as $$ -x_0^2+\sum_{i=0}^k\binom{k}{i}p^i(1-p)^{k-i}(U+Vi+Wi^2), $$ where $U$, $V$ and $W$ depend on $k$ and $p$ but not on $i$. It remains to use formulas \begin{gather} \sum_{i=0}^k\binom{k}{i}p^i(1-p)^{k-i}=1,\\ \sum_{i=0}^k i\binom{k}{i}p^i(1-p)^{k-i}=kp,\\ \sum_{i=0}^k i(i-1)\binom{k}{i}p^i(1-p)^{k-i}=k(k-1)p^2 \end{gather} (which are obvious) to check directly that the formulas for $x_i$ as above give a solution.

This solution also simplifies to $x_i = (\frac{1}{2}\sqrt{k} + i)/(\sqrt{k}+k)$ which is exactly the smoothed estimate of the win-rate of a coin flipped $k$ times showing $i$ wins with $\sqrt{k}$ "pseudo-observations" (half wins, half losses) added first (or Bayesian inference starting with $\beta(\sqrt{k}/2,\sqrt{k}/2)$ priors, $\beta(1/2,1/2)$ being Jeffreys priors, and $\beta(1,1)$ being standard Laplace smoothing).

$\endgroup$
3
$\begingroup$

This is not a solution but some background to the question.

Define $$S(k,p,x) = \sum_{i=0}^k {k \choose i} p^i (1-p)^{k-i} (x_i-p)^2.$$ Define $$f(k) = \mathrm{argmin}_x \max_p S(k,p,x).$$ Then $f(k)$ is the minimax square-loss solution to trying to estimate the win rate of a random process by observing $k$ results (Wald wrote on this). The neat thing is: we can show if there is a real solution $x$ in the interior of $[0,1]^{k+1}$ to $S(k,p,x) = x_0^2$ then $x=f(k)$. Meaning we avoided two nasty quantifiers. See this file for some experimental examples. Also, a change of variables $z = p/(1-p)$ makes collecting terms easier.

$\endgroup$
  • $\begingroup$ I hope my edits didn't spoil anything. Except, here $S$ does not have the $-x_0^2$ term, but that doesn't matter when we're just looking for extrema. $\endgroup$ – Andrej Bauer Aug 1 '14 at 17:37
  • 1
    $\begingroup$ A note to user56665: instead of editing John Mount's answer to the question to give your observations, just submit them as a second answer. $\endgroup$ – Jeremy Rouse Aug 4 '14 at 20:16
  • 1
    $\begingroup$ (I may well be mistaken, but the wording of the edits makes me think that 56665 is John Mount.) $\endgroup$ – Emil Jeřábek Aug 4 '14 at 20:40
2
$\begingroup$

Having trouble formatting. Here is a [line of attack][1] . Also a [proof of the problem mapping][2]. Apparently I am both user 56-something and "John Mount" but have lost control of at least one of those accounts.


[1] http://winvector.github.io/freq/explicitSolution.html [2] http://winvector.github.io/freq/minimax.pdf

$\endgroup$
  • 2
    $\begingroup$ You should try using it through not-iPhone. $\endgroup$ – Andrej Bauer Aug 5 '14 at 8:21
  • 1
    $\begingroup$ Yeah, sorry about the iPhone bits. It seems to have created an account I can't get control of that posted the other answer. Vladimir Dotsenko's observation that the $x_i$ are evenly spaced was really awesome though. Much simpler than I expected. $\endgroup$ – John Mount Aug 5 '14 at 21:56
  • $\begingroup$ John, I have put in a request to merge the other account (unregistered) into the one used to post this answer (registered). $\endgroup$ – Todd Trimble Aug 5 '14 at 23:56
  • 1
    $\begingroup$ @JohnMount: and now that you're on Mathoverflow, make sure statistics and probability are your favorite tags, and help answer some questions! $\endgroup$ – Andrej Bauer Aug 6 '14 at 9:14

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.