User daniel mansfield - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T12:58:41Z http://mathoverflow.net/feeds/user/8769 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/120011/permutations-that-preserve-cesaro-mean Permutations that preserve Cesaro mean Daniel Mansfield 2013-01-27T11:28:56Z 2013-01-31T11:07:50Z <p>Given a summable sequence $a_i$ of real numbers, theorems of Levi and later Agnew characterize the permutations $\pi: \mathbb N \mapsto \mathbb N$ which are sum preserveing: that is</p> <p>$$\lim_{n\to\infty}\sum_{i=1}^n a_{i} = \lim_{n\to\infty}\sum_{i=1}^n a_{\pi(i)}$$</p> <p>I would like to know of any similar research into permutations that preserve the Cesaro mean. That is, given a sequence $b_i \in \ell^\infty$, is there any characterization of permutations which $$\lim_{n\to\infty} \frac{1}{n} \sum_{i=1}^n b_i = \lim_{n\to\infty} \frac{1}{n} \sum_{i=1}^n b_{\pi(i)}$$ </p> http://mathoverflow.net/questions/118758/question-about-entropy/118774#118774 Answer by Daniel Mansfield for Question about entropy Daniel Mansfield 2013-01-13T02:11:55Z 2013-01-13T06:45:44Z <p>I think that I can expand on RW's answer</p> <p>If $I$ is countably infinite, then we can cover $X$ with the countable partition $$X = \vee_{n=0}^\infty T^{-n}P$$ Take any element of this partition: $$Q = P_{n_0} \vee T^{-1}P_{n_1} \vee \cdots \vee T^{-i}P_{n_i} \vee \cdots$$ where $n_i \in [1,k]$. Then $$TQ = TP_{n_0} \vee P_{n_1} \vee T^{-1}P_{n_2} \vee \cdots \vee T^{-i+1}P_{n_i} \vee \cdots$$ is contained within partition element $$P_{n_1} \vee T^{-1}P_{n_2} \vee \cdots \vee T^{-i+1}P_{n_i} \vee \cdots$$ so $TQ$ (or more generally $T^iQ$) is either disjoint from $Q$ (when it is contained within another partition), or equal to $Q$</p> <p>There are two possibilities for the measure of $Q$:</p> <p>(1) the measure of $Q$ is zero, or</p> <p>(2) the measure of $Q$ is positive, and $T^nQ=T^{n+k}Q$ for some $n,k &lt; \infty$. Otherwise $\{T^iQ\}$ is an infinite sequence of disjoint sets, each of constant measure $\mu(Q)$, and</p> <p>$$\infty = \sum_{i=1}^\infty \mu(Q) = \sum_{i=1}^\infty \mu(T^iQ) \leq \mu(X) = 1$$</p> <p>Hence there are (possibly infinitely many) $Q$'s of finite measure, each with finite orbit.</p> <p>Each $Q$ represents the set of points that are indistinguishable in your topology, so we can say that the space you are talking about is really just a (countable) union of finite orbits with an atomic probability measure.</p> http://mathoverflow.net/questions/93516/cesaro-means-and-banach-limits/118595#118595 Answer by Daniel Mansfield for Cesaro means and Banach limits Daniel Mansfield 2013-01-11T01:03:19Z 2013-01-12T00:57:40Z <p>If $(x_n) \in \ell^\infty$. According to Lorenz the Banch limit is unique (also known as <em>almost convergent</em>) iff $$\lim_{p\mapsto\infty} \frac{ x_n + x_{n+1} + \cdots + x_{n+p}}{p} = L \quad (*)$$ uniformly in $n$. Setting $n=0$ yields Cesaro summability.</p> <p>As Aaron says, the converse is false. If each $x_n$ is chosen uniformly at random from $\{0,1\}$ then this sequence almost never has property $(*)$ (see Connor's appropriately named article <em>Almost none of the sequences of 0's and 1's are almost convergent</em>)</p> <p>However the Cesaro limit of this random sequence $(x_n)$ is almost always $1/2$ by the law of large numbers.</p> http://mathoverflow.net/questions/102979/a-name-for-radon-nikodym-derivatives-that-are-bound-away-from-zero-and-infinity A name for Radon-Nikodym derivatives that are bound away from zero and infinity Daniel Mansfield 2012-07-24T04:37:55Z 2012-07-24T10:33:10Z <p>Dear Mathoverflow, </p> <p>I would like to know if the nomenclature of mathematics has a name for Radon-Nikodym derivatives that are bounded away from zero and infinity almost everywhere. As in for equivalent measures $\mu, \nu$, there exists constants $c,C$ such that $$0 &lt; c \leq \frac{d\nu}{d\mu}(x) \leq C &lt; \infty$$ for $\mu$-almost every $x$.</p> <p>Such measures could be called <em>boundedly equivalent</em>. But if there already exists a name, I'd like to use it.</p> <p>Another possibility is to say the measures are <em>correlated</em>. Intuitively the condition means $\mu$ and $\nu$ either both give small or large values to the same $x$. However this is word already has a lot of meaning in maths - perhaps it is best not to add more.</p> <p>Also, I'm open to suggestion if someone would like to offer a better name.</p> http://mathoverflow.net/questions/87109/recurrence-for-sets-of-finite-measure-on-infinite-measure-space Recurrence for sets of finite measure on infinite measure space Daniel Mansfield 2012-01-31T05:44:23Z 2012-02-02T03:06:01Z <p>Thanks to your helpful feedback, I have made my claim more precise.</p> <p><strong>Claim</strong></p> <p>Given an infinite measure space $\left( X,\mathcal B, \mu\right)$ and an ergodic, invertible, measure preserving and conservative transformation $T$. Let $n_i \in \mathbb Z, i \in \mathbb N$ and $W\in \mathcal B$ be an exhaustive weakly wandering sequence. Then for any measurable set $A$ of finite measure, almost every $x \in A, T^{n_i - n_k}x \in A$ finitely many times (where $k$ is chosen such that $x \in T^{n_k}W$, and $n_i > n_k$).</p> <p>This is to be contrasted with the recurrence theorem. If $T$ is conservative, then for almost every $x \in A$, $T^{n}x \in A$ for infinitely many $n \in \mathbb N$. I claim that $T^nx \in A$ for finitely many $n \in \{n_i - n_k\}, n_i > n_k$. </p> <p><strong>Proof</strong></p> <p>Under these assumptions, an exhaustive weakly wandering set will always exist. Hence there is a set $W$ and integers $n_i, i \in \mathbb N$ such that $T^{n_i}W \cap T^{n_j}W = \emptyset, i \neq j$ and the sets $T^{n_i}W$ cover $X$.</p> <p>Given any set $A \in \mathcal B$ of finite measure, let $B \subseteq A$ be the set of points which recur infinitely often in $A$. That this set is measurable can be shown by the same method used in the recurrence theorem.</p> <p>Suppose $x \in B \cap T^{n_k}W$ for some fixed $k$. Without loss of generality, and with some improvement in readability, assume $n_k = 0$, so we need to prove that for $x \in B \cap W$, then only finitely many $T^{n_i}x \in B$ for $n_i > 0$.</p> <p>Let $I = \{ i : \mu(T^{n_i}W \cap B) > 0\}$. If $|I|&lt;\infty$ and $x \in T^{n_k} W \cap B, k \in I$, then $T^{n_i - n_k}x \in T^{n_i}W$ is disjoint from the cover of $B$ for $i \in \mathbb N - I$. Hence only for $i\in I$ can $T^{n_i - n_k}x$ return to $B$.</p> <p>Now suppose $|I|=\infty$: that infinitely many of the sets $T^{n_i}W \cap B$ have positive measure. Because $\infty > \mu(A) \geq \mu(B) = \sum_{i=0}^\infty \mu(B \cap T^{n_i}W)$, then for any $\epsilon > 0$ there exists an $N$ such that for all $k > N$</p> <p>$$\sum_{i=k}^\infty \mu(B \cap T^{n_i}W) &lt; \epsilon$$</p> <p>Let $\epsilon = \mu(B \cap W) > 0$ and recall for $x \in B \cap W$ that infinitely many $T^{n_i}x \in B$. Then each element of $B\cap W$ will eventually find its way into $B \cap (\cup_{i=N}^\infty T^{n_i}W)$, the measure of the former should be less than or equal to the measure of the latter; yet this is not so. To be precise, for any $x \in B\cap W$. Let $\sigma(x)$ be the smallest return time to $B$ greater than $n_N$. We can subdivide $B\cap W$ into sets according to this return time: $B_{n_i} = \{ x \in B\cap W : \sigma(x) = n_i\}$, where each $B_{n_i}$ has the property that $T^{n_i}B_{n_i} \subset B \cap T^{n_i}W$. Hence</p> <p>$$\epsilon = \mu(B\cap W) = \sum_{i=N}^\infty \mu(B_{n_i}) = \sum_{i=N}^\infty \mu(T^{n_i}B_{n_i}) \leq \sum_{i=N}^\infty \mu(B \cap T^{n_i}W) &lt; \epsilon$$</p> <p>a contradiction. Hence either $\mu(B\cap W) = 0$ or the $T^{n_i}x \in B$ only finitely often.</p> http://mathoverflow.net/questions/83028/the-average-recurrence-time The average recurrence time Daniel Mansfield 2011-12-09T04:24:54Z 2011-12-09T06:24:09Z <p>As seen on <a href="http://en.wikipedia.org/wiki/Ergodic_theory#Sojourn_time" rel="nofollow">wikipedia</a>, given a measure space $(X,\Sigma,\mu)$ with $\mu(X) &lt; \infty$ and a measure preserving transformation $T: X \mapsto X$. Let $A \subset X$ be a set of positive measure. Define $k_i$ as the power of $T$ such that $T^{k_i}x \in A$ for the $i$th time: that is to say $k_i$ is the "$i$'th return time to $A$". The difference between recurrence times is $R_i = k_i - k_{i-1}$ (assume for simplicity that $k_0 = 0$, that is $x \in A$)</p> <p>I would like know how to prove the following:</p> <p>$$\lim\limits_{n\mapsto\infty} \frac{R_1 + \cdots + R_n}{n} = \frac{\mu(X)}{\mu(A)}$$</p> <p>The <a href="http://en.wikipedia.org/wiki/Ergodic_theory#Sojourn_time" rel="nofollow">wikipedia article</a> indicates that this is a consequence of the ergodic theorem.</p> <p>Note that my definition of the $k_i$ above differs slightly from that of wikipedia, in as much as I have omitted to say that the $k_i$s are sorted in increasing order.</p> http://mathoverflow.net/questions/82501/expected-number-of-overlapping-edges-from-k-cycles-in-a-graph/82601#82601 Answer by Daniel Mansfield for expected number of overlapping edges from k cycles in a graph Daniel Mansfield 2011-12-04T07:31:50Z 2011-12-04T07:31:50Z <p><em>disclaimer: Please cast a careful eye over the definition of $L(k)$. I hope you can salvage enough from this to answer your question.</em></p> <p>Let $\mathcal P$ be the set of all paths in $\mathcal T$, and define $f: \mathcal P \mapsto \overline{\mathcal{E}_T}$ as the map </p> <p>$$f((v_0,\ldots,v_{k-1}) ) = (v_0,v_{k-1})$$</p> <p>Choose any path $p \in \mathcal P$ of length $k$. Let $C(p)$ be the set of all paths in $\mathcal T$ containing $p$. Choose two elements $a,b \in C(p)$ there are edges $f(a),f(b)$ such that </p> <p>$$|c(f(a)) \cap c(f(b))| \geq k$$</p> <p>Conversely, note that if $|c(e_i) \cap c(e_j)| \geq k$ then both $c(e_i)$ and $c(e_j)$ share a common path in $\mathcal T$ of length not less than $k$. </p> <p>Hence the number of edges which share a path of length $\geq k$ is</p> <p>$$L(k) = \sum_{p \in \mathcal P, |p| = k-1} C^{|C(p)|}_2$$</p> <p>To calculate the expected number of edges that are shared, observe that $k$ must be strictly less than the length of the longest path $l$ (Lukasz provided some examples). So $L(n-1) = \cdots = L(l) = 0$. Calculate $L(l-1), L(l-2), \ldots L(1)$. Then the expected shared number of edges is</p> <p>$$\sum_{k=1}^{l-1} k * \frac{L(k) - L(k+1)}{(n/2)(n-1) - (n-1)}$$</p> http://mathoverflow.net/questions/77036/system-with-invariant-measure-but-no-ergodic-measure/77091#77091 Answer by Daniel Mansfield for System with invariant measure, but no ergodic measure. Daniel Mansfield 2011-10-04T00:53:39Z 2011-10-04T01:19:46Z <p>To answer question 1, I think there will always be a measure for which $T$ is ergodic.</p> <p>Rotation of the unit circle $T(z) = az$ is measure preserving, (with Haar measure) and ergodic only when $a$ is not a root of unity. (Walters, P. <em>Introduction to Ergodic Theory</em>, Theorem 1.8).</p> <p>However, we can still define a measure for which $T$ <strong>is</strong> ergodic. Say $\mu(\{a^k\}) = 1/n$ where $a$ an $n$-th root of unity, $k=0,\ldots, n-1$. Then the $T$-invariant sets either have measure 0 or 1.</p> <p>When there are periodic points we can use the above argument to create an ergodic measure. </p> <p>The argument is not very different in the absence of periodic points. For any measure preserving system $(X,\mathcal B, \nu)$ take any element $a \in X$ and define $orb_T(a) = \{T^na: n \in \mathbb Z\}$. Let $\mu$ be a probability measure on $\mathcal B / orb_T(a)$ with $\mu(0 + orb_T(a)) = 1$ and zero otherwise. Then $T$ is ergodic on $(X, \mathcal B/ orb_T(a), \mu)$.</p> http://mathoverflow.net/questions/76908/supremum-amongst-kolmogorov-sinai-entropies-ergodic-or-just-invariant-measures/77006#77006 Answer by Daniel Mansfield for Supremum amongst Kolmogorov-Sinai entropies: ergodic or just invariant measures. Daniel Mansfield 2011-10-03T03:07:08Z 2011-10-03T03:07:08Z <p>Welcome to mathoverflow!</p> <p>I believe I can answer question 3. My reference here is Walters, P. <em>An introduction to Ergodic Theory</em>. Chapter 6.2.</p> <p>When $T: X \mapsto X$ is a continuous transformation of a compact metrisable space $X$, then there will always be a measure for which $T$ is measure preserving. Hence $M(T)$ is never empty. (Corollary 6.9.1)</p> <p>The space $M(T)$ is compact, convex and nonempty. Hence it has an extreme point by <a href="http://mathoverflow.net/questions/15654/extreme-point-compact-convex-set" rel="nofollow">this argument</a>. </p> <p>The extreme points are the ergodic measures (Walters theorem 6.10(iii))</p> <p>Hence $E(T) \neq \emptyset$.</p> http://mathoverflow.net/questions/75171/refining-ladders-and-orbit-segments-with-a-picture Refining ladders and orbit segments - with a picture Daniel Mansfield 2011-09-11T22:38:26Z 2011-09-16T05:23:45Z <p>I am trying to understand the following paragraph from <a href="http://math.stanford.edu/~katznel/nonsingact.pdf" rel="nofollow">The Classification of Non-Singular Actions, Revisited</a>, page 5 paragraph 2. </p> <blockquote> <p>Remember that $S \in [T]$ so that for every $x\in X, S(x) = T^{n(x)}$. If $M_1$ is large compared with $n(x)$ for all but $\epsilon_1$ of the space, and compared with $M$ as well (and $\epsilon_1$ is taken small enough), the orbit segment $\{T^jx\}_{j=0}^M$ is in fact contained in some orbit segment of $\mathcal{L}_0$ for most $x$.</p> </blockquote> <p>So, choosing $M_1$ and $\epsilon_1$ apply Rohlin's lemma to the induced transformation on $C(0)$. This gives us that $\{{T \vert_{C(0)}}^jx\}_{j=0}^{M_1}$ is an orbit segment for all but $\epsilon_1$ of $C(0)$.</p> <p>But how does this imply that we have orbit segments outside of $C(0)$? I do not understand the significance of choosing $M_1$ to be large compared with $n(x)$ or $M$.</p> http://mathoverflow.net/questions/75171/refining-ladders-and-orbit-segments-with-a-picture/75467#75467 Answer by Daniel Mansfield for Refining ladders and orbit segments - with a picture Daniel Mansfield 2011-09-15T00:58:09Z 2011-09-16T00:21:56Z <p>I believe that I have the answer. I would like to hear what people think.</p> <p>The objective here is to prove $\{x,Tx,\ldots,T^{M-1}x\}$ lie in the same orbit segment $\{ S^j(y)\}_{j=0}^\infty$, for all but $\epsilon$ of the space.</p> <p>Given a ladder $\mathcal{L} = \mathcal{L}(\{C(i)\},N,S)$. For any $x \in X$ there exists $y_0 \in C(0)$ such that $x = S^{j_0}(y_0) = T^{n_0}(y_0)$ with $j_0 &lt; N$.</p> <p>Similarly, for $T^kx \in X$, $k \in \{1,\ldots,M\}$ there exists some $y_k \in C(0)$ such that $T^kx = S^{j_k}(y_k) = T^{n_k}(y_k)$ with $j_k &lt; N$. So</p> <p>$$T^{n_k}(y_k) = T^k(x) = T^{n_0 + k}(y_0)$$</p> <p>$$y_k = T^{n_0 + k - n_k}(y_0)$$</p> <p>That is to say, each of the $y_k \in C(0)$ can be placed in the $T$-orbit of $y_0$. Rearrangement of the $y_k$ may be necessary to make the exponent of $T$ positive. Since $y_k \in C(0)$, we can further say that each of the $y_k$ can be placed in the same $T\vert_{C(0)}$ orbit of $y_0$.</p> <p><img src="http://web.maths.unsw.edu.au/~danielmansfield/images/ladder_combination.png" alt="Graphical representation of how the orbit $T^i(x)$ is related to the orbit of the ladder on $C(0)$"></p> <p>Let $M_1$ be so large that for all but $\epsilon/2M$ of the space the return time to $C(0)$ is less than $M_1$. Then for all but $\epsilon/2$ of the space, $n_k &lt; M_1$ and $n_0 + k - n_k &lt; M_1 + k &lt; M + M_1$</p> <p>By Rohlin's lemma we can create $\mathcal{L}_0$ which (except on a set of measure $\epsilon/2$) contains any orbit segments of length $M + M_1$. This new ladder contains $\{ y_{k}\}_{k=0}^M$ as an orbit segment for all but $\epsilon/2$ of the space $C(0)$.</p> <p>Refining $\mathcal{L}$ by $\mathcal{L}_0$ gives a new ladder $\mathcal{L}_1$. By construction, the orbit of $\{S_1^j(y_0)\}_{j=0}^\infty$ contain $y_k$ because $S_1^N = T \vert_{C(0)}$, and for any $k &lt; M$</p> <p>$$T^k(x) = S^{j_k}(y_k) \in \{S^j(y_k)\}_{j=1}^N \subset \{S_1^j(y_0)\}_{j=0}^\infty$$</p> http://mathoverflow.net/questions/73717/point-mapping-induces-a-set-mapping Point mapping induces a set mapping Daniel Mansfield 2011-08-26T01:52:24Z 2011-09-06T04:19:27Z <p>Mathematics is the universal language. </p> <p>That is, until someone says the word "obvious", or "well known". At which point it becomes relative to the reader.</p> <p>My question is about a "well known" theorem. My problem is that it is not known to me. But I would like to know.</p> <p>The following comes from Y. Katznelson and B. Weiss <a href="http://math.stanford.edu/~katznel/nonsingact.pdf" rel="nofollow">The Classification of Non-Singular Actions, Revisited</a>, J. Ergodic Theory and Dynamical Systems, 11, 1991. Page 4.</p> <p>It reads:</p> <blockquote> <p>Thus the family {$\theta_k$} defines a Boolean set mapping between the $\sigma$-algebras generated by the ladder sets. If the ladder sets are both "algebra complete", a well known theorem implies that there exists a point mapping $\theta : X \mapsto X^\prime$ which induces a set mapping.</p> </blockquote> <p>Can someone please tell me which theorem they are referring to here?</p> http://mathoverflow.net/questions/74503/different-uses-of-the-word-ergodic Different uses of the word "ergodic" Daniel Mansfield 2011-09-04T09:10:52Z 2011-09-04T10:38:36Z <p>There appear to be two definitions of the word ergodic. </p> <p>The dynamical systems definition says that a measure space $(X,\mathit B, \mu)$ and measure preserving transformation $T: X \mapsto X$ is <em>ergodic</em> if</p> <blockquote> <p>the only $T$-invariant sets have measure 0 or 1.</p> </blockquote> <p>However, a Markov chain is ergodic if </p> <blockquote> <p>there exists $t$ such that for all $x,y \in \Omega, P^t(x,y) >0$</p> </blockquote> <p>I've used the Markov chain notation and definition found <a href="http://www.cc.gatech.edu/~vigoda/MCMC_Course/MC-basics.pdf" rel="nofollow">here</a></p> <p>I would like to know if these definitions are equivalent.</p> <p>Of course, I am asking here because it seems to me that they are not. For example, if $X=\{0,1\}$, $\mathit B = \{\emptyset, \{0\},\{1\},X\}$, $\mu(\{0\})=0,\mu(\{1\})=1$ and $T(x) = 1$ for all $x\in X$, then $(X,\mathit B, \mu, T)$ is ergodic as a dynamical system, but the equivalent Markov chain is not ergodic, since the probability of traveling from $0$ to $1$ is zero. </p> http://mathoverflow.net/questions/66785/how-to-determine-a-specific-graph-process-is-markovian-or-not/74353#74353 Answer by Daniel Mansfield for How to determine a specific graph process is Markovian or not ? Daniel Mansfield 2011-09-02T12:50:35Z 2011-09-04T09:13:20Z <p>Let me check that I understand you correctly.</p> <p>Let $Y(t)$ be the $n+1$-dimensional vector $Y(t) = \otimes_{i=0}^n Y^t_i$ where $Y^t_i$ represents the number of verticies with degree $i$ at time $t$. When time increases by $1$, add an edge at random.</p> <p>So, $Y(0) = (n,0,0,\ldots,0)$, $Y(1) = (n-2,2,0,\ldots,0)$, </p> <p>$Y(2) = (n-4,4,0,0,\ldots,0)$ if the new edge is not adjacent to the old edge, or $Y(2) = (n-3,2,1,0,\ldots,0)$ if the new edge is adjacent to the old edge.</p> <p>At time $t$, the new edge is chosen at random by choosing one vertex of degree $i$ with probability $Y^t_i/(n - Y^t_n)$ and another of degree $j$ with probability $Y^t_j/(n - Y^t_n - 1)$ if $j\neq i$ and probability $(Y^t_j-1)/(n - Y^t_n-1)$ if $j=i$.</p> <p>Assuming $j\neq i$ (a simple adjustment is necessary for the $i=j$ case), the probability moving from $Y(t)$ to $Y(t+1)$ where $Y^{t+1}_k = Y^t_k - 1$ and $Y^{t+1}_k = Y^t_k + 1$ for $k= i,j$ and $Y^{t+1}_k = Y^t_k$ for $k \neq i,j$ is therefore $$\frac{Y^t_i Y^t_j}{2(n - Y^t_n)(n - Y^t_n-1)}$$ Which only depends on the present state, and is independent of the history of the previous $t-1$ steps. Hence it is a Markov chain.</p> http://mathoverflow.net/questions/74029/what-is-meant-by-invariant-measure-on-a-graph/74037#74037 Answer by Daniel Mansfield for What is meant by Invariant Measure on a Graph Daniel Mansfield 2011-08-30T03:32:41Z 2011-08-30T04:45:51Z <p>I agree with @Gjergji that the technical answer you require is on page 4 of the paper you reference.</p> <blockquote> <p>A measure $m$ on $S_L$ is <em>invariant</em> when it is invariant under the action of $\mathfrak G_{\mathbb N}$ (the permutation group of $\mathbb N$), i.e., for every Borel set $X \subseteq S_L$ and every $g \in \mathfrak G_{\mathbb N}$, we have $m(X) = m(g.X)$.</p> </blockquote> <p>So, they put a measure m on the space of your special graphs. For any set of graphs $X \subseteq S_L$, we measure the size of this set as $m(X)$. If we rename all the verticies of $X$ and call this set $g.X$, then these sets have equal measure $m(X)=m(g.X)$.</p> <p>So, to your friend, you can say that "invariant measure" means that the measure assigns the same number to sets of isomorphic graphs.</p> http://mathoverflow.net/questions/73726/generating-r-regular-random-graph-in-parallel/73735#73735 Answer by Daniel Mansfield for Generating r-Regular Random Graph in Parallel Daniel Mansfield 2011-08-26T06:19:16Z 2011-08-26T06:19:16Z <p>This question is more difficult that it seems.</p> <p>Firstly, there is a difference between picking edges of a graph uniformly, and picking a $r$-regular graph uniformly.</p> <p>Let $G_{r,n}$ be the set of $r$-regular graphs on $n$ nodes. By "uniformly pick a $r$-regular graph", you need to create an algorithm that chooses $G \in G_{r,n}$ with probability $1/|G_{r,n}|$. There are probabilistic methods to do this, perhaps they even lend themselves to parallelization. </p> <p>See the section on algorithms for generation of random regular graphs <a href="http://en.wikipedia.org/wiki/Random_regular_graph" rel="nofollow">here</a>. In particular,B. McKay and N. Wormald, <a href="http://cs.anu.edu.au/~bdm/papers/RandRegGen.pdf" rel="nofollow">Uniform Generation of Random Regular Graphs of Moderate Degree,</a> Journal of Algorithms, Vol. 11 (1990), pp 52-67</p> http://mathoverflow.net/questions/36607/does-essentially-minimal-imply-minimal Does essentially minimal imply minimal? Daniel Mansfield 2010-08-25T00:34:55Z 2010-08-25T04:09:36Z <p>Suppose X is compact and totally disconnected space, and that phi a homeomorphism of X.</p> <p>We say a subset Z of X is phi-invariant if phi(Z) = Z. A phi-invariant set is minimal if it is closed, phi-invariant, nonempty and the smallest of all such sets. We say (X,phi) is minimal if X itself is a minimal set.</p> <p>An orbit of x in X is the set {phi^n(x) : n an integer}</p> <p>A system (X,phi) is minimal iff every orbit is dense.</p> <p>Given (X,phi) as above, and any point y in X. The system is "essentially minimal" if one of the following equivalent conditions hold: 1) For all x in X, y in { phi^n(x) : n >= 0, n an integer }. 2) For all x in X, y in { phi^n(x) : n &lt; 0, n an integer }. 3) X contains a unique minimal set Y, and y in Y.</p> <p>If a system is minimal, then condition 3 is satisfied (setting Y := X), and is hence essentially minimal.</p> <p>Does essential minimality imply minimality?</p> http://mathoverflow.net/questions/120011/permutations-that-preserve-cesaro-mean Comment by Daniel Mansfield Daniel Mansfield 2013-01-31T11:13:50Z 2013-01-31T11:13:50Z Permutations preserving Cesaro mean for any sequence would be the Levy group. See theorem 2 of M. Bl&#252;mlinger; N. Obata &quot;Permutations preserving Ces&#224;ro mean, densities of natural numbers and uniform distribution of sequences&quot; (1991) http://mathoverflow.net/questions/120011/permutations-that-preserve-cesaro-mean Comment by Daniel Mansfield Daniel Mansfield 2013-01-31T04:44:20Z 2013-01-31T04:44:20Z I do mean the set $S$ of permutations preserving a given Cesaro mean. http://mathoverflow.net/questions/118758/question-about-entropy/118764#118764 Comment by Daniel Mansfield Daniel Mansfield 2013-01-13T08:39:28Z 2013-01-13T08:39:28Z I like this answer because it answers what the question should have been. http://mathoverflow.net/questions/118758/question-about-entropy/118774#118774 Comment by Daniel Mansfield Daniel Mansfield 2013-01-13T05:48:54Z 2013-01-13T05:48:54Z Thank you Anthony, $TQ$ is not necessarily an element of the partition. I have modified the answer in response to your comment. http://mathoverflow.net/questions/105530/the-behavior-of-a-product-with-specified-rates-of-growth-for-two-variables Comment by Daniel Mansfield Daniel Mansfield 2012-08-26T13:30:02Z 2012-08-26T13:30:02Z Can $P[N^u,R+w]$ be defined when $N^u$ is not an integer? Or does $u$ have to be chosen such that $N^u$ is always an integer? http://mathoverflow.net/questions/102979/a-name-for-radon-nikodym-derivatives-that-are-bound-away-from-zero-and-infinity/102994#102994 Comment by Daniel Mansfield Daniel Mansfield 2012-07-25T01:07:15Z 2012-07-25T01:07:15Z Thank you for your answer. Uniformly equivalent it shall be. http://mathoverflow.net/questions/87109/recurrence-for-sets-of-finite-measure-on-infinite-measure-space/87123#87123 Comment by Daniel Mansfield Daniel Mansfield 2012-02-01T04:13:03Z 2012-02-01T04:13:03Z Thank you Jerome, You are correct, except that I've changed the question now: the dissipative assumption has been dropped, and I claim something more consistent with $T$ being conservative. http://mathoverflow.net/questions/87109/recurrence-for-sets-of-finite-measure-on-infinite-measure-space Comment by Daniel Mansfield Daniel Mansfield 2012-02-01T04:09:38Z 2012-02-01T04:09:38Z I meant that a sub collection of them cover $B \subset X$. I've removed that bit now because it was over-complicating the matter. http://mathoverflow.net/questions/83028/the-average-recurrence-time/83033#83033 Comment by Daniel Mansfield Daniel Mansfield 2011-12-10T04:45:48Z 2011-12-10T04:45:48Z Thank you very much for your answer. http://mathoverflow.net/questions/82501/expected-number-of-overlapping-edges-from-k-cycles-in-a-graph/82601#82601 Comment by Daniel Mansfield Daniel Mansfield 2011-12-04T23:11:47Z 2011-12-04T23:11:47Z I mean &quot;the number of ways $2$ objects can be chosen from $|C(p)|$&quot;. http://mathoverflow.net/questions/78411/complexity-of-bipartite-graphs-and-their-matchings Comment by Daniel Mansfield Daniel Mansfield 2011-10-19T05:42:00Z 2011-10-19T05:42:00Z How can an algorithm check all $2^i$ edges of a matching in polynomial time in the order of $i$? http://mathoverflow.net/questions/77036/system-with-invariant-measure-but-no-ergodic-measure/77091#77091 Comment by Daniel Mansfield Daniel Mansfield 2011-10-04T01:34:56Z 2011-10-04T01:34:56Z So in the example of $Tx = x+1$ on $\mathbb R$ with measurable sets $\mathit B$. You can actually define a invariant measure and an ergodic measure. Say we let measure $\mu$ be 1 on the integers; 0 elsewhere. Then $(X, \mathit B / \mathbb N, \mu, T)$ is ergodic. The catch here is that subsets of the integers are not measurable. http://mathoverflow.net/questions/76908/supremum-amongst-kolmogorov-sinai-entropies-ergodic-or-just-invariant-measures/77006#77006 Comment by Daniel Mansfield Daniel Mansfield 2011-10-03T06:15:53Z 2011-10-03T06:15:53Z Perhaps I misunderstood. Are you interested in the case where $X$ is not compact? For if the space is compact, $E(T)$ will not be empty. http://mathoverflow.net/questions/76701/is-there-a-way-to-solve-the-following-equation Comment by Daniel Mansfield Daniel Mansfield 2011-09-28T23:04:08Z 2011-09-28T23:04:08Z Two questions: (1) does $A^t$ mean the transpose of $A$, or the $t$'th power of $A$? (2) does 'diag($B$)' refer to the vector whose elements are the diagonal elements of $B$? http://mathoverflow.net/questions/75567/spanning-trees-in-3-regular-graphs Comment by Daniel Mansfield Daniel Mansfield 2011-09-16T02:37:39Z 2011-09-16T02:37:39Z Also, I'm sure you can construct an example of 3-regular graphs which has many &quot;long&quot; paths and many &quot;short&quot; ones. It would look something like a big Y. Perhaps more detail about what is considered long and short would be helpful. Or, if you didn't like the big &quot;Y&quot;, here's another example <a href="http://t1.gstatic.com/images?q=tbn:ANd9GcQVMwMYe8ylqb9M7rQyVmz-LbZG_nmWFyA7Q9UWWPkjJUHzJ7Z5mqyBC9k" rel="nofollow">t1.gstatic.com/&hellip;</a>