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.

Improve this question
$\endgroup$
11
  • $\begingroup$ What is $p_i[1-t_i^n]$? $\endgroup$
    – Emil Jeřábek
    Commented 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
    Commented Nov 30, 2014 at 15:42
  • $\begingroup$ Oh I see, so these are just brackets. $\endgroup$
    – Emil Jeřábek
    Commented 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$
    – Ilya Bogdanov
    Commented Nov 30, 2014 at 15:59
  • 1
    $\begingroup$ You do not mind if some $t_i$ are negative, do you? $\endgroup$
    – fedja
    Commented Nov 30, 2014 at 18:14

1 Answer 1

Reset to default
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 .$$

Improve this answer
$\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$
    – Pietro Majer
    Commented 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
    Commented 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
    Commented 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$
    – Pietro Majer
    Commented 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$
    – Pietro Majer
    Commented Dec 1, 2014 at 14:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .