User daniel mansfield - MathOverflow

Permutations that preserve Cesaro mean

2013-01-27T11:28:56Z

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

$$ \lim_{n\to\infty}\sum_{i=1}^n a_{i} = \lim_{n\to\infty}\sum_{i=1}^n a_{\pi(i)} $$

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)}$$

Answer by Daniel Mansfield for Question about entropy

2013-01-13T02:11:55Z

I think that I can expand on RW's answer

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$

There are two possibilities for the measure of $Q$:

(1) the measure of $Q$ is zero, or

(2) the measure of $Q$ is positive, and $T^nQ=T^{n+k}Q$ for some $n,k < \infty$. Otherwise $\{T^iQ\}$ is an infinite sequence of disjoint sets, each of constant measure $\mu(Q)$, and

$$ \infty = \sum_{i=1}^\infty \mu(Q) = \sum_{i=1}^\infty \mu(T^iQ) \leq \mu(X) = 1$$

Hence there are (possibly infinitely many) $Q$'s of finite measure, each with finite orbit.

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.

Answer by Daniel Mansfield for Cesaro means and Banach limits

2013-01-11T01:03:19Z

If $(x_n) \in \ell^\infty$. According to Lorenz the Banch limit is unique (also known as almost convergent) 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.

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 Almost none of the sequences of 0's and 1's are almost convergent)

However the Cesaro limit of this random sequence $(x_n)$ is almost always $1/2$ by the law of large numbers.

A name for Radon-Nikodym derivatives that are bound away from zero and infinity

2012-07-24T04:37:55Z

Dear Mathoverflow,

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 < c \leq \frac{d\nu}{d\mu}(x) \leq C < \infty$$ for $\mu$-almost every $x$.

Such measures could be called boundedly equivalent. But if there already exists a name, I'd like to use it.

Another possibility is to say the measures are correlated. 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.

Also, I'm open to suggestion if someone would like to offer a better name.

Recurrence for sets of finite measure on infinite measure space

2012-01-31T05:44:23Z

Thanks to your helpful feedback, I have made my claim more precise.

Claim

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$).

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$.

Proof

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$.

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.

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$.

Let $I = \{ i : \mu(T^{n_i}W \cap B) > 0\}$. If $|I|<\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$.

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$

$$\sum_{i=k}^\infty \mu(B \cap T^{n_i}W) < \epsilon$$

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

$$ \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) < \epsilon$$

a contradiction. Hence either $\mu(B\cap W) = 0$ or the $T^{n_i}x \in B$ only finitely often.

The average recurrence time

2011-12-09T04:24:54Z

As seen on wikipedia, given a measure space $(X,\Sigma,\mu)$ with $\mu(X) < \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$)

I would like know how to prove the following:

$$ \lim\limits_{n\mapsto\infty} \frac{R_1 + \cdots + R_n}{n} = \frac{\mu(X)}{\mu(A)}$$

The wikipedia article indicates that this is a consequence of the ergodic theorem.

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.

Answer by Daniel Mansfield for expected number of overlapping edges from k cycles in a graph

2011-12-04T07:31:50Z

disclaimer: Please cast a careful eye over the definition of $L(k)$. I hope you can salvage enough from this to answer your question.

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

$$ f((v_0,\ldots,v_{k-1}) ) = (v_0,v_{k-1}) $$

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

$$|c(f(a)) \cap c(f(b))| \geq k$$

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$.

Hence the number of edges which share a path of length $\geq k$ is

$$ L(k) = \sum_{p \in \mathcal P, |p| = k-1} C^{|C(p)|}_2 $$

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

$$ \sum_{k=1}^{l-1} k * \frac{L(k) - L(k+1)}{(n/2)(n-1) - (n-1)}$$

Answer by Daniel Mansfield for System with invariant measure, but no ergodic measure.

2011-10-04T00:53:39Z

To answer question 1, I think there will always be a measure for which $T$ is ergodic.

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. Introduction to Ergodic Theory, Theorem 1.8).

However, we can still define a measure for which $T$ is 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.

When there are periodic points we can use the above argument to create an ergodic measure.

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)$.

Answer by Daniel Mansfield for Supremum amongst Kolmogorov-Sinai entropies: ergodic or just invariant measures.

2011-10-03T03:07:08Z

Welcome to mathoverflow!

I believe I can answer question 3. My reference here is Walters, P. An introduction to Ergodic Theory. Chapter 6.2.

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)

The space $M(T)$ is compact, convex and nonempty. Hence it has an extreme point by this argument.

The extreme points are the ergodic measures (Walters theorem 6.10(iii))

Hence $E(T) \neq \emptyset$.

Refining ladders and orbit segments - with a picture

2011-09-11T22:38:26Z

I am trying to understand the following paragraph from The Classification of Non-Singular Actions, Revisited, page 5 paragraph 2.

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$.

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)$.

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$.

Answer by Daniel Mansfield for Refining ladders and orbit segments - with a picture

2011-09-15T00:58:09Z

I believe that I have the answer. I would like to hear what people think.

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.

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 < N$.

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 < N$. So

$$ T^{n_k}(y_k) = T^k(x) = T^{n_0 + k}(y_0) $$

$$y_k = T^{n_0 + k - n_k}(y_0)$$

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$.

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 < M_1$ and $n_0 + k - n_k < M_1 + k < M + M_1$

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)$.

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 < M$

$$ 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 $$

Point mapping induces a set mapping

2011-08-26T01:52:24Z

Mathematics is the universal language.

That is, until someone says the word "obvious", or "well known". At which point it becomes relative to the reader.

My question is about a "well known" theorem. My problem is that it is not known to me. But I would like to know.

The following comes from Y. Katznelson and B. Weiss The Classification of Non-Singular Actions, Revisited, J. Ergodic Theory and Dynamical Systems, 11, 1991. Page 4.

It reads:

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.

Can someone please tell me which theorem they are referring to here?

Different uses of the word "ergodic"

2011-09-04T09:10:52Z

There appear to be two definitions of the word ergodic.

The dynamical systems definition says that a measure space $(X,\mathit B, \mu)$ and measure preserving transformation $T: X \mapsto X$ is ergodic if

the only $T$-invariant sets have measure 0 or 1.

However, a Markov chain is ergodic if

there exists $t$ such that for all $x,y \in \Omega, P^t(x,y) >0$

I've used the Markov chain notation and definition found here

I would like to know if these definitions are equivalent.

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.

Answer by Daniel Mansfield for How to determine a specific graph process is Markovian or not ?

2011-09-02T12:50:35Z

Let me check that I understand you correctly.

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.

So, $Y(0) = (n,0,0,\ldots,0)$, $Y(1) = (n-2,2,0,\ldots,0)$,

$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.

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$.

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.

Answer by Daniel Mansfield for What is meant by Invariant Measure on a Graph

2011-08-30T03:32:41Z

I agree with @Gjergji that the technical answer you require is on page 4 of the paper you reference.

A measure $m$ on $S_L$ is invariant 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)$.

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)$.

So, to your friend, you can say that "invariant measure" means that the measure assigns the same number to sets of isomorphic graphs.

Answer by Daniel Mansfield for Generating r-Regular Random Graph in Parallel

2011-08-26T06:19:16Z

This question is more difficult that it seems.

Firstly, there is a difference between picking edges of a graph uniformly, and picking a $r$-regular graph uniformly.

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.

See the section on algorithms for generation of random regular graphs here. In particular,B. McKay and N. Wormald, Uniform Generation of Random Regular Graphs of Moderate Degree, Journal of Algorithms, Vol. 11 (1990), pp 52-67

Does essentially minimal imply minimal?

2010-08-25T00:34:55Z

Suppose X is compact and totally disconnected space, and that phi a homeomorphism of X.

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.

An orbit of x in X is the set {phi^n(x) : n an integer}

A system (X,phi) is minimal iff every orbit is dense.

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 < 0, n an integer }. 3) X contains a unique minimal set Y, and y in Y.

If a system is minimal, then condition 3 is satisfied (setting Y := X), and is hence essentially minimal.

Does essential minimality imply minimality?

Comment by Daniel Mansfield

2013-01-31T11:13:50Z

Permutations preserving Cesaro mean for any sequence would be the Levy group. See theorem 2 of M. Blümlinger; N. Obata "Permutations preserving Cesàro mean, densities of natural numbers and uniform distribution of sequences" (1991)

Comment by Daniel Mansfield

2013-01-31T04:44:20Z

I do mean the set $S$ of permutations preserving a given Cesaro mean.

Comment by Daniel Mansfield

2013-01-13T08:39:28Z

I like this answer because it answers what the question should have been.

Comment by Daniel Mansfield

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.

Comment by Daniel Mansfield

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?

Comment by Daniel Mansfield

2012-07-25T01:07:15Z

Thank you for your answer. Uniformly equivalent it shall be.

Comment by Daniel Mansfield

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.

Comment by Daniel Mansfield

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.

Comment by Daniel Mansfield

2011-12-10T04:45:48Z

Thank you very much for your answer.

Comment by Daniel Mansfield

2011-12-04T23:11:47Z

I mean "the number of ways $2$ objects can be chosen from $|C(p)|$".

Comment by Daniel Mansfield

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$?

Comment by Daniel Mansfield

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.

Comment by Daniel Mansfield

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.

Comment by Daniel Mansfield

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$?

Comment by Daniel Mansfield

2011-09-16T02:37:39Z

Also, I'm sure you can construct an example of 3-regular graphs which has many "long" paths and many "short" 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 "Y", here's another example t1.gstatic.com/…