7
$\begingroup$

I want to solve the following optimization problem

\begin{align} \inf_{ X: |X| \le a \text{ a.s.}} E \left[ \frac{1}{1+(X-X^\prime)^2} \right] \end{align} where $X^\prime$ is an independent copy of $X$ and $a>0$ is some constant.

How would one approach such a problem? Is the solution easy to find?

At some point I thought that the optimal distribution is given by $X=\{-a,a\}$ equally likely. In which case, the solution is given by \begin{align} \inf_{ X: |X| \le a \text{ a.s.}} E \left[ \frac{1}{1+(X-X^\prime)^2} \right] \le \frac{1}{2}\frac{1}{1+4a^2}+\frac{1}{2}. \end{align} However, I don't have any supporting arguments for this.

The following might be useful. Note that by Jensens' inequality

\begin{align} E \left[ \frac{1}{1+(X-X^\prime)^2} \right] \ge \frac{1}{1+E[(X-X^\prime)^2]} =\frac{1}{1+2Var(X)}. \end{align}

Therefore,

\begin{align} \inf_{ X: |X| \le a \text{ a.s.}} E \left[ \frac{1}{1+(X-X^\prime)^2} \right] \ge \frac{1}{1+2 \sup_{ X: |X| \le a \text{ a.s.}} Var(X)}=\frac{1}{1+2a^2}, \end{align}

where in the last optimization step we used \begin{align} Var(X) \le E[X^2] \le a^2, \end{align} which is achievale with $X=\{-a,a\}$ equally likely.

$\endgroup$
13
  • $\begingroup$ This is similar in spirit to finding the equilibrium measure in potential theory, except that your kernel isn't the "right" one. This analogy suggests that the optimal distribution will have the full interval as its support, with more mass sitting near the endpoints. I'm skeptical if an explicit solution is possible. In any event, you can check that $\epsilon\delta_0 +(1/2) (1-\epsilon)(\delta_a+\delta_{-a})$ beats your distribution, so that isn't optimal. $\endgroup$ Sep 9, 2017 at 3:12
  • $\begingroup$ @ChristianRemling: This is very smart comment! Unfortunately, $1/(1+(x-y)^2)$ is not a potential kernel of any Lévy process (if it were a potential kernel, the generator of the corresponding Markov process would be an operator with Fourier symbol $\exp(|x|)$, which is impossible). Interestingly, even in the limiting cases $a \to \infty$ or $a \to 0^+$ there are no reasonable Markov processes behind this functional. $\endgroup$ Sep 9, 2017 at 15:38
  • 1
    $\begingroup$ How are you applying Jensen's inequality to $1/(1+x^2)$? $\endgroup$
    – MTyson
    Sep 10, 2017 at 1:12
  • 1
    $\begingroup$ ...If you read French, however, you should take a look into the original paper of Marcel Riesz Intégrales de Riemann–Liouville et potentiels, if only to see how the theory developed almost a century ago. A completely general theory can be found in any books on general potential theory, of which I know mostly Bliedtner and Hansen's Potential Theory An Analytic and Probabilistic Approach to Balayage (which is terrible to read, but I like the non-mathematical flavour of the title) and... $\endgroup$ Sep 10, 2017 at 10:40
  • 1
    $\begingroup$ ... Chung and Walsch's Markov Processes, Brownian Motion, and Time Symmetry (a fantastic read, but rather technical and written from a different perspective). $\endgroup$ Sep 10, 2017 at 10:40

3 Answers 3

5
$\begingroup$

My initial intuition was incorrect. It seems we can sometimes solve this explicitly, and the minimizer does not have full support; my argument is incomplete (as discussed below), but I think it's reasonably convincing anyway. I'm also only going to discuss $a=1$ (initially, I thought that was the general case, but of course that's not true because of the $1$ in the denominator of the kernel; see also Mateusz's answer for more on this). Then it is given by $$ \mu= \frac{5}{12}(\delta_{-1}+\delta_1) + \frac{1}{6}\delta_0 . $$ To see why this is optimal, look at $$ F(x)=\int \frac{d\mu(t)}{1+(t-x)^2} = \frac{5}{12}\left( \frac{1}{1+(x+1)^2} + \frac{1}{1+(x-1)^2} \right) + \frac{1}{6}\frac{1}{1+x^2} . $$ Notice that $F(x)=7/12$ on $x=0,\pm 1$ (the support of $\mu$), and $F(x)\ge 7/12$ for $-1\le x\le 1$ (this is a tedious but elementary calculus exercise).

This means that if we vary the measure slightly, say $\nu=\mu+\epsilon\sigma$ with a signed measure $\sigma$ with $\int d\sigma=0$ and $\epsilon\ll 1$, then the change in first order will be proportional to $\int F(x)\, d\sigma(x)$. However, since $\nu$ must remain a positive measure, the negative part of $\sigma$ can only be supported by $0,\pm 1$. This means that $\int F\, d\sigma\ge 0$, by the properties of $F$ observed above.

This verifies that my $\mu$ is a local minimum. I don't have an argument that shows that it gives the global minimum also, though I'm fairly optimistic that this will be true.


A few things can perhaps be said in general: First of all, this criterion ($F_{\mu}$ constant on the support of $\mu$ and $F(x)$ at least as large otherwise) is also necessary for local minima. The general scenario that seems likely is that as you increase $a$, additional points enter the support. This would also be consistent with what Mateusz does in his answer.


Finally, here is a general argument why a measure $d\mu =f\, dx$ with $f>0$ on $-a<x<a$ can not give a minimum, not even a local one. To see this, consider again a small variation $d\nu =(f+\epsilon g)\, dx$. Now $g$ can be an arbitrary (let's say, almost arbitrary, to be safe) function with $\int g=0$, so it now follows that at an extremum, $\int Fg =0$ for all such $g$. This forces $F$ to be constant on $-a<x<a$, but since $F$ is the restriction of a harmonic (on $\mathbb C^+$) function to the line $\textrm{Im}\: z =1$ (your kernel is the Poisson kernel for the upper half plane), this harmonic function would have to be constant on this whole line, which makes $f$ constant on $\mathbb R$, but we need an $f$ that is zero outside $(-a,a)$.

$\endgroup$
11
  • $\begingroup$ I think there is an error in your evaluation of the first variation: if $F_\mu(x) = \int (1+x^2)^{-1} \mu(dx)$, then $\int F_{\mu+h\sigma}(x) (\mu+\sigma)(dx) \approx \int F_\mu(x) \mu(dx) + h(\int F_\mu(x)\sigma(dx)+\int F_\sigma(x)\mu(dx)) + o(h^2)$, so apparently you are missing $\int F_\sigma(x)\mu(dx)$. I am not sure, though, if it changes the result. $\endgroup$ Sep 9, 2017 at 21:09
  • $\begingroup$ @MateuszKwaśnicki: The two terms are equal to one another, they are both double integrals $\int d\sigma(x)\int d\mu(t)\, 1/(1+(x-t)^2)$ with just the variables swapped in the second term. $\endgroup$ Sep 11, 2017 at 15:48
  • $\begingroup$ Oh, that is of course correct, sorry! $\endgroup$ Sep 11, 2017 at 17:36
  • $\begingroup$ Do you think $E[ e^{-(X-X^\prime)^2}]$ has an easier solution? Should I ask a new question on this? $\endgroup$
    – Boby
    Sep 11, 2017 at 19:06
  • $\begingroup$ @Boby: I don't know really off the top of my head, right now my feeling is this is going to have the same general features as the question you asked. $\endgroup$ Sep 11, 2017 at 19:25
3
$\begingroup$

You ask what is the minimiser of the functional $$ F(\mu) = \int_{[-a,a]} \int_{[-a,a]} \frac{1}{1+(x-y)^2} \mu(dx) \mu(dy) . $$ As Christian Remling points out, it is unlikely a closed-form expression exists. However, you can say what happens as $a \to \infty$ and $a \to 0^+$.

Some notation first. Denote by $\nu(E) = \mu(a E)$ a measure rescaled by a factor of $a$. Then $$ G_a(\nu) := F(\mu) = \int_{[-1,1]} \int_{[-1,1]} \frac{1}{1+a^2 (x-y)^2} \nu(dx) \nu(dy) . $$

As $a \to \infty$, $a/(1+a^2(x-y)^2) dx$ converges to the Dirac measure at $y$. Therefore, if $\nu$ has a density $g(x)$, then $a G_a(\nu)$ converges as $a \to \infty$ to $$ \int_{[-1,1]} g(y) \nu(dy) = \int_{[-1,1]} (g(y))^2 dy ,, $$ which is minimised by a constant $g$. Therefore, the minimiser of $F$ can be expected to be close to the uniform distribution if $a$ is large.

When $a \to 0^+$, $G_a(\nu)$ converges to $1$, but one can inspect $(G_a(\nu)-1)/a^2$ instead. We have $$ \frac{G_a(\nu)-1}{a^2} = \int_{[-1,1]} \int_{[-1,1]} \frac{-(x - y)^2}{1+a^2 (x-y)^2} \nu(dx) \nu(dy) , $$ which converges to $$ -\int_{[-1,1]} \int_{[-1,1]} (x - y)^2 \nu(dx) \nu(dy) . $$ This expression is easily evaluated to be $-2 \operatorname{Var}(\nu)$, a negative multiple of the variance of $\nu$, which is maximised by a symmetric two-point distribution $\tfrac{1}{2}\delta_{-a}+\tfrac{1}{2}\delta_a$. Therefore, the minimisers of $F$ should behave roughly as a two-point distribution for small $a$.

$\endgroup$
1
$\begingroup$

I am proposing the following lemma.

For $g$ concave $\inf_{|X|\leq a}\mathbb{E}(g(X-X'))=\inf_{|X|= p\delta_a+(1-p)\delta_{-a},p\in[0,1]}\mathbb{E}(g(X-X'))$

This show that for $a<2/7$, the solution of your problem is exactly $1/2\delta_a+1/2\delta_{-a}$.

Proof of the lemma : replace $X$ by $X+B_T$ where $B$ is a brownian motion and $T$ the stoping time $\inf(t:|X+B_t|=a)$. Define $$ u(t)=\mathbb{E}(g(X+B_{\inf (t,T)}-X'-B_{\inf (t,T')}'))$$ Then because of ito formula : $$ \frac{d}{dt}u(t)=\mathbb{E}(\frac{1}{2}g''(X+B_{\inf (t,T)}-X'-B_{\inf (t,T)}')(1_{t\leq T}+1_{t\leq T'}))\leq 0$$ $u$ is then decreasing and for $t\rightarrow \infty$, $|X+B_{\inf (t,T)}|=a$ with probability one.

For large $a$, One can adapt your perturabative proof : $\int Fg = 0$ for all $g$ such that $\int g =0$ and $g\geq 0$ outside the support of $\mu$. If there exist $x\in supp(\mu)$ and $F(x)>\inf_{[-a,a]} F(x)$ then let $\exists F(x_0)<F(x)$ and set $g=-1/2 \delta_x+1/2 \delta_{x_0}$ which do not satisfy the condition.

Conclusion : $supp(\mu)\subset [x: F(x)=\inf F]$. Because $F$ is harmonic, then $supp(\mu)$ is discreet and $\mu $ is therefore a sum of dirac mass. We can see the dirac like particles which repel each other and at the limit $a \rightarrow \infty$ because of Mateusz remark will form a regular cristal.

$\endgroup$
1
  • $\begingroup$ Why in the ito formula do you have a second derivative of $g$ and the first? Is this something specific to the ito formula. $\endgroup$
    – Boby
    Sep 14, 2017 at 18:20

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.