User jennifer gao - MathOverflow

Rate of change of mass of a parameterized region

2012-05-08T20:52:23Z

Let $R_t$ be a family of compact, simply connected regions in the plane defined by

$R_t = \{x\in\mathbb{R}^2 : h(x) \leq t\}$

for all $t$, where $h(x)$ is some nicely behaved smooth function. Suppose $f(x)$ is a probability density on $\mathbb{R}^2$ and define

$M(t) = \iint_{R_t} f(x) dA$

for all $t$. Is it true that

$\frac{dM}{dt}|_{t=t_0} = \int_{\partial R_{t_0}} f(x) /\|\nabla h\| ds$

where $ds$ denotes integration with respect to arc length? If not, what is the right expression for $\frac{dM}{dt}$? I assume this is some well-known first-year calculus-type problem but I can't find it stated in any context (it may very well be a common homework problem though I've not seen it).

Solving a particular nonlinear system of equalities

2012-04-23T16:00:42Z

How hard is it to solve a system of equalities of the form

$a_{k1}x_1^k + \cdots + a_{kn}x_n^k = b_k$

with $k$ ranging from $1$ to $m$? I realize that this is a non-convex system but it seems plausible that it might be tractable. If the theoretical complexity is bad, how might one go about finding a feasible solution to such a system in practice? In my case I have $m < n \leq 10$. We also happen to know that $x_i \geq 0$, in case that helps. Other suggestions for tags are welcome.

Connected level sets

2012-02-21T19:14:09Z

This may be an ill-posed question, but suppose I have a collection of continuous, bounded, scalar-valued nonnegative functions $f_1(x,y),\dots,f_n(x.y)$ defined on the closed unit disk. Given a collection of scalars $a_1,\dots,a_n$, define

$R_i = \{(x,y) : f_i(x,y) + a_i \leq f_j(x,y) + a_j \ \forall j \ \} $

for each index $i$. Are there any sufficient conditions I can impose on these functions that will guarantee that the $R_i$ are connected for all $a_i$? It works if the functions are linear, for example (since the $R_i$ end up being convex), but I'd like something as general as possible.

Locus of points where difference in gravitational forces is constant

2012-02-05T14:27:55Z

Is there a name for the curve in the plane defined by

$a/\|x - p\|^2 - b/\|x - q\|^2=\mathrm{constant}$

where $a$ and $b$ are fixed numbers and $p$ and $q$ are fixed points? How about if I don't square the denominators? How about if $a$ and $b$ are both $1$?

Conditions under which a given scheme converges

2011-11-28T22:34:30Z

I'm sorry in advance for how long this question is. Suppose I have a continuous function $f:\mathbb{R}^n \rightarrow \Delta_{n-1}$, where we think of the simplex $\Delta_{n-1}$ as the set

$\Delta_{n-1} = {x\in \mathbb{R}^n : \sum_i x_i = 1, x_i \geq 0}$.

Suppose that this function $f$ has the following "nice" properties:

$f$ is translation-invariant, in the sense that $f(x_1,\dots,x_n) = f(x_1+t,\dots,x_n+t)$ for all $t$.
For any point $x=(x_1,\dots,x_n)$, if we increase the $i$th entry of $x$, the corresponding $i$th entry of $f(x)$ approaches $1$. In other words, we have $\lim_{t \rightarrow \infty} f(x_1,\dots, x_i + t, \dots, x_n)_i = 1$.
$f$ has a "monotonicity property", in the following sense: If $x = (x_1,\dots,x_n)$ and $\tilde{x} = (x_1,\dots,x_i+t,\dots,x_n)$ where $t > 0$, then $f(x)_i < f(\tilde{x})_i$ (with no other conditions on the other elements).

Now, let's define a vector field $V:\mathbb{R}^n \rightarrow \mathbb{R}^n$ in the following way: at point $(x_1, \dots, x_n)$, we select the index(es) $i$ such that $f(x_1,\dots,x_n)_i$ is maximal. Then, we let $V(x_1,\dots,x_n)$ be a vector with $-1$ in the components corresponding to $i$, and $0$ everywhere else. So, for example, if $f(x_1,x_2,x_3) = (0.1, 0.7, 0.2)$, we'd have $V(x_1,x_2,x_3) = (0,-1,0)$.

My question now is: suppose we start at some point $x$ and "follow" this vector field $V$ (I hope that the notion of "following" a vector field is well-defined -- I don't even know if that is the case here). Are there any "nice" conditions under which I'm guaranteed to eventually end up at a point where $f(x) = (1/n ,\dots, 1/n)$? Using an argument that Neil Strickland gave in an earlier thread,

http://mathoverflow.net/questions/67318/map-from-simplex-to-itself-that-preserves-sub-simplices

it seems that my map $f$ must be surjective, thus the barycenter of the simplex is at least in the image of $f$. Thanks!

Minimum distance to a sampled point with given pdf

2011-12-09T23:02:06Z

Let $f(x)>0$ be a probability density function defined on the unit square $[0,1]^2$ in $\mathbb{R}^2$. Suppose that we take $N$ independent samples, $X_1,\dots,X_N$, of $f$. Now, sample a point $Y$, UNIFORMLY, on the unit square. What's the expected distance from $Y$ to its nearest neighbor? It would seem to me that it should be something like $\frac{1}{\sqrt{N}}\int_{[0,1]^2} 1/\sqrt{f(x) }dA $. I

Distributing points with respect to a concave function

2011-06-09T20:01:39Z

Suppose I have a concave function defined on the unit interval such that $f(0) = f(1) = 0$ and $\int_0^1 f(t) dt = \alpha$, where $\alpha$ is "small" (say $0.01$ or thereabouts). Say I distribute $n$ points $x_1,\dots,x_n$ on the unit interval and consider the function $F(x_1,\dots,x_n) = \int_0^1 f(t) \cdot \min_i{|x_i - t|} dt$. Is there a lower bound on $F$ as a function of $\alpha$ and $n$? If $n=1$, I can show that a lower bound is $\alpha/6$, so I'm curious if something like $\alpha/(6n)$ holds in general.

Proving that a function's image contains (1/n,...,1/n)

2011-07-12T23:35:06Z

This question is a follow-up to a previous question answered by Neil Strickland:

http://mathoverflow.net/questions/67318/map-from-simplex-to-itself-that-preserves-sub-simplices

Let $B$ denote the closed unit ball in $\mathbb{R}^2$ and let $\Delta_{n-1}$ denote the $(n-1)$-simplex. I have a continuous function $f(x_1,\dots,x_n):B^n \rightarrow \Delta_{n-1}$ defined for all subsets $\lbrace x_1,\dots,x_n\rbrace \subset B$ of size $n$ that satisfy $x_i \neq x_j$ for all pairs $i,j$ (in other words, the function is only defined if all of the $n$ arguments are distinct). This function has the property that, if $\sigma$ denotes a permutation, then $f(\sigma(x_1,\dots,x_n)) = \sigma(f(x_1,\dots,x_n))$. In other words, permuting the arguments of the function merely permutes the output. My question is: are there non-trivial sufficient conditions on $f$ under which the point $(1/n , \dots, 1/n)$ lies in the image of this map? (or, even better, is this always the case?)

Here's one property of the map $f$ that I can add regarding the requirement that arguments be distinct: if $\lbrace \mathbf{x}_k \rbrace$ is a sequence of $n$-tuples (with distinct entries) in $B$ that converges to an $n$-tuple $\bar{\mathbf{x}}$ with (possibly) non-distinct entries, then the limit of $f(\mathbf{x}_k)$ exists if and only if, for each pair of entries $x_i^k$ and $x_j^k$ in the $n$-tuple, the unit direction vector from $x_i^k$ to $x_j^k$ (i.e. $\frac{x_i^k - x_j^k}{||x_i^k - x_j^k||}$) has a limit.

Polar interpretation of convexity

2011-06-21T20:02:24Z

Let $C$ be a convex polygon in the plane containing the origin, and let $r(\theta)$ for $\theta\in[0,2\pi)$ be a parametrization of its boundary. Is there a condition on $r$ that is equivalent to (or necessary for) convexity of $C$?

Map from simplex to itself that preserves sub-simplices

2011-06-08T21:55:51Z

I believe this may be a standard algebraic topology problem, so I apologize in advance if this belongs in stackexchange (it's not a homework problem, however, and came about in a research context). I've got a continuous map $f$ from the $n$-simplex to itself, such that the image of every strict sub-simplex is itself. So, each vertex gets mapped to itself, as does each edge, and so on and so forth. Does it follow that $f$ must be surjective?

Thank you!

A lower bound of a particular convex function

2011-04-16T19:15:18Z

Hello, I suspect this reduces to a homework problem, but I've been a bit hung up on it for the last few hours. I'm trying to minimize the (convex) function $f(x) = 1/x + ax + bx^2$ , where $x,a,b>0$. Specifically, I'm interested in the minimal objective function value as a function of $a$ and $b$. Since finding the minimizer $x^*$ is tricky (requires solving a cubic), I figured I'd try and find a lower bound using the following argument: if $b=0$, the minimizer is $x=1/\sqrt{a}$ and the minimal value is $2\sqrt{a}$. If $a=0$, the minimizer is $x=(2b)^{-1/3}$ and the minimal value is $\frac{3\cdot2^{1/3}}{2}b^{1/3}$. Therefore, one possible approximate solution is the convex combination

$(\frac{a}{a+b})\cdot2\sqrt{a} + (\frac{b}{a+b})\cdot\frac{3\cdot2^{1/3}}{2}b^{1/3}$.

Numerical simulations suggest that the above expression is a lower bound for the minimal value. Does this follow from some nice result about parameterized convex functions? It seems like it shouldn't be hard to prove. I guess in a nutshell I just want to prove that for all $x,a,b>0$ we have

$(\frac{a}{a+b})\cdot2\sqrt{a} + (\frac{b}{a+b})\cdot\frac{3\cdot2^{1/3}}{2}b^{1/3} \leq 1/x + ax + bx^2$. Thanks!

EDIT: It also appears that if I take the convex combination

$(\frac{a^{3/5}}{a^{3/5}+b^{2/5}})\cdot2\sqrt{a} + (\frac{b^{2/5}}{a^{3/5}+b^{2/5}})\cdot\frac{3\cdot2^{1/3}}{2}b^{1/3}$

then I get a tighter lower bound, and in fact the lower bound is within a factor of something like $3/2$ of the true minimal solution.

Applications of linear fractional relationship

2011-04-05T20:30:52Z

This may be the wrong forum, but are there any natural contexts (physics, economics, etc.) in which one might observe the relationship $y = ax/(bx+c)$ between a pair of variables $x$ and $y$? General linear fractional expressions come up all the time in optimization but I've had a hard time finding a really simple and natural context where this might arise. Thanks!

Comment by Jennifer Gao

2012-05-11T00:26:00Z

Thanks to both of you, I wasn't familiar with that result! That clears this question up for me nicely.

Comment by Jennifer Gao

2012-04-23T18:22:15Z

Thanks, Chris and Brian -- this is very helpful. Brian: Both $m$ and $n$ are quite small, say $10$ or so (and I have amended the question appropriately). Is there some sort of branch-and-bound based approach that might be feasible here? Chris: The actual problem is one communicated to me by a colleague involving estimation of some physical constants, so I do not have more detail yet to give (it will be forthcoming after we discuss it in the near future)

Comment by Jennifer Gao

2012-02-21T19:59:28Z

Thanks. The disk should be closed and I'll require that the functions be continuous and bounded.

Comment by Jennifer Gao

2011-07-13T21:38:45Z

I just now added one more condition on the map that may be helpful. Also, thanks to Neil and gowers for the helpful comments.

Comment by Jennifer Gao

2011-07-13T06:01:44Z

Sorry, I think I didn't explain this properly (or I've misunderstood your explanation); what I meant was that $f$ is a map that takes an $n$-tuple of points in $B$ and spits out a point in $\Delta_{n-1}$, and that $f$ is defined if each of the $n$ arguments in the $n$-tuple is distinct. So for example, if $n=2$, then the $2$-tuple $( (1/2,1/2),(1/3,1/3)$ is allowed, but $((0,1),(0,1))$ is not. This doesn't seem to be the same as "Removing from $B$ all points where two coordinates coincide". Did I miss something? Thanks!

Comment by Jennifer Gao

2011-04-17T20:40:22Z

@Suvrit: is it? The expression for the roots of a cubic looks pretty complicated to me, and the lower bound is just a pair of terms.

Comment by Jennifer Gao

2011-04-17T08:29:54Z

Sorry, I don't understand -- how does the "splitting" work?

Comment by Jennifer Gao

2011-04-05T22:32:15Z

Thanks for that!