most recent 30 from http://mathoverflow.net 2013-05-22T01:25:55Z http://mathoverflow.net/feeds/user/11541 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/101477/combinatorial-descriptions-of-the-stationary-distribution-of-a-markov-chain Erik Aas 2012-07-06T10:24:52Z 2012-07-06T15:53:20Z

<p>When I say "Markov chain" I think of a directed positively weighted (finite) graph, such that the sum of all edges going out of a vertex equals 1. Also I assume that it is aperiodic and irreducible. </p> <p>If the Markov chain happens to be equivalent to an "undirected Markov chain", i.e. for each directed arc (u,v) with weight w there is an arc (v,u) with same weight w, then it is easy to characterize the stationary distribution directly in terms of the graph; the stationary distribution at a vertex v is proportional to the out-degree (which in this case is half the total degree) of v.</p> <p>However I know of no such direct description of the stationary distribution in terms of the graph of a Markov chain that does not come from an undirected graph (except possibly for time-reversible chains, but this is a very special special case). My question is: are there any such descriptions?</p> <p>This is of course a bit vague(since the stationary distribution clearly depends only on the graph) but I hope it is not too vague.</p> <p>I would not expect an as easy description as in the undirected case (where it suffices to look in a neighbourhood of radius 1 to find the probability of any vertex), but it seems reasonable that there could be a description involving, say, all trees rooted at the vertex.</p> <p>This seems not to be treated in standard texts on Markov chains (correct me if wrong), where usually most effort is spent on proving existence, estimating speed of convergence, and the underlying graph is considered as 'auxilliary'.</p>

http://mathoverflow.net/questions/88750/functions-satisfying-one-one-iff-onto/88768#88768 Erik Aas 2012-02-17T21:07:15Z 2012-02-18T09:03:11Z

<p>If $f : S \to S$ is volume preserving and $S \subseteq \mathbb{R}^n$ has finite volume, then f is injective iff f is surjective.</p> <p>There is a very elegant proof of Koebe–Andreev–Thurston theorem (given in the book on combinatorial geometry by Agarwal and Pach) using this property.</p>

http://mathoverflow.net/questions/87827/sampling-uniformly-from-a-sphere Erik Aas 2012-02-07T18:57:55Z 2012-02-08T17:31:43Z

<p>Let $B^{n} _p= ${$ (x_1, \dots, x_n) : |x_1|^p + \dots |x_n|^p = 1 $} be the unit ball in $\mathbb{R}^n$ in the $\ell^p$ norm.</p> <p>If $X_1,\dots,X_n$ are iid $\exp(1)$ -distributed random variables, then $(X_1/D,\dots,X_n/D)$, where $D =X_1+ \dots + X_n $ is uniformly distributed in $B^{n}_1$.</p> <p>If $X_1,\dots,X_n$ are iid normally distributed with mean 0, then $(X_1/D,\dots,X_n/D)$, where $D = (X_1^2+\dots+X_n^2)^{1/2}$, is uniformly distributed in $B^{n}_2$.</p> <p>Is there a choice of $X_1,\dots , X_n$ iid such that $ ( X_1 / D, \dots, X_n/D)$, where $D = (|X_1|^p + \dots + |X_n|^p)^{1/p} $ is uniformly distributed in $B^{n} _p$ for arbitrary $p$?</p> <p>I would be happy with any sensible common generalization of the two statements above. I have no particular reason to believe there is such a generalization - I'm just hoping that two so similar and neat examples have similarly nice generalizations.</p>

http://mathoverflow.net/questions/76595/is-this-statement-about-the-real-edge-space-of-a-graph-known-or-trivial Erik Aas 2011-09-28T03:07:05Z 2011-09-30T23:59:44Z

<p>The statement is: ($u$ is a fixed node in a fixed graph $G$)</p> <p>$G$ is 3-connected if and only if the set of u-cycles span $\mathbb{R}^{E(G)}$.</p> <p>A u-cycle is a simple (no vertex repetitions) cycle in G that contains the given node u.</p> <p>A cycle is identified with its characteristic vector in $\mathbb{R}^{E(G)}$ that is $1$ on the edges in the cycle and $0$ otherwise.</p> <p>I first thought this would be a standard result on the cycle space of a graph. However, the references I've found have only considered cycle spaces over a field with non-zero characteristic.</p> <p>EDIT: The 'usual' edge space $\mathbb{Z}_2^{E(G)}$ is quite different from the 'real' edge space $\mathbb{R}^{E(G)}$. For example the set of (characteristic vectors of) cycles form a m-n+1-dimensional space independently of all other properties of the graph, while the statement above claims the cycle space can indeed be the entire edge space even in non-trivial cases.</p> <p>Here's an example. Let K_4 have four nodes 1,2,3,4 and edges indexed so:</p> <p>1 - {1,2}</p> <p>2 - {1,3}</p> <p>3 - {1,4}</p> <p>4 - {2,3}</p> <p>5 - {2,4}</p> <p>6 - {3,4}</p> <p>The characteristic vectors of the u-cycles (u = '1') 1463, 1562, 3542, 153, 142, 263 (sequences of indices of <em>edges</em>) are, row by row:</p> <p>1 0 1 1 0 1</p> <p>1 1 0 0 1 1</p> <p>0 1 1 1 1 0</p> <p>1 0 1 0 1 0</p> <p>1 1 0 1 0 0</p> <p>0 1 1 0 0 1</p> <p>bluebit.gr (and hopefully any other calculator) tells me this matrix has rank 6, so the cycles given span the entire 6-dimensional real edge space and they are also all u-cycles.</p>

http://mathoverflow.net/questions/42241/errata-for-atiyah-macdonald/54465#54465 Erik Aas 2011-02-05T21:17:16Z 2011-02-05T21:17:16Z

<p>page 81, line 5: change $f_i \in A[x]$ to $f_i \in \mathfrak{a}$</p>

http://mathoverflow.net/questions/101787/optimal-bounds-for-an-alternating-sum-on-a-downset Erik Aas 2012-07-09T17:31:18Z 2012-07-09T17:31:18Z

Possibly related: <a href="http://mathoverflow.net/questions/91712/is-euler-characteristic-of-a-simplicial-complex-upper-bounded-by-a-polynomial-in" rel="nofollow" title="is euler characteristic of a simplicial complex upper bounded by a polynomial in">mathoverflow.net/questions/91712/&hellip;</a> (since your sum is the euler characteristic of the down-set).

http://mathoverflow.net/questions/101477/combinatorial-descriptions-of-the-stationary-distribution-of-a-markov-chain Erik Aas 2012-07-06T11:02:47Z 2012-07-06T11:02:47Z

(well I don't even need to scale p(v) to be integers for Ap = p to hold - but the space of solutions is 1-dimensional and contains the stationary distribution.)

http://mathoverflow.net/questions/101477/combinatorial-descriptions-of-the-stationary-distribution-of-a-markov-chain Erik Aas 2012-07-06T11:01:41Z 2012-07-06T11:01:41Z

Felix: yes. It is easy to check that letting p(v) = degree(v) / (sum of all degrees of vertices) satisfies the equation A*p = p where A is the transition matrix in this case. This occurs in many places in the literature, for example in Lovasz' notes on random walks in graphs.

http://mathoverflow.net/questions/89478/magnitude-of-the-sum-of-complex-i-u-d-random-variables-in-the-unit-circle Erik Aas 2012-02-25T13:12:08Z 2012-02-25T13:12:08Z

The central limit theorem (en.wikipedia.org/wiki/central_limit_theorem ) applied to the real and imaginary parts of \sum _k Z_k shows these are normally distributed and independent. From this it should be easy to show $M_n = O(\sqrt n )$ with high probability.

http://mathoverflow.net/questions/88750/functions-satisfying-one-one-iff-onto/88768#88768 Erik Aas 2012-02-18T09:06:48Z 2012-02-18T09:06:48Z

@Tom : oops, I've fixed it now. (The intention was to answer the question &quot;under what circumstances is f injective iff f is surjective&quot;, but I just realized the question was not given like that.)

http://mathoverflow.net/questions/76595/is-this-statement-about-the-real-edge-space-of-a-graph-known-or-trivial/76741#76741 Erik Aas 2011-10-01T03:21:56Z 2011-10-01T03:21:56Z

Nice! I don't know if this means the answer to the original question is &quot;yes&quot;, but I'll accept it as an answer anyway.

http://mathoverflow.net/questions/76595/is-this-statement-about-the-real-edge-space-of-a-graph-known-or-trivial/76699#76699 Erik Aas 2011-09-29T06:44:18Z 2011-09-29T06:44:18Z

Good point - that definition of 'real (cycle/edge) space' would probably make more sense in general. In my question I'm thinking of the edges as undirected so the characteristic vectors mentioned there are really those of sets of undirected edges (which happen to form cycles). So the vectors of a cycle and its reverse would be the same, for example. The undirected model is also natural if one is thinking about quantities that add up along edges independently of direction (like lengths).

http://mathoverflow.net/questions/76595/is-this-statement-about-the-real-edge-space-of-a-graph-known-or-trivial Erik Aas 2011-09-29T04:08:55Z 2011-09-29T04:08:55Z

The u-cycles do span the cycle space (for either interpretation of the term (see below)) but they do not span R^E, as the statement claims they should not.

http://mathoverflow.net/questions/76595/is-this-statement-about-the-real-edge-space-of-a-graph-known-or-trivial/76699#76699 Erik Aas 2011-09-29T04:05:19Z 2011-09-29T04:05:19Z

So, I was indeed thinking of spanning the 'real cycle space' but more importantly show that it coincides with the edge space, and that it is spanned by the subset of cycles given by the u-cycles.

http://mathoverflow.net/questions/76595/is-this-statement-about-the-real-edge-space-of-a-graph-known-or-trivial/76699#76699 Erik Aas 2011-09-29T04:04:35Z 2011-09-29T04:04:35Z

I don't agree with your claim that the space spanned by the cycles has dimension E-V+1. This is true for the cycle space over Z_2, but not for the 'real cycle space' (if defined as the subspace of R^E spanned by characteristic vectors of cycles - Wikipedia defines the cycle space only for Z and Z_2), I believe - I will edit my question to contain an example. The statement you prove above is not what I was thinking of but is nonetheless very nice! (continued)