User gb - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T12:51:25Z http://mathoverflow.net/feeds/user/21816 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/128879/when-does-the-finite-union-of-convex-sets-have-a-hole-in-it When does the finite union of convex sets have a hole in it? GB 2013-04-27T00:26:56Z 2013-04-28T01:49:13Z <p>Let $f_1, \dots, f_j$ be convex functions from $\mathbb{R}^n \to \mathbb{R}$. I am trying to develop a test that decides whether or not the set $\{x | f_1(x) \le k_1\} \cup \dots \cup \{x | f_n(x) \le k_n\}$ has a hole in it of any size (the alternative is that the set is homeomorphic to the unit ball, maybe plus a few lower-dimensional "fingers").</p> <p>Is anything known about this problem?</p> <p>Editing in some extra information that is specific to my particular use for this algorithm. In my algorithm, $n$ of the convex sets that I'm unioning together are the coordinate planes (i.e. $\{x | x_j = 0\}$), and there are exactly $n$ additional convex sets that I care about (so $j = 2n$).</p> http://mathoverflow.net/questions/127163/what-is-the-complexity-of-finding-the-number-mod-2-of-multicolored-edges-on-a-l What is the complexity of finding the number (mod 2) of multicolored edges on a loop? GB 2013-04-11T00:47:36Z 2013-04-11T00:47:36Z <p>Let $C$ be a circuit that maps $n$-length bitstrings to elements of $\{0, 1, 2\}$. Arrange the $n$-length bitstrings in a giant loop: $0^n$ is connected to $1^n$ and $0^{n-1}1$, $0^{n-1}1$ is connected to $0^n$ and $0^{n-2}10$, etc. An edge of this loop is <em>multicolored</em> if it connects $x$ and $y$ but $C(x) \ne C(y)$.</p> <p>I want to decide whether there are an even or odd number of multicolored edges on the loop. What is the computational complexity of this problem?</p> http://mathoverflow.net/questions/120884/geometric-interpretations-of-matrix-inverses Geometric interpretations of matrix inverses GB 2013-02-05T17:41:16Z 2013-02-05T18:03:36Z <p>$A$ is an invertible $n \times n$ matrix. Interpret each row of $A$ as a point in $\mathbb{R}^n$; then these $n$ points define a unique hyperplane in $\mathbb{R}^n$ that passes through each point (this hyperplane does <em>not</em> intersect the origin).</p> <p>Under this geometric interpretation, $A^{-1}$ has an interesting property: the normal vector to the hyperplane is given by the row sums of $A^{-1}$ (i.e. $A^{-1} * 1$, where $1 = \langle 1, \dots, 1 \rangle^T$).</p> <p>Within this same geometric interpretation of $A$, what other interesting properties does $A^{-1}$ have? Do the individual entries of $A^{-1}$ have geometric meaning? How about the column sums (besides the obvious <em>row sums of $A^T$</em> intepretation)?</p> http://mathoverflow.net/questions/118339/is-there-a-general-process-for-conditioning-a-stochastic-process-above-a-boundary Is there a general process for conditioning a stochastic process above a boundary? GB 2013-01-08T07:59:17Z 2013-02-01T16:00:10Z <p>$(X_t, Y_t)$ is a two-dimensional Markov stochastic process that runs on time interval $[0, t_f]$. Given its transition function $a(x, y | x', y')$, I would like to condition the process on $\inf_{s \in [0, t_f]} X_s \ge k$ and find the new transition function.</p> <p>Can the problem be solved at this level of generality? Or must we dig into the specifics of $a$ to find a solution on a case-by-case basis?</p> http://mathoverflow.net/questions/119608/does-this-result-exist-in-the-literature Does this result exist in the literature? GB 2013-01-22T23:18:17Z 2013-01-23T05:15:35Z <p>Cover a table with a tablecloth, crumple it up in the middle (while still leaving the edges hanging over the edge of the table), then stab the folds with a pin. You will almost surely poke an odd number of holes in the tablecloth, because one end of the pin is above the tablecloth, the other is below, and each hole indicates one instance of the pin changing sides (the only exception is if your stab lies perfectly tangent to a fold of the tablecloth).</p> <p>I suspect that this generalizes. I hope that something like this is true:</p> <p>Let $X$ be a subset of $\mathbb{R}^n \times \mathbb{R}^m$ that is homeomorphic to $\mathbb{R}^n$. For any $r \in \mathbb{R}^n$, let $D(r) = \{ s \in \mathbb{R}^m | (r, s) \in X \}$. Suppose $D(r)$ is never empty for any $r \in \mathbb{R}^n$. Then $D(r)$ almost always (with respect to Lebesgue measure) has an odd number of elements.</p> <p>In other words, we have crumpled an $n$-dimensional tablecloth into $m$ additional dimensions (while still leaving it hanging over the edges of our $n$-dimensional table), then stabbed it with an $m$-dimensional pin, hopefully in an odd number of places.</p> <p>Is this a known result? It smells a lot like Sperner's Lemma (which contains a similar statement about oddness), but I'm not entirely sure how.</p> http://mathoverflow.net/questions/116895/can-we-express-a-one-dimensional-raised-bessel-bridge-as-a-function-of-a-single-b Can we express a one-dimensional raised Bessel Bridge as a function of a single Brownian Motion? GB 2012-12-20T19:15:53Z 2012-12-20T21:21:15Z <p>A Bessel Bridge is a Brownian Motion, conditioned such that $B(0) = B(1) = 0$ and $B([0, 1]) \ge 0$. A raised Bessel Bridge is a generalization of this: it's a Brownian Motion conditioned such that $C(0) = a, C(1) = b, C([0, 1]) \ge 0$ for some nonnegative constants $a, b$.</p> <p>My end goal is to find a density function for the integral of a random realization of a raised Bessel Bridge. I plan to approach this problem as follows: the Feynman-Kac formula gives an expression for $E(e^{-u \int_0^1 V(x(t)) dt})$, where $x(t)$ is a Brownian Motion, $u$ is a constant, and $V$ is any function. If I choose $V$ such that $V(x(t))$ is a raised Bessel Bridge, then this information is sufficient to compute the desired density function (simply take a Fourier Transform).</p> <p>So, my question: what function $V$ makes the process $V(x(t))$ a raised Bessel Bridge, where $x(t)$ is a Brownian Motion?</p> http://mathoverflow.net/questions/112447/can-we-efficiently-compute-a-third-nash-equilibrium-given-two Can we efficiently compute a third Nash Equilibrium, given two? GB 2012-11-15T03:35:26Z 2012-11-15T03:35:26Z <p>A finite, two-player, nondegenerate, symmetric game is defined by a nondegenerate $n \times n$ <em>payoff matrix</em> $A$. If player 1 plays strategy $i$ and player 2 plays strategy $j$, then player 1's payoff is $A_{ij}$ and player 2's payoff is $A_{ji}$. It is well known that the problem of computing a symmetric Nash Equillibrium in such a game is PPAD-complete (PPAD lies between P and NP but is probably intractable).</p> <p>Wilson's <em>Oddness Theorem</em> states that there are an odd number of symmetric Nash Equilibria in such games. This gives rise to my question. Suppose we have found two equilibria of $A$. Given these, what is the computational complexity of computing one more?</p> <p>Or, more generally - given $2k$ equilibria, what is the complexity of computing another?</p> http://mathoverflow.net/questions/112102/computing-a-density-function-for-the-integral-of-a-stochastic-process-given-its Computing a density function for the integral of a stochastic process, given its transition function GB 2012-11-11T18:34:48Z 2012-11-11T19:09:53Z <p>$P$ is a one-dimensional Markov stochastic process that runs on time interval $[0, t_f]$. I know its transition function: $P(0) = x_0$ and for any $0 \le t_a &lt; t_b \le t_f$, the function $f(x_b | x_a, t_a, t_b)$ describes the probability that $P(t_b) = x_b$ given that $P(t_a) = x_a$ (so $f$ is a density function in its first parameter).</p> <p>Now, let $I$ be the random variable described by $\int_0^{t_f} P(s) ds$ for a random realization of $P$. Is it possible to find a density function for $I$ in terms of $f$ and $x_0$?</p> http://mathoverflow.net/questions/112010/integrating-a-bessel-bridge Integrating a Bessel Bridge GB 2012-11-10T18:40:37Z 2012-11-10T19:06:48Z <p><strong>Preliminaries</strong></p> <p>An order-3 <em>Bessel Process</em> is the one-dimensional stochastic process $X$ described by $X(t) = \sqrt{W_1(t)^2 + W_2(t)^2 + W_3(t)^2}$, where each $W_k$ is an independent Brownian Motion. It is known that this process is equivalent to a Brownian Motion conditioned to always be positive.</p> <p>A <em>Bessel Bridge</em> is a Bessel Process on time interval $[0, 1]$, conditioned to have start point $(0, x_0)$ and end point $(1, x_f)$.</p> <p><strong>My Question</strong></p> <p>I am trying to find a density function for the random variable $\int_0^1 \beta_3(t) dt$, where $\beta_3(t)$ is a random realization of an order-3 Bessel Bridge.</p> <p><strong>A Possibly Useful Fact</strong></p> <p>When $x_0 = x_f = 0$, the Bessel Bridge is called a <em>Brownian Excursion Process</em>, and the density function for its integral is known.</p> <p>Thanks!</p> http://mathoverflow.net/questions/109254/when-is-a-sublevel-set-path-connected When is a sublevel set path-connected? GB 2012-10-09T22:14:57Z 2012-10-10T08:59:52Z <p>I am trying to completely characterize the conditions on $f : \mathbb{R}^n \to \mathbb{R}$ under which $\{x | f(x) \le 0 \}$ is path-connected. There are many obvious conditions that are sufficient (e.g. $f$ concave), but is there any suite of conditions that is necessary and sufficient?</p> <p>We can assume $f$ is continuous.</p> <p>If you have any ideas or recommended reading, I'd love to hear about it. Thanks!</p> http://mathoverflow.net/questions/109169/when-is-x-ge-0-fx-le-0-path-connected When is $\{ x \ge 0 | f(x) \le 0\}$ path-connected? GB 2012-10-08T18:57:10Z 2012-10-08T18:57:10Z <p>I'm trying to determine the conditions on $f : \mathbb{R}^n_{\ge 0} \to \mathbb{R^n}$ under which $\{ x \ge 0 | f(x) \le 0 \}$ is path-connected. We can assume that $f$ is continuous and concave.</p> <p>Any advice?</p> http://mathoverflow.net/questions/107993/does-quadratic-programming-get-easier-when-its-described-by-a-diagonal-matrix Does Quadratic Programming get easier when it's described by a diagonal matrix? GB 2012-09-24T17:20:33Z 2012-09-24T17:43:52Z <p>Generally, Quadratic Programming solves the problem</p> <p>$$\text{Given }Q, c, A, b,\text{ choose }x \text{ to maximize } x^TQx + c^Tx \text{ subject to } Ax \le b$$</p> <p>In this form, Quadratic Programming is NP-hard. For my purposes, I happen to know that $b$ and $c$ are $0$ and $Q$ is diagonal. Thus, the problem looks like:</p> <p>$$\text{Given }q, A, \text{ choose } x \text{ to maximize } q \cdot \langle x_1^2, \dots, x_n^2 \rangle \text{ subject to } Ax \le 0$$</p> <p>Does the problem now admit an efficient solution?</p> <p>The problem is not entirely theoretical, so I am somewhat interested in approximation methods if no exact solution can be found efficiently.</p> <p>Edit: we can introduce the additional constraint $\sum_j x_j \le 1$ to prevent unbounded growth of optimization from scaling our solutions. This works because the condition $x \ge 0$ is already built into $A$.</p> http://mathoverflow.net/questions/95068/is-the-simplex-method-still-polynomial-when-all-inequalities-are-through-the-orig Is the Simplex Method still polynomial when all inequalities are through the origin? GB 2012-04-24T20:47:16Z 2012-04-24T21:29:51Z <p>Hello,</p> <p>I want to solve a linear program using the simplex method, and I know that all my inequalities will pass through the origin (therefore, either my initial solution of (0, ... , 0) is optimal, or the program is unbounded; I'm only really interested in distinguishing between these two cases).</p> <p>So here's how I think the algorithm would work: Step one is to pick a pivot variable. Step two - and here's where I think things break down - is to find the equation with the smallest value of the constant to the coefficient of the pivot variable. But since my inequalities all pass through the origin, the constant is 0 every time, so all equations are an equally valid choice for the pivot. This reduces the Simplex Method to a brute-force search of the set of basic variables, which would make it run in above-polynomial time.</p> <p>Is this correct? Or am I missing some feature of the Simplex Method that handles this case?</p> <p>Thanks in advance!</p> http://mathoverflow.net/questions/92777/how-do-you-tell-if-a-system-of-linear-inequalities-has-a-solution How do you tell if a system of linear inequalities has a solution? GB 2012-03-31T21:41:32Z 2012-04-01T05:27:50Z <p>A naive solution would be to optimize a dummy variable via linear programming and see if a result is returned. I imagine there must be a more direct way.</p> http://mathoverflow.net/questions/90103/finding-the-top-or-bottom-vertex-of-a-simplex Finding the "top" or "bottom" vertex of a simplex GB 2012-03-03T02:57:21Z 2012-03-03T05:14:13Z <p>A vertex $v$ of a simplex in $\mathbb{R}^n$ is a "top" vertex if there exists a point $p \neq v$ in the simplex with $v \ge p$ (i.e. $v_1 \ge p_1$, ... , $v_n \ge p_n$). Similarly, $v$ is a "bottom" vertex if there exists $p \neq v$ with $v \le p$.</p> <p>It's not hard to show that any simplex has at least one top or bottom vertex. I'm looking for a test I can run (preferably in polynomial time) that identifies at least one such vertex, and whether it's top or bottom.</p> <p>Thanks in advance for any advice!</p> http://mathoverflow.net/questions/89905/how-do-you-tell-if-the-span-of-a-set-of-vectors-enters-the-most-positive-sector-o How do you tell if the span of a set of vectors enters the most positive sector of a graph? GB 2012-02-29T22:08:35Z 2012-03-01T17:15:25Z <p>I have $k$ linearly independent vectors in $\mathbb{R}^n$. I want to know if the span of these vectors (i.e. the set of points in $\mathbb{R}^n$ that can be described by linear combinations of these vectors) intersects the portion of $\mathbb{R}^n$ where all the axes are positive (e.g. the first quadrant in $\mathbb{R}^2$, the first octant in $\mathbb{R}^3$, etc.).</p> <p>Is there a test I can run on my vectors that will answer this question?</p> http://mathoverflow.net/questions/128879/when-does-the-finite-union-of-convex-sets-have-a-hole-in-it Comment by GB GB 2013-04-27T02:49:52Z 2013-04-27T02:49:52Z Man, that is a cool answer you linked to. I do have a way to test intersections, so that will do perfectly. http://mathoverflow.net/questions/128879/when-does-the-finite-union-of-convex-sets-have-a-hole-in-it Comment by GB GB 2013-04-27T01:09:32Z 2013-04-27T01:09:32Z 1. Yes, it's the union, not the intersection of the sets (the intersection would be convex =) ). 2. Yes, I am attempting a floating-point algorithm. Rather than place restrictions on the sets, I'm hoping to use standard convex optimization techniques as a subroutine (the $\epsilon$-fudginess in these techniques is okay; I'd be fine with an algorithm that reports &quot;the functions come within $\epsilon$ of being hole-less&quot;). http://mathoverflow.net/questions/112422/largest-subarray-with-average-geq-k Comment by GB GB 2012-11-15T04:00:05Z 2012-11-15T04:00:05Z You can easily get down to $O(n \log n)$ by first sorting the array, then checking the subarray [0..0], then [0..1], then [0..2], etc. http://mathoverflow.net/questions/112102/computing-a-density-function-for-the-integral-of-a-stochastic-process-given-its Comment by GB GB 2012-11-11T19:10:10Z 2012-11-11T19:10:10Z Ah, yes it is, thank you. I just edited that detail into the post. http://mathoverflow.net/questions/112067/sperners-lemma-and-paths-from-one-side-to-the-opposite-one-in-a-grid Comment by GB GB 2012-11-11T18:23:37Z 2012-11-11T18:23:37Z Computationally speaking, it is PPAD-complete to find a three-colored simplex per Sperner's Lemma. <a href="http://en.wikipedia.org/wiki/PPAD_(complexity" rel="nofollow">en.wikipedia.org/wiki/PPAD_(complexity</a>) http://mathoverflow.net/questions/109169/when-is-x-ge-0-fx-le-0-path-connected Comment by GB GB 2012-10-08T19:21:15Z 2012-10-08T19:21:15Z Yes, the co-domain of $f$ is meant to be $\mathbb{R}^n$. By concave, I mean that it is concave on each index: for any $\lambda \in [0, 1]$, $f(\lambda x + (1 - \lambda)y) \ge \lambda f(x) + (1 - \lambda) f(y)$ (the inequality is pointwise). I think the sublevel set is only necessarily path-connected if the domain of $f$ is $\mathbb{R}^n$, not $\mathbb{R}^n_{\ge 0}$. http://mathoverflow.net/questions/97257/a-brownian-motion-inspired-paradox Comment by GB GB 2012-05-17T20:50:44Z 2012-05-17T20:50:44Z $t_f$ is finite, but I think $Z$ is still an infinitely large set. It's not hard to show that, on any neighborhood $N$ of some fixed $t$, $inf B(N) &lt; B(t) &lt; sup B(N)$ with probability 1, which implies that the path returns to $B(t)$ on any $N$ with probability 1. Apologies for misplacing this question, I guess I'm still figuring this place out. It did arise during research, but I'll admit it was a tangent rather than the actual research topic. http://mathoverflow.net/questions/95213/mapping-sets-to-orthants Comment by GB GB 2012-04-26T18:56:44Z 2012-04-26T18:56:44Z Hey, thanks for your response. I'm new to MO - for future reference, what about this is not an MO question? What sort of things should I be asking? http://mathoverflow.net/questions/95068/is-the-simplex-method-still-polynomial-when-all-inequalities-are-through-the-orig/95076#95076 Comment by GB GB 2012-04-24T21:45:18Z 2012-04-24T21:45:18Z I looked into it more - you're completely right, and now I'm trying to remember why I was so sure Simplex was strongly polynomial in the first place. I may have found one of the cases on which it's exponential. I found a source that says there are no known strongly-polynomial linear programming algorithms, and the existence of such an algorithm is a major open question. Thanks for your help! http://mathoverflow.net/questions/90103/finding-the-top-or-bottom-vertex-of-a-simplex/90106#90106 Comment by GB GB 2012-03-03T20:17:03Z 2012-03-03T20:17:03Z This is very helpful - thank you.