0
$\begingroup$

I have a set of equations with some inequality constraints that I expect generally does not have a unique solution.

The equations take the form below:

$$\alpha/N+(1-\alpha)x_1=a_1$$ $$\alpha/N+(1-\alpha)x_2=a_2$$ $$\vdots$$ $$\alpha/N+(1-\alpha)x_N=a_N$$ $$x_1+x_2+\dots+x_N=1$$ $$0<x_i<1$$ $$1>\alpha>0$$

where $N$ is fixed and $a_i$ are known and satisfy $a_i>0$ and $a_1+\dots a_N=1$.

If I toy around in Mathematica I get that if I take $N=3$ and $(a_1,a_2,a_3)=(1/2,3/10,1/5)$ the feasible solutions are given as a family of solutions for $x_1$, $x_2$, and $x_3$ all depending on $\alpha<3/5$. I expect in general that one can get some estimated range for $\alpha$ that depends on the values of $a_i$, computationally for instance with enough time.

I am wondering if there is any structure I can utilize for this set of equations to simplify things, or if there is a simple reduction of this problem to a simpler one.

It seems from the examples that $\alpha<1-2\min\{a_i\}$ is the best bound, but I don't see why this is true immediately.

P.S. The motivation for looking at these equations is related to probability, and estimation of a distribution from its marginals.

$\endgroup$
1
  • $\begingroup$ For another data point if one takes $N=4$ and $(a_1,a_2,a_3,a_4)=(1/2,1/6,1/6,1/6)$ you get $\alpha<2/3$. $\endgroup$
    – asd
    Commented Aug 26, 2021 at 2:35

1 Answer 1

3
$\begingroup$

Let $n:=N$ and $t:=\alpha$. We have $$0<x_i=\frac{a_i-t/n}{1-t}<1$$ for all $i\in[n]:=\{1,\dots.n\}$ -- or, equivalently, $$t<t_{n,a}:=\min_{i\in[n]}\min\Big(\frac{1-a_i}{1-1/n},na_i\Big) =\min\Big(\frac{1-a_{\max}}{1-1/n},na_{\min}\Big),$$ where $a_{\max}:=\max_{i\in[n]}a_i$ and $a_{\min}:=\min_{i\in[n]}a_i$.

So, $t_{n,a}$ is the best bound on $t$.

If, as in your example, $n=3$ and $(a_1,a_2,a_3)=(1/2,3/10,1/5)$, then $t_{n,a}=3/5$, as you found. If, as in your comment, $n=4$ and $(a_1,a_2,a_3,a_4)=(1/2,1/6,1/6,1/6)$, then $t_{n,a}=2/3$, as you also found.

$\endgroup$
1
  • $\begingroup$ Thanks! I guess I should've looked a little more before asking :) $\endgroup$
    – asd
    Commented Aug 26, 2021 at 3:04

You must log in to answer this question.

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