Existence of solutions of a polynomial system

Question

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

Answer 1

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).

Answer 2

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.

Answer 3

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