(Re-posted from StackOverflow as suggested)

I have the following problem.

The functions $f(x),g(x)$ are defined as $$ f(x) = \begin{cases} f_1(x) & 0 \leq x \leq 10, \\ f_2(x) & 10 < x \leq 20, \\ 0 & \text{otherwise}, \end{cases} \qquad g(x) = \begin{cases} g_1(x) & 0 \leq x \leq 5, \\ g_2(x) & 5 < x \leq 20, \\ 0 & \text{otherwise}, \end{cases} $$ In addition, we require the constraints $$ \int_0^{20} f(x) dx \geq K, \quad \int_0^{20} g(x) dx \geq Q, \quad f(x)+g(x) \leq R \text{ for all $x$}. $$ where $K,Q,R$ are parameters.

I assume there is quite some elaborate theory behind it, and was wondering if anybody could point me in the right direction to devise an algorithm that can generate $f_1(x), f_2(x), g_1(x), g_2(x)$?

I would like to add that for a given $K$ and $Q$, the interest is to keep $R$ as low as possible.

  • $\begingroup$ Do you mean that when $x \in [0, 10)$, $f(x) = f_1(x)$ and when $x \in [10, 20]$, $f(x) = f_2(x)$? What sort of restriction is that? $\endgroup$ – Karolis Juodelė Apr 5 '14 at 16:26
  • $\begingroup$ Yeah, that's what I mean, f1(x)!=f2(x) $\endgroup$ – MrD Apr 5 '14 at 16:28
  • 1
    $\begingroup$ I can take any function $f$ and define $f_1(x) = f(x)\cdot 1_{[0, 10)}(x)$ where $1_{[...]}$ is an indicator function. My point is that dividing $f$ into two functions adds nothing to the problem. $\endgroup$ – Karolis Juodelė Apr 5 '14 at 16:33
  • $\begingroup$ I may have gotten the syntax wrong, but I hope what I mean is still clear? $\endgroup$ – MrD Apr 5 '14 at 16:34
  • 2
    $\begingroup$ So is there actually a point to $f_1, f_2$ or not? $\endgroup$ – Karolis Juodelė Apr 5 '14 at 16:36

Let $X$ be a random variable distributed uniformly over $[0,20]$. Your constraints imply $$ \mathbb{E}[f(X)] \geq \frac{K}{20}, \qquad \mathbb{E}[g(X)] \geq \frac{Q}{20}. $$ We conclude that $$ \mathbb{E}[f(X)+g(X)] \geq \frac{K+Q}{20}, $$ and so there is some point $x \in [0,20]$ such that $f(x) + g(x) \geq (K+Q)/20$. In particular, $R \geq (K+Q)/20$. This bound is tight, as shown by the functions $$ f(x) = \frac{K}{20} \mathbf{1}_{x \in [0,20]}, \qquad g(x) = \frac{Q}{20} \mathbf{1}_{x \in [0,20]}. $$

  • $\begingroup$ Hi Yuval, thanks for taking the time to answer and format my post. I'm afraid I don't fully understand your solution though. Why are you saying that my constraints inply that the expected values of f and g are k/20 and q/20 respectively? $\endgroup$ – MrD Apr 5 '14 at 17:43
  • $\begingroup$ You have a constraint on $\int_0^{20} f(x) dx$, and this translates to a constraint on $\mathbb{E}[f(X)]$ since the density of $X$ is $(1/20)\mathbf{1}_{x \in [0,20]}$. $\endgroup$ – Yuval Filmus Apr 5 '14 at 18:22
  • $\begingroup$ Hi Yuval, I'm sorry, I still don't understand how the solution guarantees that both functions are less than R for all given X. $\endgroup$ – MrD Apr 6 '14 at 13:53
  • $\begingroup$ This solution only works for $R \geq (K+Q)/20$, in which case I hope you can answer this yourself. The first part shows that there is no solution if $R < (K+Q)/20$. $\endgroup$ – Yuval Filmus Apr 6 '14 at 14:15

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.