# Expectation of the ratio of two discrete random variables with combinatorial constraints

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

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

• 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$). – Penelope Benenati Nov 4 '20 at 13:08
• 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. – Mikhail Tikhomirov Nov 4 '20 at 16:50
• 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. – Penelope Benenati Nov 4 '20 at 18:50
• 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. – Mikhail Tikhomirov Nov 4 '20 at 18:57
• 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! – Penelope Benenati Nov 4 '20 at 19:27