3
$\begingroup$

We are given a number $n$ and a vector $p=(p_1,p_2,\ldots,p_r)$, where $$p_1\geq p_2 \geq \ldots \geq p_r > 0 ; \ \ \ \ \sum_{i\in [r]} p_i \leq 1$$

I'm interested in proving that a solution for the following set of equation exist (the variables here are $t_1,t_2,\ldots, t_r$, all non-negative): $$\begin{cases} p_i\cdot (1-(1-t_i)^n)\cdot t_{i+1}=p_{i+1}\cdot (1-(1-t_{i+1})^n)\cdot t_{i} & & & &\forall i\in [r-1] \\ \sum_{i\in [r]}t_i=1\end{cases}$$

Or equivalently:

$$\begin{cases} p_i\cdot \sum_{k=0}^{n-1}(1-t_i)^k\ \ \ =\ \ \ p_{i+1}\cdot \sum_{k=0}^{n-1}(1-t_{i+1})^k & & & &\forall i\in [r-1]:t_i>0 \\ \sum_{i\in [r]}t_i=1\end{cases}$$

So my questions are:

1. Is there always a solution $t$ for this set of equations?

2. If not, can we characterize when (i.e. for which inputs $n,p$) such solution exist?

3. (least important) In which cases such solution can be found efficiently (computationally)?


A few observations about this problem:

  • If $n=2$, this is gives a set of $r$ linearly-independent linear equations, hence a solution exist and can be found efficiently.

  • If $r=2$ (two variables) then this reduces to this question (for $p_2=1-p_1$), although now I'm also interested in a solution existence, which is true for $r=2$, but I'm not sure about general $r$. As a result of the discussion on the other question, I believe efficient computation for the general problem would be hard, but I'm wondering what about the existence of a solution.

$\endgroup$
  • $\begingroup$ What is $p_i[1-t_i^n]$? $\endgroup$ – Emil Jeřábek Nov 30 '14 at 15:39
  • $\begingroup$ @EmilJeřábek - the $p_i$'s are given, the $t_i's$ are the variables and I meant the product of $p_i$ and $1 - t_i\ ^n$. I've edited the question, hope this is clear now, thanks. $\endgroup$ – R B Nov 30 '14 at 15:42
  • $\begingroup$ Oh I see, so these are just brackets. $\endgroup$ – Emil Jeřábek Nov 30 '14 at 15:47
  • 1
    $\begingroup$ In your second system, shouldn't there be $(1-t_i)^k$ instead of $(t_i)^k$? $\endgroup$ – Ilya Bogdanov Nov 30 '14 at 15:59
  • 1
    $\begingroup$ You do not mind if some $t_i$ are negative, do you? $\endgroup$ – fedja Nov 30 '14 at 18:14
5
$\begingroup$

Assuming $p_r>0$, your problem has at most a solution with all $t_i>0$, and it admits a solution provided the $p_i$'s are not too dispersed, in a sense to be made precise below.

Consider the polynomial $f(t):=\frac{1-(1-t)^n}{t}$. It defines a strictly decreasing homeo $[0,1]\rightarrow [1,n]$ (because it is the incremental ratio of a concave function), and your system writes $p_i f(t_i)=p_{i+1} f(t_{i+1}),$ for $i=1,\dots, r-1$. So it has at most one strictly positive solution, given by $t_i=f^{-1}(\lambda/p_i)$, where $\lambda$ solves $$ p_1\le\lambda \le n p_r $$ $$\sum_{i=0}^rf^{-1}(\lambda/p_i)=1.$$ Since the LHS in the latter equation is strictly decreasing, a sufficient condition for existence is then expressed on the $p_i$'s, requiring
$$ p_1\le n p_r $$ and $$\sum_{i=0}^rf^{-1}(np_r /p_i)\le 1 .$$

$\endgroup$
  • $\begingroup$ Note that assuming $p_r>0$ (hence $p_i>0$ for all $i$) implies that no $t_i$ can vanish, so we didn't loose solutions. If some $p_i$ vanishes, a small discussion is required, but in general uniqueness drops (e.g., if all $p_i$ vanish) . $\endgroup$ – Pietro Majer Dec 1 '14 at 11:26
  • $\begingroup$ I think that $p_r\geq \frac{p_1}{n}$ is what makes sure $t_r$ doesn't vanish, doesn't it? It might also suggest that a solution is still unique, where $t_i=0$ for all $i$ such that $p_i\geq \frac{p_1}{n}$ . $\endgroup$ – R B Dec 1 '14 at 12:40
  • $\begingroup$ Actually, consider the following input: $p_1=p_2=\frac{4}{11}$, $p_3=\frac{3}{11}$ and $n=2$. This gives us $t_1=t_2=0.5$ and $t_3=0$, despite the fact that $p_3\geq \frac{p_1}{2}$. What am I missing? $\endgroup$ – R B Dec 1 '14 at 13:06
  • $\begingroup$ You are right: writing the equations $p_{i}f(t_i) =p_{i+1 }f(t_{i+1}) $ excludes the case where some $t_i$ vanishes. $\endgroup$ – Pietro Majer Dec 1 '14 at 13:47
  • $\begingroup$ So the complete discussion should take into account that some $t_{i_0}$ can be zero. It seems this has a double effect: it makes the ${i_0}$-th equation (and in case $i_0>0$, the ${i_0-1}$-th equation too) automatically satisfied. Moreover, $p_i f(t_i)$ must be constant only in any interval of $i$ corresponding to non-vanishing $t_i$. $\endgroup$ – Pietro Majer Dec 1 '14 at 14:08

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.