0
$\begingroup$

Im trying to maximize the probability of a particular outcome occurring subject to a constraint. In particular

$$\max \prod_{i \leq n} 1 - (1 - x_i)^{y_i} \;\;\; \text{ s.t. } \;\;\; i \in \mathbb{N}^+,\; 0 \leq x_i \leq 1,\; x_1\cdots x_n = z, \forall n \in \mathbb{N}^+$$

where $y_i \in \mathbb{N}^+$ and $0 \leq z \leq 1$. The context really isn't important, I'm interested only in a solution to this problem. I've been able to find and prove a solution for the minimum, but I haven't been able to for the max.

I highly suspect that the maximum is at $x_1 = \cdots = x_n = z^{(1/n)}$ ($y_i$ fixed for all $i$), but I have not been able to come close to proving this. I'm looking for a proof that either the solution that I have proposed is correct, or incorrect. I'm not necessarily looking for a solution, but it would be welcome. I've been trying to prove this for quite some time and haven't had any luck (proving it false or true). Any advice or suggestions would be greatly appreciated.

Note (read all first): I've posted this on math exchange, but despite the number of views, I haven't received any responses. I'm reposting here (shouldn't do this, I know, but in retrospect I think this question is more relevant here) because I'm beginning to wonder if this problem is in fact much more difficult than I originally thought. It seems to me that someone would have looked at a problem similar to this from the research community since this problem, at least to me, seems relatively elementary despite its potential usefulness when calculating outcome probabilities. Barring a solution, is anyone aware of any references that I could take a look at that might lead me to a proof or counter proof?

In addition I have included algebraic geometry as a tag because one of the approaches I have looked at is a reduction of this problem by looking at it as the maximization of a $n$ hyper rectangle. That is to say given a hyper rectangle with $n$ dimensional volume $x_1\cdot...\cdot x_n = z$, what side lengths will give the largest $n$ dimensional volume if we set each side length to be $1 - (1 - x_i)^{y_i}$ for fixed $y_i$. From this perspective, I would expect the greatest $n$ dimensional volume increase (and thus greatest volume) would occur when all sides ($x_i$) have the same length. I don't have much of a background in geometry though so I haven't gotten far on this.

Edit.

I mentioned that I was able to prove what the minimum was. My proof was incorrect. Doesn't change this question, but I wanted to make sure the problem description was as accurate as possible.

$\endgroup$
3
  • $\begingroup$ I assume that you are given $n \in \mathbb{N}$ and $y_{1}, \ldots, y_{n} \in \mathbb{N}$ and you maximize that quantity. Since $y_{i}$ are different I doubt that the maximum is attained when all $x_{i}$ are equal (try $n=2$). In general one possible approach is the following "rearrangement" type idea: Let $x_{i}\cdot x_{j}=t$ for some $i\neq j$. Then when is the product $(1-(1-x_{i})^{y_{i}})(1-(1-x_{j})^{y_{j}})$ maximized? This should tell you how the pairs $(x_{i}, x_{j})$ are distributed... $\endgroup$ Mar 19, 2017 at 6:26
  • $\begingroup$ @HXSP1947 To clarify $x_1*...*x_n = z, \forall n \in \mathbb{N}^+$, did you mean to say that the problem has infinitely many constraints? $\endgroup$
    – aberdysh
    Mar 19, 2017 at 6:33
  • $\begingroup$ The stackexchange post was math.stackexchange.com/questions/2191797/… $\endgroup$ Apr 19, 2017 at 4:13

1 Answer 1

2
$\begingroup$

To me, the natural approach is to:

  1. Take the log of everything (to replace product by sums);
  2. Use a Lagrangian relaxation to solve the problem.

By 1, your maximization problem is equivalent to the following concave maximization problem:
$$\max \sum_{i\le n} \log (1 - (1-e^{a_i})^{y_i}) \text{ s.t.} \sum\log a_i=\log z.$$ In particular if all $y_i$ are constant, this implies that As for 2, you write your problem as: $$\max_a \sum_{i\le n} \log (1 - (1-e^{a_i})^{y_i}) + \lambda (\sum\log a_i-\log z)$$

Differentiating with respect to $a_i$ shows that $\log(1-(1-e^{a_i})^{y_i})=\lambda$. This implies that $(1-e^{a_i})^{y_i}$ is constant. In particular, if all $y_i$s are the same you get $x_i=(z)^{1/n}$.

The minimization problem is not well defined (the value of the minimum is $0$ and is attained when one $x_i$ goes to $0$ while the over ones are maintained such that $\prod x_i=z$).

$\endgroup$
1
  • 1
    $\begingroup$ Should the post and this answer go back to stackexchange instead? This seems like a non "math-level" research. $\endgroup$
    – N. Gast
    Mar 19, 2017 at 11:27

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.