We are given a set $S=\{1, 2, \ldots, n\}$ where $n\gg 1$, and for all indices $1\le i \le n$, $i$ is associated with a real value $\alpha_i\!\cdot\! v_i$, where $\alpha_i\in[0,1]$ and $v_i\in(0,1]$.

Let $X$ be a discrete random variable whose sample space consists of $n'<n$ (not necessarily disjoint) proper subsets of $S$. We denote all the possible outcomes as $S_1, S_2, \ldots, S_{n'}$. We also have $\bigcup_{1\le k\le n'} S_k=S$, and the values taken by $X$ are defined as follows for all $1\le k\le n'$:

$$X(S_k)\equiv x_k:=\frac{y_k}{z_k}~,$$

where $y_k$ and $z_k$ are the values taken by the two random variables $Y$ and $Z$ (with the same sample space, outcomes and constraints of $X$), defined as $$Y(S_k)\equiv y_k:=\sum_{j\in S_k}\!\left(\alpha_j\!\cdot\! v_j\right)$$ and $$Z(S_k)\equiv z_k:=\sum_{j\in S_k} v_j~.$$

For $1\le i\le n$, let $p(i):=\sum_{k: i\in S_k} \Pr(S_k)$. Note that we have $\mathbb{E}[Y]=\sum_{1\le i\le n} \left(p(i)\,\alpha_i\,v_i\right)$ and $\mathbb{E}[Z]=\sum_{1\le i\le n} \left(p(i)\,v_i\right)$.

Question: Is it possible to express the expectation $\mathbb{E}[X]$ (or a lower bound for it close to $\mathbb{E}[X]$ for all possible input values of this problem), as a function of $\alpha_1, \alpha_2, \ldots, \alpha_n$,$~~$$v_1, v_2, \ldots, v_n$,$~~$and $~p(1), p(2), \ldots, p(n)$like above for $\mathbb{E}[Y]$ and $\mathbb{E}[Z]$?

  • 1
    $\begingroup$ Are particular values of $e_i$ significant in any way? Say, can one simply assume $e_i = i$? $\endgroup$ – Mikhail Tikhomirov Nov 4 '20 at 1:46
  • $\begingroup$ Thank you for your question @MikhailTikhomirov. No, you can immagine that they are just items, colours or people (not even numerical values). If the problem seems easier when assuming that they are the first $n$ positive integers, that's completely fine. $\endgroup$ – Penelope Benenati Nov 4 '20 at 2:01
  • 1
    $\begingroup$ (Maybe it is worth to simplify the notation based on your question). $\endgroup$ – Penelope Benenati Nov 4 '20 at 2:07

This obviously depends on the "closeness" measure of the lower bound. FWIW, for any $n$ (let $n = 2k$ even for simplicity) and the following input values:

  • $\alpha_1 = \alpha_k = 0$, $\alpha_{k + 1} = \alpha_{2k} = 1$,
  • $v_1 = v_2 = \ldots = v_{2k} = 1$,
  • $p(1) = \ldots = p(2k) = \frac{1}{k + 1}$,

$\mathbb{E}(X)$ can be both:

  • $\frac{1}{k + 1}$, when $S_1, \ldots, S_{k + 1}$ are equiprobable, and $S_1, \ldots, S_k$ are singleton sets $\{1\}, \ldots, \{k\}$, $S_{k + 1} = \{k + 1, \ldots, 2k\}$,
  • $1 - \frac{1}{k + 1}$, for a symmetrical construction.

Thus, any lower bound on $\mathbb{E}(X)$ would have worst-case $\Omega(n)$ relative error, or $1 - O(1 / n)$ absolute error.

  • $\begingroup$ Thank you for your answer @Mikhail, I see the point. Can we get a similar result in your opinion if we further assume that $\min_i(\alpha_i)$ and $\max_i(\alpha_i)$ are both close to $1$? Assume for instance that $\alpha_{i}=0.8$ for all $1\le i\le n/2$ and $\alpha_j=0.9$ for all $n/2+1\le j\le n$. I am asking this question also because I suspect that your result depends on the fact $\max_i(\alpha_i)-\min_i(\alpha_i)$ is equal to $1$ (or, more in general, it is large w.r.t the maximum possible difference value -- which is $1$). $\endgroup$ – Penelope Benenati Nov 4 '20 at 13:08
  • $\begingroup$ In your assumption the absolute error is $0.1 - O(1/n)$. Though, as $\min \alpha$ and $\max \alpha$ become closer, the trivial lower bound $\min \alpha$ gradually becomes "better" and the question make less and less sense. $\endgroup$ – Mikhail Tikhomirov Nov 4 '20 at 16:50
  • $\begingroup$ Yes, of course. However, in the "real" research problem I am working on (which includes this little subproblem of this post here above) I have exactly $\min_i(\alpha_i)\simeq 0.8$ and $\max_i(\alpha_i)\simeq 0.9$. It would be a significant improvement to obtain an expected value of $X$ always strictly larger than $\min_i(\alpha_i)$. That's the main reason I asked my last question in the previous comment. Thank you anyway. $\endgroup$ – Penelope Benenati Nov 4 '20 at 18:50
  • 1
    $\begingroup$ Well, there's only so much to gather in the worst-case OP setting. If there's additional information that could be helpful for the estimate, please feel free to put it in another question. $\endgroup$ – Mikhail Tikhomirov Nov 4 '20 at 18:57
  • $\begingroup$ It's a bit complex, anyway I agree, I understood that for my goal I should use some of the constraints not mentioned in the original post above. Thank you once again! $\endgroup$ – Penelope Benenati Nov 4 '20 at 19:27

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.