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$
11
  • $\begingroup$ What is $p_i[1-t_i^n]$? $\endgroup$ Nov 30, 2014 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, 2014 at 15:42
  • $\begingroup$ Oh I see, so these are just brackets. $\endgroup$ Nov 30, 2014 at 15:47
  • 1
    $\begingroup$ In your second system, shouldn't there be $(1-t_i)^k$ instead of $(t_i)^k$? $\endgroup$ Nov 30, 2014 at 15:59
  • 1
    $\begingroup$ You do not mind if some $t_i$ are negative, do you? $\endgroup$
    – fedja
    Nov 30, 2014 at 18:14

1 Answer 1

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$
8
  • $\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$ Dec 1, 2014 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, 2014 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, 2014 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$ Dec 1, 2014 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$ Dec 1, 2014 at 14:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.