Timeline for Maximizing the expectation of a polynomial function of iid random variables
Current License: CC BY-SA 4.0
42 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 27, 2019 at 19:54 | answer | added | Jairo Bochi | timeline score: 1 | |
| Feb 25, 2019 at 15:05 | answer | added | Jairo Bochi | timeline score: 3 | |
| S Feb 25, 2019 at 8:58 | history | bounty ended | Romeo | ||
| S Feb 25, 2019 at 8:58 | history | notice removed | Romeo | ||
| Feb 23, 2019 at 6:52 | comment | added | user44143 | @JairoBochi, I had an error in my calculations, which is why you expected something different; my new suggestion is in the answer I posted. | |
| Feb 23, 2019 at 6:50 | answer | added | user44143 | timeline score: 2 | |
| Feb 22, 2019 at 22:22 | answer | added | user114668 | timeline score: 5 | |
| Feb 22, 2019 at 18:12 | comment | added | Jairo Bochi | @MattF. I see, beta distributions are good candidates. I didn't expected something so flat near the extremes, however... | |
| Feb 22, 2019 at 14:51 | answer | added | Dan | timeline score: 4 | |
| Feb 22, 2019 at 14:40 | comment | added | user44143 | @JairoBochi, a beta-version of your suggestion is $\mu=.326(\delta_0+\delta_1)+.348\beta(22.63,22.63)$, which gives an integral greater than 1/9. | |
| Feb 21, 2019 at 18:51 | comment | added | Jairo Bochi | Another numeric experiment indicates that if we square the integrand in the Baby Question, then the optimizer becomes $\mu = (\delta_0+\delta_{1/2}+\delta_1)/3$, that is, the distribution considered by @MattF. on a comment above. | |
| Feb 21, 2019 at 18:50 | comment | added | Jairo Bochi | I believe that this Baby is a "terrible two". | |
| Feb 21, 2019 at 18:49 | comment | added | Jairo Bochi | Hoping that Maple is not tricking me, numeric experiments indicate that the optimizer $\mu$ for the Baby Question is of the form $\mu = a \delta_0 + a \delta_1 + (1-2a) \nu$, where the number $a$ is approximately $0.27$ and the probability $\nu$ on $[0,1]$ is absolutely continuous with respect to Lebesgue. Furthermore, it seems that the density of $\nu$ is a smooth function, whose graph is Gaussian-shaped, symmetric around $1/2$, where the maximum is attained. At the extremes of the interval, the density is small, maybe zero. | |
| Feb 20, 2019 at 8:46 | comment | added | Romeo | @MattF. So it seems that in the baby version the uniform distribution is not optimal. Hence also in the general version it might not be the maximizer. So probably there is no "canonical" maximizer and it depends on the polynomial itself? Interesting remark, thanks, I will think about that. | |
| Feb 20, 2019 at 2:55 | comment | added | user44143 | For the baby version, the uniform distribution gives 1/30 (by integration, wolframalpha.com/input/…), while the distribution evenly divided between 0, 1/2, 1 gives (6/27)(1/4)=1/18. | |
| Feb 18, 2019 at 21:44 | comment | added | Romeo | @student You are right, I have added the modulus. Thanks for the interesting connection to the Hausdorff moment problem, I did not know it and I'll certainly look into that. | |
| Feb 18, 2019 at 21:43 | history | edited | Romeo | CC BY-SA 4.0 |
deleted 6 characters in body
|
| Feb 18, 2019 at 21:05 | comment | added | user114668 | I might misunderstand the problem, but if you do not take the absolute value, for a polynomial of degree $n$ you have the expectation $$E\bigl[\sum_{|\alpha| < n} a_{\alpha} x^{\alpha}\bigr] = \sum_{|\alpha| < n} a_{\alpha} \, m_{\alpha_1} \cdots m_{\alpha_k}$$ in terms of the moments $m_i$, $0 \le i \le n$. So after you find the numbers $m_i$ that maximise the sum for the coefficients of the polynomial, you have a Hausdorff moment problem. | |
| Feb 18, 2019 at 20:16 | comment | added | user44143 | Actually that cubic is not so good, since the integral will be identically zero by symmetry. | |
| Feb 18, 2019 at 17:48 | history | edited | Romeo | CC BY-SA 4.0 |
added 25 characters in body
|
| Feb 18, 2019 at 17:44 | comment | added | user44143 | For the baby version, E[(X-Y)(Y-Z)(Z-X)] would be more interesting. | |
| Feb 18, 2019 at 16:46 | history | edited | Romeo | CC BY-SA 4.0 |
added 749 characters in body
|
| Feb 18, 2019 at 15:03 | comment | added | Pierre PC | @Romeo About the reduction of the problem, yes. And it's not really a method, just consider $Sf$ the symmetrised function, find the point $x=(x_1,\cdots,x_n)$ maximising $Sf$, then set $\mu=\sum_i\delta_{x_i}/n$. You have a probability $n!/n^n$ to get a point that is a permutation of $x$. | |
| Feb 18, 2019 at 14:54 | comment | added | Romeo | @PierrePC Interesting random thought! I see your point, you are suggesting that it is enough to solve the problem by consider only symmetric functions, am I right? But I am not following you in your second comment: which "method" are you referring to? D. Hughes' one? Thanks for your interest. | |
| Feb 18, 2019 at 13:20 | comment | added | Pierre PC | [Edited] In fact, if the maximum of the symmetrised function is M, then that method shows that the expectation is at least $n!/n^n\cdot M$, which coincides with David's case (where $M=1/n!$). | |
| Feb 18, 2019 at 12:43 | comment | added | Pierre PC | Maybe I am mistaken, but here is another random thought. Because the expectation is symmetric, in fact it is the same to consider the expectation of $|f|$ or that of $x\mapsto\sum_\sigma |f(\sigma\cdot x)|/n!$, where $\sigma$ ranges over all permutations. So you need only consider symmetrical functions. | |
| S Feb 17, 2019 at 14:06 | history | bounty started | Romeo | ||
| S Feb 17, 2019 at 14:06 | history | notice added | Romeo | Draw attention | |
| Feb 16, 2019 at 15:45 | comment | added | David Hughes | Actually what I said is only true if $A_i \neq A_j $ for $i \neq j$ and does not give the right answer in the linked cases... | |
| Feb 16, 2019 at 15:08 | comment | added | Romeo | @DavidHughes Mmm, interesting value, I had not found it. Can we use a "double" continuity approach (I mean wrt the measure and to the integrand) to reduce the problem to maximize $E[f(X)]$ where $f$ is an indicator function and formally prove that the max is the one you surmise? Thanks. | |
| Feb 16, 2019 at 14:50 | comment | added | David Hughes | If, instead of polynomials, you look at indicator functions $f = 1_A$ for $A=A_1 \times \ldots \times A_n$ you get $\mathbb{E}[1_A(X)] =\Pi_{i=1}^n \mathbb{P}_\mu (X \in A_i),$ which achieves its maximum $n^{-n}$ when $\mathbb{P}_\mu (X \in A_i ) = n^{-1}$ for all $i$. This suggests that, at least in this case, the maximum of $\mathbb{E}[f(X)]$ is $n^{-n} \sup\limits_{x \in \mathbb{R}^n}f(x).$ I don't know if that helps. | |
| Feb 16, 2019 at 13:30 | comment | added | Romeo | @JosiahPark Interesting, thanks. How did you come up with that polynomial? And when is your candidate maximum value attained? Indeed, in the case $N=2$ we have Sangchul Lee's approach yielding that the optimal measure is a.c. with respect to Lebesgue. Can you use your Python code on more general polynomials? Thank you. | |
| Feb 16, 2019 at 10:54 | history | edited | Romeo | CC BY-SA 4.0 |
added 18 characters in body
|
| Feb 16, 2019 at 9:00 | history | edited | Romeo | CC BY-SA 4.0 |
added 286 characters in body
|
| Feb 16, 2019 at 8:56 | comment | added | Romeo | @NateEldredge Thank you for sharing your interesting "random thought" :-). However, is it really easier to restrict only to a.c. measures (this amounts to consider the functional I have written at the hand of my post)? Of course a great advantage is that we have now "two" functions $f,g$: is it possible to use Holder/other inequalities to find the maximum? I do not know. Concerning $f$, good point, let us replace $f$ with a polynomial $\tilde{f}$ (uniformly close to $f$). | |
| Feb 16, 2019 at 0:00 | comment | added | Nate Eldredge | Random thought: the functional is weakly continuous in $\mu$, so you can sup over your favorite dense subset of $\mu$, e.g. a.c. measures suffice. (2) it may help to uniformly approximate $|f|$ by simpler functions, e.g. polynomials. | |
| Feb 15, 2019 at 20:57 | history | edited | Romeo | CC BY-SA 4.0 |
deleted 212 characters in body
|
| Feb 15, 2019 at 14:18 | comment | added | Romeo | To the down-voter: could you please suggest what is going wrong in the question so that I can accordingly modify it? Thanks! | |
| Feb 15, 2019 at 13:35 | review | Close votes | |||
| Feb 15, 2019 at 23:30 | |||||
| Feb 15, 2019 at 13:31 | comment | added | Ankitp | @Alexandre This argument only works if the maximum is attained at a point which has all coordinates same because the points are i.i.d. | |
| Feb 15, 2019 at 13:19 | comment | added | Alexandre Eremenko | The maximum is equal to the maximum of $|f|$ is exists: take $\mu_j$ to be point masses at $x_j$ where $x=(x_1,...,x_n)$ is the point of maximum of $|f|$. If $|f|$ has no maximum, then your expression also has no maximum. | |
| Feb 15, 2019 at 12:47 | history | asked | Romeo | CC BY-SA 4.0 |