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



Expectation of the ratio of two discrete random variables with combinatorial constraints
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.


