2
$\begingroup$

This problem is distilled from one arising in a study of complex random variables, but I've removed as much baggage as I can without (I hope) making it trivial.

Fix $D>0$. A function $f:\mathbb R\to\mathbb R$ is $D$-basic if there are $x_1,x_2\in\mathbb R$ and $p_1,p_2\ge 0$ such that $|x_1-x_2|\le D$, $f(x_1)=p_1$, $f(x_2)=p_2$, $f(x)=0$ for $x\notin\lbrace x_1,x_2\rbrace$, and $p_1x_1+p_2x_2=0$.

If you like random variables, this is like a real random variable of mean 0 supported on 2 points at most $D$ apart; but for convenience I won't assume $p_1+p_2=1$.

Now define $F_D$ to be the set of all functions which are a sum of $D$-basic functions. I.e., $f\in F_p$ if $f(x)=\sum f_j(x)$ where $f_j$ is $D$-basic for all $j$.

Question 1. Is there a characterisation of $F_D$ that doesn't just restate the definition?

All nonnegative functions $f$ on a finite support $X$ with $\max X-\min X\le D$ and $\sum_{x\in X}xf(x)=0$ are in $F_D$ (easy induction proof) but many other functions are in there too.

Question 2. Given a nonnegative $f$ of finite support, how can we tell if it is in $F_D$? How can we find the smallest $D$ such that $f\in F_D$?

Since any $D$-basic functions in a decomposition of $f$ have a support which is a subset of the support of $f$, Q2 can be solved in polynomial time using linear programming. But that's pretty awful; can it be done in time quadratic or better in the size of the support of $f$?

It should be clear that this setting can be generalised to countable support, and to arbitrary support with some integrability/measurability conditions. Then further to higher dimensions. I'd appreciate any references to this type of question.

Improve this question
$\endgroup$
4
  • $\begingroup$ It looks like you can drop the alpha's in your definition of $F_D$. Also, all such combinations have domain contained in (-D, D). If a function $f$ majorises a D basic function $g$, hopefully $f-g$ is in $F_D$, which would then lend hope to find quickly a decomposition of $f$. $\endgroup$
    – The Masked Avenger
    Commented May 22, 2015 at 7:25
  • $\begingroup$ Actually, f(x) + f(-x) is in $F_D$, and one can subtract a smaller function g which leaves something not in $F_D$. This reminds me of stacking rectangles, then looking just at the height of the stack as x varies, and using that to reconstruct the rectangles. I suspect you have something similar and NP hard to untangle. $\endgroup$
    – The Masked Avenger
    Commented May 22, 2015 at 7:35
  • $\begingroup$ Suppose you consider one-sided basic D functions. These are those functions in which x2 and p2 are both positive. Then consider G_D as any function which is a sum of one sided functions. Then f in F_D should be a difference of two functions in G_D. While decomposing f may be hard, dealing with functions in G_D should be easy. Is it? Does it help to decompose f into functions in to F_D' which in turn may be decomposed into functions of G_D for D' bigger than D? $\endgroup$
    – The Masked Avenger
    Commented Jun 12, 2015 at 17:08
  • $\begingroup$ Oops. I flipped a sign bit. I no longer know if one-sided functions make sense, much less help with F_D. It might help to dichotomize into x2 bigger or less than D/2, but I am unsure now if that helps. $\endgroup$
    – The Masked Avenger
    Commented Jun 12, 2015 at 17:21

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .