User yaroslav bulatov - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T23:20:46Z http://mathoverflow.net/feeds/user/7655 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/52141/invariants-that-might-determine-graph-up-to-isomorphism Invariants that might determine graph up to isomorphism Yaroslav Bulatov 2011-01-15T02:11:26Z 2011-07-15T07:14:12Z <p>Are there any graph invariants which have a reasonable chance of capturing the graph up to isomorphism? In other words, some candidates for a function $f$ such that f(G)=f(H) iff G and H are isomorphic.</p> <p>For instance, in the case of trees, weighted graph polynomial (U-polynomial) of Welsh/Noble 1999 is a candidate because no counter-example has been found. Are there such candidates for general graphs?</p> <p><b>Clarification</b>: I'm interested in examples of functions which capture some graph invariant, are practical to compute, and are not yet proven to assign the same value to a pair of non-isomorphic graphs</p> http://mathoverflow.net/questions/35617/sanovs-theorem-and-chernoff-bound Sanov's Theorem and Chernoff bound Yaroslav Bulatov 2010-08-15T02:18:07Z 2011-04-26T22:04:40Z <p>Sanov's Theorem (p.292, Thomas/Cover "Elements of Information Theory" (1991)) says that probability of a hypothesis $E$ according to distribution $Q$ is bounded above by </p> <p>$$(n+1)^k \exp (-n D(P^* \|Q) )$$ where $D$ is KL-divergence, $k$ is the size of sample space and $P^*$ is an element of $E$ closest to $Q$ according $D(\cdot\|Q)$.</p> <p>This bound is quite loose for small $n$ because when $k=2$ and $E$ is simply connected, Chernoff's bound tells us that the probability is at most the following</p> <p>$$\exp (-n D(P^* \|Q) )$$</p> <p>Is there a natural restriction of $E$ that makes the bound above generalize to $k>2$? Alternatively, is there a natural restriction of $E$ and a modification of Sanov's theorem that gives it a similar level of tightness to Chernoff's bound for small n?</p> http://mathoverflow.net/questions/57336/lovasz-theta-function-integrality Lovasz theta function integrality Yaroslav Bulatov 2011-03-04T10:28:44Z 2011-03-05T11:29:19Z <p>Is anything known about Lovasz Theta Function taking integral value in non-perfect graphs? In particular, does integral value of Lovasz theta always coincide with the size of largest independent set?</p> <p>For instance, graph below is non-perfect, and its Lovasz theta function gives the independence number.</p> <p><img src="http://yaroslavvb.com/upload/save/non-perfect.png"></p> <p>Its true for a few other non-perfect graphs I tried, here's a <a href="http://mathematica-bits.blogspot.com/2011/03/computing-lovasz-theta-function.html" rel="nofollow">Mathematica package </a> I used to compute it</p> http://mathoverflow.net/questions/55002/maximal-clique-intersection-graphs Maximal clique intersection graphs Yaroslav Bulatov 2011-02-10T08:10:06Z 2011-03-04T20:03:45Z <p>Consider graph $T$ where nodes correspond to maximal cliques of some graph $G$ and two nodes can be connected if corresponding cliques intersect. Clique tree is an example when $T$ is required to be a tree and $G$ is chordal. I'm interested in graphs $T$ when tree/chordal requirements are relaxed, do they come up anywhere? </p> <p>Motivation: I come across these graphs when looking at approximate decompositions of Ising model entropy, searching for "maximal clique intersection graphs" only gives me literature related to clique trees/chordal graphs</p> http://mathoverflow.net/questions/51595/breaking-frustrated-loops-in-list-coloring-problem Breaking frustrated loops in list coloring problem Yaroslav Bulatov 2011-01-09T22:53:44Z 2011-01-11T03:22:28Z <p>Suppose we have a graph with $n$ vertices and $n$ lists of colors such that no vertex coloring of the graph using colors from given lists is a <a href="http://en.wikipedia.org/wiki/List_coloring" rel="nofollow">proper list coloring</a>. We can characterize the obstacle to proper list coloring in terms of frustrated cycles -- simple cycles such that every list coloring of the induced subgraph is improper.</p> <p>Given graph and set of color lists I'd like to delete a small number of vertices to break a large number of frustrated cycles.</p> <p>Is anything known about this problem, especially from algorithmic point of view?</p> http://mathoverflow.net/questions/39429/how-many-non-equivalent-sections-of-a-regular-7-simplex How many non-equivalent sections of a regular 7-simplex? Yaroslav Bulatov 2010-09-20T20:17:23Z 2010-12-22T19:14:12Z <p>Suppose we have a regular 7-<a href="http://en.wikipedia.org/wiki/Simplex" rel="nofollow">simplex</a> in $\mathbb{R}^8$ defined by vertices &lt;1,0,0,...,0>, &lt;0,1,0,..,0>,...,&lt;0,...,0,1>. A section is a 3-dimensional linear subspace of $\mathbb{R}^8$ that contains simplex <a href="http://en.wikipedia.org/wiki/Centroid" rel="nofollow">centroid</a> and three other points, each of which is a centroid of a non-empty set of simplex vertices. Two sections are equivalent if they are identical spaces under permutation of coordinates. In other words, when some permutation of coordinates is the bijection between two spaces. How many non-equivalent sections are there? Is there an efficient way to enumerate them?</p> <p>Motivation: visualizing symmetric priors over distributions over 8 outcomes</p> <p><b>Update 12/09</b> I tried an <a href="http://mathematica-bits.blogspot.com/2010/12/listing-interesting-sections-of-simplex.html" rel="nofollow">automatic search</a> and got 49 sections, same as Peter Shor below. Here they are. Note that grouping is a bit different since I group sections with or without unexpected centroids together.</p> <p>No empty vertices:</p> <p><img src="http://yaroslavvb.com/upload/save/sections0.png"></p> <p>One empty vertex:</p> <p><img src="http://yaroslavvb.com/upload/save/sections1.png"></p> <p>Two empty vertices:</p> <p><img src="http://yaroslavvb.com/upload/save/sections2.png"></p> <p>Three empty vertices:</p> <p><img src="http://yaroslavvb.com/upload/save/sections3.png"></p> <p>Four empty vertices:</p> <p><img src="http://yaroslavvb.com/upload/save/sections4.png"></p> <p><b>old stuff</b> Here's an illustration of solving this problem for 2-sections of a 3-simplex in 4 dimensions. There seems to be only 2 non-equivalent 2-sections (triangle and square). This solves the problem of visualizing entropy (contour lines) of distributions over 4 outcomes, and I'd like extend it to 8 outcomes.</p> <p><img src="http://yaroslavvb.com/upload/simplex-sections3.png"></p> http://mathoverflow.net/questions/40876/second-order-taylor-expansion-to-solve-system-of-equations Second order Taylor expansion to solve system of equations Yaroslav Bulatov 2010-10-02T21:37:20Z 2010-12-22T15:57:16Z <p>Suppose you need to solve $f(\mathbf{x})=\mathbf{0}$ where $f:\mathbb{R}^n \to \mathbb{R}^m$, $m,n>1$. Newton's method relies on first order Taylor expansion of f. Where can I find details of analogous method using second order Taylor expansion? I found at least a dozen numerical analysis books which mention this method, but give no details or applications</p> http://mathoverflow.net/questions/50090/do-singular-values-of-a-point-set-determine-its-shape Do singular values of a point set determine its shape? Yaroslav Bulatov 2010-12-21T19:47:06Z 2010-12-21T23:37:38Z <p>Suppose I have $k$ points in $d$ dimensions. Let A be a $k\times d$ matrix with $i$th row giving the coordinates of $i$th point. Do singular values of this matrix have an interpretation as some kind of geometric invariant?</p> <p>I tried a set of convex point sets formed by centroids of vertices of 8 dimensional 7-simplex, and there were 49 distinct singular value sets, which is the same as the number of such point sets not equivalent under coordinate permutation, obtained by Peter Shor in <a href="http://mathoverflow.net/questions/39429/how-many-non-equivalent-sections-of-a-regular-7-simplex/39892#39892" rel="nofollow">earlier post</a>, I'm wondering if it's a coincidence</p> http://mathoverflow.net/questions/47824/why-are-low-order-fourier-coefficients-more-important-for-real-life-probability Why are low order Fourier coefficients more important for real-life probability? Yaroslav Bulatov 2010-11-30T19:02:41Z 2010-11-30T21:22:37Z <p>Suppose have a probability distribution over space of $n$ binary variables. We can view logarithm of the density as a function $f$ from $\{-1,1\}^n$ to $\mathbb{R}$. Fourier expansion of the $f$ can be viewed as expansion of $f$ in terms of square free monomials.</p> <p>Given a sample from this density, we'd like to find Fourier coefficients that approximate true density. For real-life densities, fit is usually done by adjusting a small number of low order coefficients to fit the sample and fixing the rest to 0. Why does it work better than adjusting high-order coefficients?</p> <p>This was inspired by Gil Kalai's <a href="http://cstheory.stackexchange.com/questions/3332/fourier-coefficients-boolean-functions-described-by-bounded-depth-circuits-with-a" rel="nofollow">question</a> on CSTheory.</p> <p>Originally I thought it's because real life distributions have high entropy, but it seems that restricting entropy, or any symmetric function of the density is not enough to break symmetry between different coefficients. </p> <p>Here is a plot of all Fourier coefficients (0th order one dropped) realizable by empirical densities of 20 samples of 2-variable density. Z-axis, corresponds to $x_1 x_2$ term, $x,y$ axes are $x_1$ and $x_2$ terms. <img src="http://yaroslavvb.com/upload/save/log-linear-simplex.png"></p> http://mathoverflow.net/questions/46708/sum-over-labelings-representations-of-graph-polynomials "sum over labelings" representations of graph polynomials Yaroslav Bulatov 2010-11-20T03:33:00Z 2010-11-23T02:53:57Z <p>It seems that there's a general <a href="http://arxiv.org/abs/0812.1364" rel="nofollow">way</a> to go from "recursive" definition of a graph polynomials to "subset expansion" formulas.</p> <p>Furthermore, polynomials with subset expansion formulas often have a representation as a sum over all possible vertex labelings of some "local interactions" model.</p> <p>For instance, generating function for Eulerian subgraphs becomes Ising model partition function, generating function of independent sets becomes partition function of the hard-core model and Potts model has both "sum over labelings" and "sum over subgraphs" representation.</p> <ol> <li><p>Are there other interesting examples of graph polynomials with "sum over labelings" representation?</p></li> <li><p>When is it possible to get this representation of a graph polynomial? More specifically, to represent it as a sum over labelings of some quantity that is a product of functions each depending only on the variables corresponding to some edge of the graph. IE, if a graph has edges (1,2),(2,3) the term being summed over has to factor into f(x1,x2)*g(x2,x3)</p></li> </ol> <p>Motivation: there's a general algorithm to efficiently compute "sum over labelings" for functions decomposing over graph or hyper-graph of bounded tree-width, and it's interesting to see which graph polynomials I can use it for</p> http://mathoverflow.net/questions/46321/numeric-equality-testing Numeric equality testing? Yaroslav Bulatov 2010-11-17T03:37:09Z 2010-11-17T04:40:03Z <p>Suppose we have two closed-form expressions with $k$ unknowns which are hard to test for equality but easy to evaluate numerically over $\mathbb{R}^k$. One could then approach the problem of equality testing by checking equality numerically at several points. The interesting questions are then -- for which kinds of expressions can you do it, how to pick sampling points and how many points are needed.</p> <p>Google Scholar gives 0 hits for "numeric equality testing"</p> <p>Has this kind of problem been studied before? What are the right keywords to search for?</p> http://mathoverflow.net/questions/45526/finding-set-of-tree-decompositions-to-cover-all-pairs-of-vertices finding set of tree decompositions to cover all pairs of vertices Yaroslav Bulatov 2010-11-10T05:52:54Z 2010-11-10T05:52:54Z <p>I first <a href="http://cstheory.stackexchange.com/questions/2773/ensemble-of-tree-decompositions-for-all-pairs-problem" rel="nofollow">asked this</a> on cstheory.SE but got no reply.</p> <p>Let $P(X_i=x)$ represent probability that randomly chosen <a href="http://en.wikipedia.org/wiki/Graph_coloring" rel="nofollow">proper</a> $q$-coloring of an $L\times L$ <a href="http://en.wikipedia.org/wiki/Lattice_graph#Square_grid_graph" rel="nofollow">square grid</a> contains color $x$ at position $i$. How do you efficiently compute $P(X_{i}=X_{j})$ for every pair $(i,j)$?</p> <p>Fastest known <a href="http://arxiv.org/abs/1003.4847" rel="nofollow">method</a> for counting $q$-proper colorings on grids uses tree decomposition. To extend it to this problem, one needs a set of tree decompositions so that every pair of vertices is contained in some bag. Is anything known about this problem? </p> <p>Motivation: this is essentially two-point correlation function of Potts model, but also correlation function of self-avoiding walks and few other "all-pairs" problems face the same issue</p> http://mathoverflow.net/questions/44506/connective-constant-for-self-avoiding-walks-on-a-skip-chain Connective constant for self-avoiding walks on a skip-chain Yaroslav Bulatov 2010-11-02T02:04:21Z 2010-11-02T09:36:21Z <p>Suppose we have an undirected graph with integer valued nodes where $0&lt;|i-j|\le 2$ implies nodes $i$ and $j$ are connected. Let $c_n$ be the number of self-avoiding walks on this graph of length $n$ starting at origin. Define the connective constant as</p> <p>$$\mu = \lim_{n\to \infty} c_n^{\frac{1}{n}}$$</p> <p>What is known about $\mu$? This quantity seems to be related to the transition temperature of an Ising model on such graph, has such model been studied?</p> http://mathoverflow.net/questions/43363/derivative-of-tutte-polynomial-at-1 Derivative of Tutte polynomial at -1 Yaroslav Bulatov 2010-10-24T08:25:34Z 2010-10-26T20:07:49Z <p>Let Tutte polynomial on graph with edge-set $E$ be defined as follows</p> <p>$$f(q,v)=\sum_{A\subseteq E} q^{\kappa(A)} v^{|A|}$$</p> <p>Here the sum is over all subgraphs $A$, $\kappa(A)$ is the number of connected components in $A$, $|A|$ is number of edges in $A$.</p> <p>Let $$g(q,v)=\frac{\partial}{\partial v} \log f(q,v)$$ $$h(q,v)=\frac{\partial}{\partial v} f(q,v)$$</p> <p>Is anything known about $g(q,-1)$ or $h(q,-1)$?</p> <p>(<b>Edit 10/26:</b> actually it's the <a href="http://arxiv.org/abs/math/0503607" rel="nofollow">multivariate Tutte polynomial</a> restricted to all $v$'s being equal, relation to regular Tutte polynomial in Jeremy Martin's answer)</p> <p><b>Update 10/24</b></p> <p>$f(q,-1)$ is the number of proper $q$ colorings, $h(q,-1)$ is ???, $g(q,-1)$ is their ratio. Below are tables of values of $h(q,-1)$ for paths, cycles, complete graphs. Columns give graph size, $n=3..6$, rows give $q=2..8$</p> <p><img src="http://yaroslavvb.com/upload/tutte-derivative.png"></p> <p>Mathematica <a href="http://pastebin.com/raw.php?i=9rwkCjGy" rel="nofollow">code</a> to generate this</p> http://mathoverflow.net/questions/43335/hardness-of-identifying-the-number-of-local-maxima-for-mixture-of-gaussians/43395#43395 Answer by Yaroslav Bulatov for hardness of identifying the number of local maxima for mixture of Gaussians Yaroslav Bulatov 2010-10-24T16:29:04Z 2010-10-25T17:18:12Z <p>This year's FOCS <a href="http://arxiv.org/abs/1004.4223" rel="nofollow">paper</a> seems relevant.</p> <p>"Settling the Polynomial Learnability of Mixtures of Gaussians"</p> <p>Given data drawn from a mixture of multivariate Gaussians, a basic problem is to accurately estimate the mixture parameters. We give an algorithm for this problem that has a running time, and data requirement polynomial in the dimension and the inverse of the desired accuracy, with provably minimal assumptions on the Gaussians.</p> <p><b>Edit 10/25</b>: Suresh has a nice summary of the two papers that appeared on this problem here <a href="http://geomblog.blogspot.com/2010/10/focs-day-1-clustering.html" rel="nofollow">http://geomblog.blogspot.com/2010/10/focs-day-1-clustering.html</a></p> http://mathoverflow.net/questions/41520/for-ising-models-on-finite-graphs-is-the-gradient-of-z-w-r-t-coupling-and-field For Ising models on finite graphs, is the gradient of Z (w/r/t coupling and field) easier to compute than Z? Yaroslav Bulatov 2010-10-08T16:39:01Z 2010-10-08T20:09:47Z <p>Suppose we have a graph $G$ with $n$ vertices, edgeset $E$, $\mathcal{X}=\{1,-1\}^n$. The partition function of the spin-1/2 Ising model on $G$ is </p> <p>$$Z(J,h)=\sum_{x\in \mathcal{X}} \exp\left(J \sum_{(i,j)\in E} x_i x_j + h \sum_i x_i\right)$$</p> <p>and its gradient with respect to the coupling and applied field is </p> <p>$$\nabla Z(J,h)=\left ( \frac{\partial}{\partial J} Z, \frac{\partial}{\partial h} Z \right ).$$</p> <p>We are interested in computing these quantities to some pre-determined finite precision. Computing $Z$ is <a href="http://arxiv.org/abs/1005.5584" rel="nofollow">hard</a> in general, but <a href="http://arxiv.org/abs/0911.5486" rel="nofollow">easy</a> in special cases, like when $|J|$ is small relative to average degree of the graph.</p> <p>What can we say about relative hardness of computing $\nabla Z$?</p> http://mathoverflow.net/questions/41065/probability-of-observing-outcome-with-low-individual-probability Probability of observing outcome with low individual probability Yaroslav Bulatov 2010-10-04T20:58:52Z 2010-10-05T18:31:15Z <p>Suppose I throw k-sided dice n times and want to know the probability $p$ of observing a set of counts with individual probability higher than $x$.</p> <p>Example, let k=2,n=2, fair dice. Possible sets of counts are (0,2),(1,1),(2,0). Individual probabilities of those counts are 1/4,1/2 and 1/4 respectively. Probability of getting outcome with individual probability above 0 is 1, above 1/4 is 1/2, above 1/2 is 0.</p> <p>What is the relationship between $p$ and $x$? For k=3, line gives surprisingly good fit</p> <p><img src="http://yaroslavvb.com/upload/cumulative-fit.png"></p> <p>This is a generalization of a related unanswered <a href="http://mathoverflow.net/questions/37582/how-big-is-the-sum-of-smallest-multinomial-coefficients" rel="nofollow">question</a></p> <p>Douglas Zare suggests to think of counts as lattice sites of a random walk and use Central Limit theorem. This suggests that relationship is going to be quadratic for k=5, and indeed, parabola seems to give a decent upper bound in that case</p> <p><img src="http://yaroslavvb.com/upload/cumulative-fit5.png"></p> <pre> n = 21; types = Flatten[ Permutations /@ (IntegerPartitions[n, {3}, Range[0, n]]/n), 1]; prob[p_, q_] := n! Times @@ MapThread[(#1)^(n #2)/(n #2)! &, {p, q}]; cum[p_, cutoff_] := Total[Select[prob2[p, #] & /@ types, # >= cutoff &]]; p0 = RandomChoice[Select[types, FreeQ[#, 0] &]]; pvals = prob[p0, #] & /@ Union[types]; cvals = cum[p0, #] & /@ pvals; data = Transpose[{pvals, cvals}]; Show[ListPlot[data, PlotRange -> All], Plot @@ {Fit[data, {1, x}, x], {x, 0, Max[pvals]}, PlotStyle -> Red}] </pre> http://mathoverflow.net/questions/40383/inverse-formula-for-counting-marginals/40384#40384 Answer by Yaroslav Bulatov for Inverse formula for counting marginals Yaroslav Bulatov 2010-09-28T21:15:25Z 2010-09-28T21:15:25Z <p>The answer is yes, and this is known as Moebius inversion. See Section E.1, p.286 in <a href="http://www.eecs.berkeley.edu/~wainwrig/Papers/WaiJor08_FTML.pdf" rel="nofollow">Graphical models, exponential families, and variational inference.</a></p> http://mathoverflow.net/questions/34130/density-function-for-a-multivariate-bernoulli-like-distribution/40041#40041 Answer by Yaroslav Bulatov for Density function for a multivariate Bernoulli-like distribution Yaroslav Bulatov 2010-09-26T17:35:30Z 2010-09-26T17:35:30Z <p>You need to specify distribution over your random vector $\mathbf{X}$. If individual components are binary valued, and you only care about positive distributions, it can be written in the following form</p> <p>$$P(\mathbf{x})=\exp(\theta_0+\theta_1 x_1 + \theta_2 x_2 + \ldots + \theta_{12} x_1 x_2 + \ldots +\theta_{1\ldots k}x_1 \cdots x_k)$$</p> <p>Now the task is determining the distribution of $P(\mathbf{X}|X_1+\ldots+X_k=n)$, this distribution is related to hypergeometric distribution, described in Percy Diaconis "Algebraic algorithms for sampling from conditional distributions" (equations 1.1-1.4)</p> http://mathoverflow.net/questions/36493/surface-of-the-cut-of-an-ellipsoid-marginal-density-of-a-multivariate-normal-ov/39171#39171 Answer by Yaroslav Bulatov for Surface of the cut of an ellipsoid / Marginal density of a multivariate normal over an affine space Yaroslav Bulatov 2010-09-18T00:06:20Z 2010-09-18T00:06:20Z <p>I had to do something similar recently and there's a neat trick for integrating Gaussian over linear subspace of $\mathbb{R}^n$ -- write it as an integral over whole $\mathbb{R}^n$ but substitute Dirac measure for regular. <a href="http://yaroslavvb.blogspot.com/2010/09/dirac-integration-trick.html" rel="nofollow">Here</a>'s overview, and <a href="http://math.stackexchange.com/questions/4106/normalization-factor-for-restricted-density" rel="nofollow">discussion</a> on math.overflow</p> http://mathoverflow.net/questions/39002/optimizing-over-matrices-with-spectral-radius-1 Optimizing over matrices with spectral radius <1? Yaroslav Bulatov 2010-09-16T17:58:02Z 2010-09-17T18:06:06Z <p>Suppose $F(x)$ is a convex objective function on $n\times n$ matrices, and I need to numerically optimize $F$ with the condition that $x$ has spectral radius less than $1$. This might be too hard, so an approximation would be needed. Has this problem been studied before?</p> <p>Motivation: Boltzmann machines are hard to evaluate when spectral radius of the weight matrix is large, especially if it's above $1$ so best fit to data subject to this constraint would give a useful model.</p> <p>Example: Let $X=\{1,-1\}^d$ and $\hat{X}$ some list of $\{1,-1\}$ $d$-tuples. Find $$\max_A \sum_{x\in \hat{X}} \mathbf{x}'A\mathbf{x} - |\hat{X}|\log \sum_{x\in X} \exp(\mathbf{x}'A\mathbf{x})$$ Where $A$ is symmetric real-valued $d\times d$ matrix with spectral radius &lt; 1. This needs to be done in time polynomial in $d$ and linear in $|\hat{X}|$. When spectral radius is &lt;1, belief propagation gives a reasonably accurate way to approximate gradient of this objective in $O(|\hat{X}|d^2)$ time</p> http://mathoverflow.net/questions/39029/why-doesnt-stein-effect-happen-for-multinomial-distributions Why doesn't Stein effect happen for multinomial distributions? Yaroslav Bulatov 2010-09-16T22:20:03Z 2010-09-17T06:24:19Z <p><a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.6043" rel="nofollow">(Medeen, et all, 1998)"</a> show that Maximum Likelihood estimate is admissible for multinomial distribution under squared error. On other hand, James and Stein showed that arithmetic average is not an admissible estimator of Gaussian location parameter in 3 dimensions. But since maximum likelihood estimates of multinomial parameters are averages of observed counts, which become normally distributed for large sample sizes, why doesn't Stein effect happen here? </p> <p>$\hat{p}$ is an inadmissible estimator of $\theta$ if there's an estimator that is no worse for every $\theta$ and better for at least one</p> http://mathoverflow.net/questions/38724/coordinates-of-vertices-of-regular-simplex coordinates of vertices of regular simplex Yaroslav Bulatov 2010-09-14T18:38:30Z 2010-09-14T21:34:35Z <p>For $d=3$, vertex coordinates of a <a href="http://en.wikipedia.org/wiki/Simplex" rel="nofollow">regular simplex</a> have a simple expression since vertices correspond to four vertices of a cube. Is there a simple expression for higher dimensions? In particular I'm interested in $d=2^n-1$, integer $n$.</p> <p><b>Edit</b>: by coordinates I mean points in $\mathbb{R}^d$. Every $d$-simplex has a simple expression for coordinates in $\mathbb{R}^{d+1}$, as Mariano shows below</p> http://mathoverflow.net/questions/38360/distribution-of-transformed-multinomial-variable Distribution of transformed multinomial variable? Yaroslav Bulatov 2010-09-10T22:56:15Z 2010-09-13T17:59:19Z <p>Suppose we have a uniform multinomial distribution over $2^d$ outcomes. Multinomial coefficients give distribution of vector valued variable $v$ where $v$ is the vector of observed counts.</p> <p>Is there a combinatorial expression for the distribution of $D v$ where $D$ is a matrix obtained by $d$-fold <a href="http://en.wikipedia.org/wiki/Kronecker_product" rel="nofollow">Kronecker product</a> of $A$, a $(-1,0,1)$ valued 2-by-2 matrix?</p> <p>Three particular choices of $A$ I'm looking at are</p> <p>$$A_1=\left(\begin{matrix}1&amp;1\\1&amp;-1\end{matrix}\right)$$ $$A_2=\left(\begin{matrix}1&amp;1\\0&amp;1\end{matrix}\right)$$ $$A_3=\left(\begin{matrix}1&amp;0\\-1&amp;1\end{matrix}\right)$$</p> <p>Motivation: distribution of $Dv$ corresponds to distribution of feature vectors for three commonly feature bases for exponential families (Walsh, Amari's $\eta$ and Amari's $\theta$ bases respectively)</p> <pre> d = 3; walsh = KroneckerProduct @@ Table[{{1, 1}, {1, -1}}, {d}]; amariEta = KroneckerProduct @@ Table[{{1, 1}, {0, 1}}, {d}]; amariTheta = KroneckerProduct @@ Table[{{1, 0}, {-1, 1}}, {d}]; </pre> <p><b>Edit</b>: all 3 matrices are invertible, so we just need to multiply by appropriate inverse to get back vector of counts and corresponding multinomial coefficient. Inverse of $D$ is just the Kronecker product of inverses of corresponding base matrices</p> <p>$$A_1^{-1}=\left(\begin{matrix}1/2&amp;1/2\\1/2&amp;-1/2\end{matrix}\right)$$ $$A_2^{-1}=\left(\begin{matrix}1&amp;-1\\0&amp;1\end{matrix}\right)$$ $$A_3^{-1}=\left(\begin{matrix}1&amp;0\\1&amp;1\end{matrix}\right)$$</p> http://mathoverflow.net/questions/38191/convergence-of-a-markov-matrix/38216#38216 Answer by Yaroslav Bulatov for Convergence of a markov matrix Yaroslav Bulatov 2010-09-09T18:48:08Z 2010-09-09T18:48:08Z <p>For irreducible Markov chain, necessary condition for convergence is primitivity (ie, all entries of $P^k$ are positive for some k). In a reducible Markov chain, your Markov walker eventually settles into one of $k$ ergodic classes where states inside each class can all reach each other. Hence, reducible Markov chain can be thought of a collection of irreducible Markov chains on a partitioning of the state space, and the limit exists if and only if Markov chain on each of those classes is primitive.</p> <p>Even if $\lim_{n \to \infty} P^k$ doesn't exist, Cesaro sum always does, ie $$\lim_{n\to \infty} \frac{I+P^1+P^2+\ldots P^n}{n}$$ </p> <p>Columns of this matrix (assuming column stochastic transition matrix) give fraction of time that Markov chain spends in each state eventually</p> <p>Ch.8 of "Matrix Analysis &amp; Applied Linear Algebra" by Carl Meyer gives more details on these conditions</p> http://mathoverflow.net/questions/37582/how-big-is-the-sum-of-smallest-multinomial-coefficients How big is the sum of smallest multinomial coefficients? Yaroslav Bulatov 2010-09-03T06:12:33Z 2010-09-06T07:20:46Z <p>Given positive integers $n$ and $d$, let $S$ indicate the list of all $d$-tuples of non-negative integers $(c_1,\ldots,c_d)$ such that $c_1+\cdots+c_d=n$. Let $v_i$ be the value of the multinomial coefficient corresponding to $i$'th tuple in $S$, ie</p> <p>$$v_i=\frac{n!}{c_1!\cdots c_d!}$$</p> <p>What can we say about the sum of smallest coefficients, ie, the value of the following?</p> <p>$$s(B)=\sum_{v_i &lt; B} v_i$$</p> <p>Motivation: upper bounds on multinomial tails would allow to give non-asymptotic error bounds for various learning algorithms</p> <p><b>Update: 09/03</b> Here are all the relevant theoretical results I found so far. Let $B=\frac{n!}{c_1!\cdots c_d}$, $C=\max_i v_i$, $k=\min_i c_i$. Then for even n and $d=2$ the following are known to hold </p> <p>$$s(B)&lt;\frac{B}{C} 2^n$$ Proof under <a href="http://yaroslavvb.com/upload/lovasz-binomial1.pdf" rel="nofollow">Lemma 3.8.2</a> of Lovasz et al "Discrete Mathematics" (2003)</p> <p>$$s(B)\le 2^n \exp(-\frac{(n/d-k)^2}{n-k})$$ Proof under <a href="http://yaroslavvb.com/upload/lovasz-binomial2.pdf" rel="nofollow">Theorem 5.3.2</a> of Lovasz et al "Discrete Mathematics" (2003)</p> <p>$$s(B)\le 2B(\frac{n-(k-1)}{n-(2k-1)}-1)$$ Michael Lugo gives <a href="http://mathoverflow.net/questions/17202/sum-of-the-first-k-binomial-coefficients-for-fixed-n" rel="nofollow">outline</a> of proof in another MO post </p> <p>$$s(B)&lt;2(\exp(n \log n - \sum_i c_i \log c_i)-B)$$ Proof under <a href="http://yaroslavvb.com/upload/flum-binomial.pdf" rel="nofollow">Lemma 16.19</a> of Flum et al "Parameterized Complexity Theory" (2006)</p> <p>To be practically useful for my application, these bounds need to be tight for tails, ie, for sums that are less than $d^n/10$. Here's a plot of logarithm of bound/exact ratio for such sums. X-axis is monotonically related to B.</p> <p><img src="http://yaroslavvb.com/upload/multinomial-bounds.png"></p> <p>You can see that Michael Lugo's bound is by far the most accurate in that range.</p> <p>Out of curiosity, I "plugged in" bounds above for sums of higher dimensional coefficients. <img src="http://yaroslavvb.com/upload/bounds-higherd2.png"> <img src="http://yaroslavvb.com/upload/bounds-higherd3.png"></p> <p>Mathematica <a href="http://yaroslavvb.com/research/qr/mo-multinomials/mo-multinomials2.nb" rel="nofollow">notebook</a>.</p> http://mathoverflow.net/questions/37424/why-are-multinomial-coefficients-with-same-entropy-equal-usually Why are multinomial coefficients with same entropy equal? (usually) Yaroslav Bulatov 2010-09-01T20:56:02Z 2010-09-02T20:27:53Z <p>Suppose $p_1,\ldots,p_d$ and $q_1,\ldots,q_d$ are positive real numbers such that </p> <p>$$p_1+\cdots+p_d=q_1+\cdots+q_d=n$$</p> <p>and</p> <p>$$p_1 \log p_1+\cdots+p_d\log p_d=q_1 \log q_1+\cdots+q_d \log q_d$$</p> <p>Then the following seems to hold</p> <p>$$\frac{n!}{p_1!\cdots p_d!}=\frac{n!}{q_1!\cdots q_d!}$$</p> <p>why?</p> <p><b>Edit</b>: JBL correctly notices that it doesn't always hold. I just didn't go far enough. Still, it's surprising to me that it holds so frequently.</p> <p>If we put a black disk at x,y if equality seems to hold (in machine precision) for x=n,y=d, and positive integer coefficients, it'll look like this <img src="http://yaroslavvb.com/upload/multinomial-equality.png"></p> <p>Red circle is JBL's example. Blue circle is n=18,d=3 which fails for (12,3,3) and (9,8,1).</p> <pre> docheck[n_, d_] := ( coefs = IntegerPartitions[n, {d}, Range[1, n]]; entropy[x_] := N[Total[# Log[#] & /@ x]]; groupedCoefs = GatherBy[coefs, entropy]; allEqual[list_] := And @@ (First[list] == # & /@ list); multinomials = Apply[Multinomial, groupedCoefs, {2}]; And @@ (allEqual /@ multinomials) ); vals = Table[docheck[#, d] & /@ Range[1, 30], {d, 1, 20}]; Graphics[Table[Disk[{n, d}, If[vals[[d, n]], .45, .1]], {d, 1, Length[vals]}, {n, 1, 30}]] </pre> <p><b>Edit:</b> Updated version that does exact checking and allows coefficients with 0 components. Still only one example of failure for d=3.</p> <p><img src="http://yaroslavvb.com/upload/multinomial-equality2.png"></p> <pre> docheck[n_, d_] := (coefs = IntegerPartitions[n, {d}, Range[0, n]]; entropy[x_] := Exp[Total[If[# == 0, 0, # Log[#]] & /@ x]]; groupedCoefs = GatherBy[coefs, entropy]; allEqual[list_] := And @@ (First[list] == # & /@ list); multinomials = Apply[Multinomial, groupedCoefs, {2}]; And @@ (allEqual /@ multinomials)); maxn = 30; maxd = 20; vals = Table[docheck[#, d] & /@ Range[1, maxn], {d, 1, maxd}]; Graphics[Table[Disk[{n, d}, If[vals[[d, n]], .45, .1]], {d, 1, Length[vals]}, {n, 1, maxn}]] </pre> http://mathoverflow.net/questions/37518/why-do-statistical-randomness-tests-seem-so-ad-hoc/37523#37523 Answer by Yaroslav Bulatov for Why do statistical randomness tests seem so ad hoc? Yaroslav Bulatov 2010-09-02T18:39:09Z 2010-09-02T18:39:09Z <p>Kolmogorov complexity is a universal quantity for infinite strings. But since randomness tests are run on finite strings, particular choice of architecture or encoding will play a large role in how the strings will be ordered. A goal of good randomness test designer is to choose an encoding such that strings coming from known random sources (like random.org) are deemed more complex than strings coming from known non-random sources (like pseudo-random generators). Good tests incorporate knowledge of how typical non-random strings are generated, hence the apparent ad hockery.</p> http://mathoverflow.net/questions/17202/sum-of-the-first-k-binomial-coefficients-for-fixed-n/37319#37319 Answer by Yaroslav Bulatov for Sum of 'the first k' binomial coefficients for fixed n Yaroslav Bulatov 2010-08-31T21:37:56Z 2010-09-01T05:06:33Z <p>Jean Gallier gives this bound (Proposition 4.16 in Ch.4 of "Discrete Math" <a href="http://www.cis.upenn.edu/~jean/gbooks/discmath.html" rel="nofollow">preprint</a>)</p> <p>$$f(n,k) &lt; 2^{n-1} \frac{{n \choose k+1}}{n \choose n/2}$$</p> <p>where $f(N,k)=\sum_{i=0}^k {N\choose i}$, and $k\le n/2-1$ for even $n$</p> <p>It seems to be worse than Michael's bound except for large values of k</p> <p>Here's a plot of f(50,k) (blue circles), Michael Lugo's bound (brown diamonds) and Gallier's (magenta squares)</p> <p><img src="http://yaroslavvb.com/upload/binomial-bounds.png"></p> <pre> n = 50; bisum[k_] := Total[Table[Binomial[n, x], {x, 0, k}]]; bibound[k_] := Binomial[n, k + 1]/Binomial[n, n/2] 2^(n - 1); lugobound[k_] := Binomial[n, k] (n - (k - 1))/(n - (2 k - 1)); ListPlot[Transpose[{bisum[#], bibound[#], lugobound[#]} & /@ Range[0, n/2 - 1]], PlotRange -> All, PlotMarkers -> Automatic] </pre> <p><b>Edit</b> The <a href="http://yaroslavvb.com/upload/lovasz-proof2.pdf" rel="nofollow">proof</a>, Proposition 3.8.2 from Lovasz "Discrete Math". </p> <p>Lovasz gives another <a href="http://yaroslavvb.com/upload/lovasz-proof.pdf" rel="nofollow">bound</a> (Theorem 5.3.2) in terms of exponential which seems fairly close to previous one </p> <p>$$f(n,k)\le 2^{n-1} \exp (\frac{(n-2k-2)^2}{4(1+k-n)}$$ Lovasz bound is the top one.</p> <p><img src="http://yaroslavvb.com/upload/binomial-bounds2.png"></p> <pre> n = 50; gallier[k_] := Binomial[n, k + 1]/Binomial[n, n/2] 2^(n - 1); lovasz[k_] := 2^(n - 1) Exp[(n - 2 k - 2)^2/(4 (1 + k - n))]; ListPlot[Transpose[{gallier[#], lovasz[#]} & /@ Range[0, n/2 - 1]], PlotRange -> All, PlotMarkers -> Automatic] </pre> http://mathoverflow.net/questions/35798/bounding-sum-of-multinomial-coefficients-by-highest-entropy-one Bounding sum of multinomial coefficients by highest entropy one Yaroslav Bulatov 2010-08-16T21:39:47Z 2010-08-24T23:11:58Z <p>When does the following hold?</p> <p>$\sum_{(i_1,\ldots,i_k)\in E} \frac{n!}{i_1! \ldots i_k!} \le \exp(n H^*)$</p> <p>Where</p> <p>$H^*=\max_{(i_1,\ldots,i_k)\in E} -(\frac{i_1}{n}\log \frac{i_1}{n}+\ldots +\frac{i_k}{n}\log \frac{i_k}{n})$ and E is some subset of {${( i_1,\ldots,i_k):i_1+\ldots+i_k=n }$}</p> <p>Motivation: this is a generalization of Chernoff's bound to n tosses of fair k-sided dice where E represents the hypothesis we make about that sample. Another motivation is reconciling tight special-case <a href="http://en.wikipedia.org/wiki/Chernoff_bound#Theorem_for_additive_form_.28absolute_error.29" rel="nofollow">Chernoff bound</a> with looser but more general bound given by <a href="http://yaroslavvb.com/upload/sanovs.png" rel="nofollow">Sanov's theorem</a></p> <p>Examples: when k=2, it can be proven to hold for sets of coefficients where first component of the coefficient is less than n/2 (ie <a href="http://yaroslavvb.com/upload/binomial.png" rel="nofollow">here</a>).</p> <p>When k=3, it seems (empirically) to hold for sets of coefficients where sum of first two components is &le;n/2. For instance, for n=10, highest entropy term gives upper bound of (2/3)^3 *10^5 whereas exact sum is 12585. Since k=3 multinomial coefficients lie in a 2-simplex, the 21 multinomial coefficients in this set can be visualized below. Top vertex represents coefficient (0,0,10)</p> <p><img src="http://yaroslavvb.com/upload/multinomials.png"></p> <p>For higher k, we can look at similar sets, ie corners of the (k-1) simplex. I tried few values and it seems to hold for coefficients where sum of first k-1 components is below n/(k-1)</p> <p>Here's how you'd check it in Mathematica</p> <pre> getit[n_, k_, c_] := ( all = Select[Tuples[Range[0, n], k], Total[#] == n &]; e = Select[all, Total[Most[#]] &lt;= c &]; hterm[x_] := If[0 &lt; x &lt; 1, x Log[x], 0]; H[event_] := -Total[hterm /@ (event/n)]; exact = Total[Multinomial @@@ e]; upper = Exp[n Max[H /@ e]]; exact &lt; upper ); (* Check bound for k=3, n=10, with i1+i2&lt;=5 *) getit[10, 3, 5] </pre> <p><b>Update 8/18</b> Leandro gives a bound on a single multinomial coefficient which gives <a href="http://yaroslavvb.com/upload/sanovs.png" rel="nofollow">Sanov's theorem</a> if we consider that there's at most $(n+1)^k$ multinomial coefficients in any set E. It seems that to generalize the <a href="http://yaroslavvb.com/upload/binomial.png" rel="nofollow">proof</a> of the tighter binomial bound to, say, trinomial coefficients, one would need to prove the following inequality first</p> <p>$$p_1 \log q_1 + p_2 \log q_2 + p_3 \log q_3 \ge q_1 \log q_1 + q_2 \log q_2 + q_3 \log q_3$$</p> <p>Where p and q add up to 1. For each q, the set of p's for which the above bound holds also gives us the hypothesis for which we can give tight Chernoff-like bound. Empirically, this bound seems to hold for p's "bounded away" from the uniform distribution. Black circle below represents q, blue region is the set of distributions p where the bound above holds. My Mathematica <a href="http://yaroslavvb.com/research/qr/mo-multinomials/mo-multinomials.nb" rel="nofollow">notebook</a></p> <p><img src="http://yaroslavvb.com/upload/cross-entropy-bound.png"></p> <p><b> Update 8/24</b>: the bound holds for sets of coefficients of the form $i_1 a_1 + \ldots + i_n a_n \le C$ where $a_1\ldots a_n$ are arbitrary non-negative numbers, details in answer</p> http://mathoverflow.net/questions/52141/invariants-that-might-determine-graph-up-to-isomorphism Comment by Yaroslav Bulatov Yaroslav Bulatov 2011-05-02T18:19:49Z 2011-05-02T18:19:49Z yes, just finite graphs http://mathoverflow.net/questions/35617/sanovs-theorem-and-chernoff-bound/63082#63082 Comment by Yaroslav Bulatov Yaroslav Bulatov 2011-04-27T05:31:05Z 2011-04-27T05:31:05Z Thanks for reference! I wonder why Shanon/Cover give the looser bound if polynomial term can be dropped http://mathoverflow.net/questions/57998/correlation-between-3-variables Comment by Yaroslav Bulatov Yaroslav Bulatov 2011-03-09T21:39:42Z 2011-03-09T21:39:42Z you could use multi-information, see Bell's &quot;co-information lattice&quot; www.rni.org/bell/nara4.pdf http://mathoverflow.net/questions/55002/maximal-clique-intersection-graphs/57396#57396 Comment by Yaroslav Bulatov Yaroslav Bulatov 2011-03-04T22:25:54Z 2011-03-04T22:25:54Z I'm interested in clique graphs created by partial triangulations -- I add some chords and look at clique intersection graph where only maximal intersections form edges. The goal is to create such clique graphs where maximal intersections are almost graph separators (any cycle that goes through such set is long). I'm looking for heuristics that lets me find such triangulations while keeping maximum clique size as small as possible http://mathoverflow.net/questions/55784/what-can-be-said-about-the-choice-of-a-prior-in-bayesian-statistics Comment by Yaroslav Bulatov Yaroslav Bulatov 2011-02-17T23:02:07Z 2011-02-17T23:02:07Z You could search for literature from &quot;objective Bayesian&quot; community, who focus on principled methods on choosing priors, esp survey papers from people like Wasserman, Berger, Bernardo, Dawid http://mathoverflow.net/questions/55002/maximal-clique-intersection-graphs/55009#55009 Comment by Yaroslav Bulatov Yaroslav Bulatov 2011-02-10T18:38:40Z 2011-02-10T18:38:40Z By click incidence do you mean connecting nodes whenever some clique contains them both? http://mathoverflow.net/questions/55002/maximal-clique-intersection-graphs Comment by Yaroslav Bulatov Yaroslav Bulatov 2011-02-10T16:14:15Z 2011-02-10T16:14:15Z The former, I believe latter would be called &quot;maximum clique&quot; http://mathoverflow.net/questions/54239/why-is-p-vs-np-necessarily-relevant Comment by Yaroslav Bulatov Yaroslav Bulatov 2011-02-04T03:16:01Z 2011-02-04T03:16:01Z There's also the converse, P!=NP but there's algorithm that solves any real-life NP-hard instance in a blink. For instance, SAT is NP-hard, but all SAT instances that &quot;come up in practice&quot; are easy -- <a href="http://rjlipton.wordpress.com/2009/07/13/sat-solvers-is-sat-hard-or-easy/" rel="nofollow">rjlipton.wordpress.com/2009/07/13/&hellip;</a> http://mathoverflow.net/questions/12310/counting-subgraphs-of-bipartite-graphs Comment by Yaroslav Bulatov Yaroslav Bulatov 2011-01-16T08:34:30Z 2011-01-16T08:34:30Z You can count the number of subgraphs with $m$ edges and $n$ vertices in polynomial time on bounded tree width graphs. http://mathoverflow.net/questions/52141/invariants-that-might-determine-graph-up-to-isomorphism Comment by Yaroslav Bulatov Yaroslav Bulatov 2011-01-15T03:47:04Z 2011-01-15T03:47:04Z Useful link, thanks. It's different from this question because it asks for for functions which are known to distinguish graphs up to isomorphism, whereas I'm asking for ones which are not known to <i>NOT</i> distinguish graphs up to isomorphism, ie, the ones which could use a counter-example http://mathoverflow.net/questions/51682/reasons-for-the-importance-of-planarity-and-colorability Comment by Yaroslav Bulatov Yaroslav Bulatov 2011-01-10T20:58:02Z 2011-01-10T20:58:02Z Maybe they are computationally special? Tree decomposition works because we can solve problem on trees, holographic reduction works because we can count perfect matchings on planar graphs http://mathoverflow.net/questions/51595/breaking-frustrated-loops-in-list-coloring-problem/51669#51669 Comment by Yaroslav Bulatov Yaroslav Bulatov 2011-01-10T19:09:20Z 2011-01-10T19:09:20Z I realize that breaking all frustrated cycles is probably too hard, so I need to find k nodes that break as many cycles as possible http://mathoverflow.net/questions/51595/breaking-frustrated-loops-in-list-coloring-problem Comment by Yaroslav Bulatov Yaroslav Bulatov 2011-01-10T19:07:33Z 2011-01-10T19:07:33Z I unfortunately don't know any related literature, this is a theoretical example for a practical problem that arises when running a particular message passing algorithm on graph. Frustrated cycles cause convergence problems and I can delete a few nodes and correct for their removal. There's a bounded number of nodes I can afford to remove, so I want to break as many frustrated cycles as possible with that number. http://mathoverflow.net/questions/50763/what-is-the-dimensionality-of-a-tree Comment by Yaroslav Bulatov Yaroslav Bulatov 2010-12-30T23:53:41Z 2010-12-30T23:53:41Z You get a tree if you connect the origin to every datapoint. Question doesn't really make sense to me http://mathoverflow.net/questions/39429/how-many-non-equivalent-sections-of-a-regular-7-simplex/39892#39892 Comment by Yaroslav Bulatov Yaroslav Bulatov 2010-12-22T04:53:44Z 2010-12-22T04:53:44Z BTW, I also got 49 sections with an automatic search. A nice surprise is that section corresponding to no empty vertices is a regular octahedron.