0

Let $T$ be a finite set.

Let $\rho:T\rightarrow (0,1)$ be such that $\sum_{t\in T}\rho(t)=1$.

Let $F:\mathbb N\cup\{0\}\rightarrow(0,1)$ be such that $\sum_{i=0}^\infty F(i)=1$. Let $\mu_F=\sum_{i=0}^\infty iF(i)$.

Let $\ell:T\rightarrow\mathbb N$ be any function.

Fix $t_0\in T$. Then consider the two quantities:

$$\sum_{i=0}^{\infty}F(i)\frac{\ell(t_0)-i}{\sum_{u\in T}\rho(u)\ell(u)-i}$$ and $$\frac{\ell(t_0)-\mu_F}{\sum_{t\in T}\rho(t)\ell(t)-\mu_F}$$

I came across a point in a paper where the second quantity was substituted for the first. But no proof or argument was given as to why this is a reasonable approximation.

So my question is, is there some kind of general theory I can look up that handles approximations such as this? Any guidance would be greatly appreciated.

Thank you!

Eric Stucky
  • 12,758
  • 3
  • 38
  • 69
Gregory Grant
  • 14,874
  • What do you mean by "the mean value of $F$"? –  Apr 16 '15 at 16:37
  • Is the mean of $F$ is $\lim_{N \to \infty} \frac1N \sum_{n=1}^N F_n$? – Mark Viola Apr 16 '15 at 16:41
  • I suspect that $F$ is a probability distribution and $\mu$ is the mean of the distribution, in other words, $\sum i \cdot F(i)$. That way the question might make sense. – Karolis Juodelė Apr 16 '15 at 16:53
  • There must be some missing context. Since the definitions of $F$ and $\mu_F$, as given, are wholly unconnected to those of $\rho$ and $\ell$, you could have a zero in the denominator of the first expression but not the second, and vice versa. – Barry Cipra Apr 16 '15 at 16:55
  • @Rahul Sorry, I wasn't clear. I meant think of $F$ as a probability distribution on $\mathbb N\cup{0}$. So $\mu_F=\sum_i iF(i)$. – Gregory Grant Apr 16 '15 at 16:55
  • @KarolisJuodelė Thank you yes that was what I meant. – Gregory Grant Apr 16 '15 at 16:56
  • @BarryCipra Thank you for your comment, let me think about it and I'll try to clarify. – Gregory Grant Apr 16 '15 at 16:57
  • @GregoryGrant, are you sure there wasn't a typo in the paper, and it shouldn't have been a $-\mu_F$ in the denominator of the first expression as well, instead of a $-i$? – Barry Cipra Apr 16 '15 at 17:08
  • @GregoryGrant I obtained an inequality relationship using Chebychev's sum inequality. Let me know how I can improve my answer. I just want to give you the best answer I can. – Mark Viola Apr 16 '15 at 19:33
  • @BarryCipra Thank you for the feedback, I don't think it should be $\mu_F$, but I didn't take it verbatim from the paper, the paper makes an even bigger leap that I reduced to this step. – Gregory Grant Apr 16 '15 at 19:37
  • @Dr.MV Thank you so much for your help! I'm going to go through it carefully and also make sure the statement is rigorous and I'll respond shortly. Thanks again! – Gregory Grant Apr 16 '15 at 19:37
  • You're welcome. My pleasure. The development uses Chebychev's sum inequality (CSI) twice. Typically, the CSI is $\frac1n \sum ab \ge (\frac1n \sum a)(\frac1n \sum b)$ when $a$ and $b$ are either both increasing or decreasing. If you let $a \to \frac{a}{b}$ and $b \to b$, then the CIS becomes $\frac1n \sum a \ge (\frac1n \sum \frac{a}{b})(\frac1n \sum b)$ or $ \frac1n \sum \frac{a}{b} \le(\frac1n \sum a)/(\frac1n \sum b)$. – Mark Viola Apr 16 '15 at 19:49

1 Answers1

1

Abbreviate $$\sum_{i=0}^{\infty}F(i)\frac{\ell(t_0)-i}{\sum_{u\in T}\rho(u)\ell(u)-i}=\sum_{i=0}^{\infty}F_i\frac{a-i}{b-i}$$

We assume that $F_i$ is a decreasing sequence. Note that both $a-i$ and $b-i$ are also decreasing sequences, but that the ratio $\frac{a-i}{b-i}$ can be increasing or decreasing depending on whether $a<b$ or $b<a$, respectively.

Let's assume first that $a<b$. Then, using Chebyshev's sum inequality twice in succession reveals that

$$\begin{align} \sum_{i=0}^{n}F_i\frac{a-i}{b-i} &\le n\left(\frac1n\sum_{i=0}^{n}F_i\right)\left(\frac1n\sum_{i=0}^{n}\frac{a-i}{b-i}\right)\\\\ &=n\left(\frac1n\sum_{i=0}^{n}F_i\right)\left(\frac1n\sum_{i=0}^{n}\frac{F_i(a-i)}{F_i(b-i)}\right)\\\\ & \le n\left(\frac1n\sum_{i=0}^{n}F_i\right)\frac{\frac1n \sum_{i=0}^{n} F_i(a-i)}{\frac1n \sum_{i=0}^{n} F_i(b-i)}\\\\ & \le \left(\sum_{i=0}^{n}F_i\right)\frac{ \sum_{i=0}^{n} F_i(a-i)}{ \sum_{i=0}^{n} F_i(b-i)}\\\\ \end{align}$$

Passing to the limit as $n \to \infty$ gives the desired inequality

$$\begin{align} \lim_{n \to \infty}\sum_{i=0}^{n}F_i\frac{a-i}{b-i} &=\sum_{i=0}^{\infty}F_i\frac{a-i}{b-i}\\\\ &\le \left(\sum_{i=0}^{\infty}F_i\right)\frac{a\sum_{i=0}^{\infty} F_i-\sum_{i=0}^{\infty} F_ii}{b\sum_{i=0}^{\infty} F_i-\sum_{i=0}^{\infty} F_ii}\\\\ &=\frac{a-\mu_F}{b-\mu_F} \end{align}$$

The case for $a>b$ can be analyzed analogously. Obvioulsy, the closer $a$ is to $b$, the tighter the inequality becomes. Recall that $a=\ell(t_0)$ while $b=\sum_{u\in T}\rho(u)\ell(u)$ is an effective averaging of $\ell$ at discrete points.

Mark Viola
  • 179,405