0
$\begingroup$

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]$?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Are particular values of $e_i$ significant in any way? Say, can one simply assume $e_i = i$? $\endgroup$
    – Mikhail Tikhomirov
    Commented Nov 4, 2020 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
    Commented Nov 4, 2020 at 2:01
  • 1
    $\begingroup$ (Maybe it is worth to simplify the notation based on your question). $\endgroup$
    – Penelope Benenati
    Commented Nov 4, 2020 at 2:07

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\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
    Commented Nov 4, 2020 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
    Commented Nov 4, 2020 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
    Commented Nov 4, 2020 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
    Commented Nov 4, 2020 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
    Commented Nov 4, 2020 at 19:27

You must log in to answer this question.

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