most recent 30 from http://mathoverflow.net 2013-05-25T23:12:45Z http://mathoverflow.net/feeds/user/7576 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/125867/concavity-of-a-ratio-of-kullback-leibler-divergences Hedonist 2013-03-29T01:58:56Z 2013-03-29T05:18:23Z

<p>For $0\leq r\leq 1$ and $0 &lt; p &lt; 1$, define the Kullback-Leibler divergence between the Bernoulli(r) and Bernoulli(p) distributions as: $D(r||p) := r\log\frac{r}{p} + \bar{r}\log\frac{\bar{r}}{\bar{p}}$ where $\bar{r}:=1-r, \bar{p}:=1-p.$</p> <p>Fix $0&lt;\theta_0,\theta_1&lt;1$ and $p.$</p> <p>Consider the function </p> <p>$$\eta(r) := \frac{D(r\theta_1+\bar{r}\theta_0||p\theta_1+\bar{p}\theta_0)}{D(r||p)}.$$</p> <p>This function can be made continuous at $r=p$ if we define $\eta(p)$ suitably.</p> <p>Plots for different values of $p,\theta_0,\theta_1$ show that $\eta(r)$ is concave in $r$. The second derivative of $\eta(\cdot)$ seems quite involved though. Perhaps I am ignorant of some sophisticated techniques that could be useful here. I would be grateful for a proof that $\eta(\cdot)$ is concave. Or any ideas that could help in proving such a thing.</p>

http://mathoverflow.net/questions/94143/useful-lower-bound-on-an-infinite-sum Hedonist 2012-04-15T19:33:33Z 2012-06-17T19:14:22Z

<p>Fix integer $s.$ I have encountered the following infinite sum.</p> <p>$$\sum_{k=0}^\infty \Pi_{l=1}^k\left[1-(1-2^{-l})^s\right]$$</p> <p>Is there a useful lower bound on this expression? For instance, if $s=1,$ this gives the series</p> <p>$$\sum_{k=0}^\infty 2^{-k(k+1)/2}.$$</p> <p>Are there good closed form expressions that describe lower bounds on this quantity?</p>

http://mathoverflow.net/questions/89820/generalization-of-renyi-maximal-correlation Hedonist 2012-02-29T01:51:26Z 2012-02-29T01:51:26Z

<p>Given a probability space, the Renyi maximal correlation of two sigma fields $\mathcal{F}, \mathcal{G}$ is defined as:</p> <p>$$\rho(\mathcal{F};\mathcal{G}) = \sup \frac{\mathbb{E}XY}{\sqrt{\mathbb{E}X^2.\mathbb{E}Y^2}}$$</p> <p>where the supremum is taken over all $\mathcal{F}$-measurable real-valued functions $X$ and $\mathcal{G}$-measurable real-valued functions $Y$ such that $\mathbb{E}X=0, \mathbb{E}Y=0$ and $\mathbb{E}|X|>0, \mathbb{E}|Y|>0.$</p> <p>A natural generalization seems to be the following. Let $p>1$ and let $p^\prime$ be the H\"{o}lder conjugate of $p,$ that is, $\frac{1}{p}+\frac{1}{p^\prime}=1.$ Define </p> <p>$$\rho_p(\mathcal{F};\mathcal{G}) = \sup \frac{\mathbb{E}XY}{(\mathbb{E}|X|^p)^{1/p}.(\mathbb{E}|Y|^{p^\prime})^{1/p^\prime}}$$</p> <p>where the supremum is taken over all $\mathcal{F}$-measurable real-valued functions $X$ and $\mathcal{G}$-measurable real-valued functions $Y$ such that $\mathbb{E}X=0, \mathbb{E}Y=0$ and $\mathbb{E}|X|>0, \mathbb{E}|Y|>0.$</p> <p>For $p=2,$ we get the Renyi maximal correlation. Is this quantity interesting? Is it well-studied? It would be great to have any references relating to this.</p>

http://mathoverflow.net/questions/88544/on-two-dimensional-gaussian-integrals Hedonist 2012-02-15T19:34:34Z 2012-02-16T09:57:16Z

<p>Fix $\epsilon, 0\leq \epsilon\leq 1/2.$ Let $Z_1,Z_2$ be zero mean, unit variance Gaussian random variables which are jointly Gaussian with $\mathbb{E}Z_1Z_2=-(1-2\epsilon)\leq 0.$</p> <p>Then, </p> <p>$$P(Z_1Z_2>0)\geq \epsilon.$$</p> <p>This curious fact popped out of some calculations I was doing using the Central Limit Theorem. I wonder if it can be proved in some easy way by directly working with the double integral.</p> <p>I also believe that the inequality is strict when $0&lt;\epsilon&lt;1/2.$ Can this be shown?</p>

http://mathoverflow.net/questions/84854/on-the-faces-of-the-multicommodity-flow-polytope Hedonist 2012-01-04T03:18:15Z 2012-01-04T03:18:15Z

<p>Consider the multicommodity flow problem on an undirected graph with k source-destination pairs and specified capacity constraints on the edges. The set of concurrently achievable flows (R_1,R_2,...,R_k) forms a polytope. We know that for k=1 (Ford-Fulkerson theorem) and k=2 (T.C. Hu's theorem), the cutset outer bound on the flow region is tight, so the polytope is completely specified by the cutset bound inequalities. </p> <p>We also know that for k=3, the cutset outer bound is not tight in general. I am interested in what is known about the faces of this polytope for k=3.</p> <ol> <li>Is there a universal bound on the number of faces of the polytope (for all graphs where k=3)? Or is it the case that given any N>0, one can construct a graph with 3 source-destination pairs whose flow polytope has more than N faces?</li> <li>Is it possible to express the equations for the new faces, namely the faces that don't correspond to the cutset bound, in terms of some combinatorial quantities associated with the graph?</li> </ol> <p>Thanks.</p>

http://mathoverflow.net/questions/80335/computation-on-polymatroidal-functions Hedonist 2011-11-07T22:09:45Z 2011-11-07T22:09:45Z

<p>Consider a set function $f$ defined over a ground set $S,$ $f:2^S\to \mathbb{R}$ that satisfies the polymatroidal axioms. I am provided certain constraints on the value of the function for some subsets. I want to obtain a bound on the value of the function for the whole set $S.$ I would be glad to know some literature on algorithms for this kind of computation. If there is any software package that can perform these computations, that would be useful too.</p> <p>Thanks.</p>

http://mathoverflow.net/questions/41939/a-balls-and-colours-problem Hedonist 2010-10-12T19:53:08Z 2011-01-24T19:32:10Z

<p>A box contains n balls coloured 1 to n. Each time you pick two balls from the bin - the first ball and the second ball, both uniformly at random and you paint the second ball with the colour of the first. Then, you put both balls back into the box. What is the expected number of times this needs to be done so that all balls in the box have the same colour?</p> <p>Answer (Spoiler put through rot13.com): Gur fdhner bs gur dhnagvgl gung vf bar yrff guna a.</p> <p>Someone asked me this puzzle some four years back. I thought about it on and off but I have not been able to solve it. I was told the answer though and I suspect there may be an elegant solution.</p> <p>Thanks.</p>

http://mathoverflow.net/questions/41874/polynomials-over-z-evaluated-with-finite-field-arguments Hedonist 2010-10-12T05:46:43Z 2010-10-12T13:59:50Z

<p>A) Given a non-constant polynomial $q\in\mathbb{Z}[\alpha_1,\alpha_2,\ldots,\alpha_n],$ if we pick random $\omega_i\in\mathbb{F}$ (a finite field) uniformly and independently across $1\leq i\leq n,$ then, we know that $q(\omega_1,\omega_2,\ldots,\omega_n)\neq 0$ with high probability (i.e. the probability goes to 1 as $|\mathbb{F}|\rightarrow\infty$). </p> <p>B) Given another polynomial $r\in\mathbb{Z}[\alpha_1,\alpha_2,\ldots,\alpha_n],$ I am interested in determining if there exists a field $\mathbb{F}$ and a choice of $\omega_i\in\mathbb{F}$ which simultaneously satisfy $q(\omega_1,\omega_2,\ldots,\omega_n)\neq 0$ and $r(\omega_1,\omega_2,\ldots,\omega_n)= 0.$ Is there a theorem that gives necessary or sufficient conditions for this to happen? Is it true that if it happens over some field, then it happens over all sufficiently large finite fields?</p> <p>Is it true that if there is a point which satisfies $r=0$ and $q\neq 0,$ then "most" of the points satisfying $r=0$ also satisfy $q\neq 0,$ in similar spirit to the result A which is the case of $r$ being the zero polynomial?</p> <p>I am interested only in solutions over finite fields and not over their algebraic closures.</p> <p>Thanks a lot.</p>

http://mathoverflow.net/questions/88544/on-two-dimensional-gaussian-integrals/88566#88566 Hedonist 2012-02-15T22:07:10Z 2012-02-15T22:07:10Z

Thanks Didier. Can you give me a reference or quick proof of the formula? Thanks.

http://mathoverflow.net/questions/41939/a-balls-and-colours-problem/41953#41953 Hedonist 2010-10-12T23:48:49Z 2010-10-12T23:48:49Z

I agree with Ross Millikan's comment below. I have verified the claimed formula upto n=4. The only approach I can imagine for this problem is to draw out the Markov chain explicitly and find the expected time it takes for the chain to hit the one non-transient state.

http://mathoverflow.net/questions/41874/polynomials-over-z-evaluated-with-finite-field-arguments/41906#41906 Hedonist 2010-10-12T19:44:11Z 2010-10-12T19:44:11Z

Thanks Charles and Felipe for your help. I am currently going through Felipe's lecture notes which have been very useful too.

http://mathoverflow.net/questions/41874/polynomials-over-z-evaluated-with-finite-field-arguments Hedonist 2010-10-12T19:39:57Z 2010-10-12T19:39:57Z

Sorry about that. I had no idea how the algebraic closure of a finite field looks like. From your comment, I see that if one can find a choice of $\omega_i$ over the algebraic closure of a prime finite field, then one can find such $\omega_i$ over some finite extension of the prime field. Thanks.