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
    Aug 26 at 2:35
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
    Aug 26 at 3:04

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.