User algernon - MathOverflow

Answer by Algernon for Variational Principle for the Entropy

2013-05-10T22:16:46Z

The mapping $f$ does not really need to be a homeomorphism. The variational principle of the entropy is valid for all continuous mappings. (See e.g., the book of Peter Walters)
A simple (boring) example of an expansive dynamical system on a compact metric space having multiple measures with maximal entropy will be the direct sum of two copies of your favorite example that has a unique measure with maximal entropy.

Another (more interesting) example is when the system has zero topological entropy but is not uniquely ergodic. In particular, there are minimal systems that are not uniquely ergodic and have zero topological entropy. However, one might still consider such examples pathological.

Multiplicity of measures with maximal entropy could be interpreted as some kind of "phase transition". If measures with maximal entropy model the equilibrium states of a system (in the sense of statistical mechanics), then multiplicity of maximal entropy measures would mean the system has multiple "macroscopically distinguishable" equilibrium states.

If you allow two-dimensional dynamics (two commuting maps rather than one), Burton and Steif found examples of two-dimensional subshifts of finite type that are strongly irreducible and have more than one measures of maximal entropy. Häggström later showed that in fact essentially any statistical mechanics model on the lattice with finite-range interactions is "equivalent" to a strongly irreducible subshift of finite type, so that the shift-invariant Gibbs measures of the former are in one-to-one correspondence with the maximal entropy measures of the latter.

Answer by Algernon for Is rigour just a ritual that most mathematicians wish to get rid of if they could?

2013-04-25T20:06:13Z

Highly recommended is this article by the late Vladimir Arnold, in which he talks of a "strong mafia of left-brained mathematicians" who "succeeded in eliminating all geometry from the mathematical education [...] replacing the study of all content in mathematics by the training in formal proofs and the manipulation of abstract notions." (Page 3 and the first half of page 4 are relevant to the question.)

Update (following Misha's comment):

Rigor is often mistaken with excessive formalism and voiding of arguments from intuitions to the extent that the proofs are more suitable for computers than humans. Arnold's article (and indeed most attacks on "rigor" such as the one the OP is referring to) criticize excessive formalism. The real rigor, on the contrary, has no conflict with intuition. Far from it, rigor (which is the basis of mathematics) is the refinement of intuition to the point that it is free from logical sloppiness. Rigor therefore should enhance intuition rather than abolishing it. Where to set the threshold of sloppiness? Arnold would probably set it on the basis of practicality and in connection with the originating real-world problems.

Answer by Algernon for compute the waiting time for a given pattern with Kac's lemma

2013-03-30T11:28:08Z

I do not know if this would qualify for you as a solution using Kac's lemma, but here it goes ...

The elementary version of Kac's lemma for an irreducible Markov chain with unique stationary distribution $\pi$ states that the expected return time of each state $a$ is $1/\pi(a)$. This follows from the ergodic theory version if you consider the (one-sided) Markov shift associated to the Markov chain and look at the return time of the cylinder set $\{(\omega_i)_{i\geq 0}: \omega_0=a\}$.

As Sesh mentioned, you can formulate your problem in terms of a Markov chain whose states are all the words of length $5$ on $\{\mathtt{H},\mathtt{T}\}$ with transitions $w_0w_1w_2w_3w_4\to w_1w_2w_3w_4\mathtt{H}$ and $w_0w_1w_2w_3w_4\to w_1w_2w_3w_4\mathtt{T}$ of equal probability from each state $w_0w_1w_2w_3w_4$. This is the $5$-bit shift register chain. The stationary distribution is uniform, so if $T_u$ denotes the first time $>0$ the shift register is in state $u:=\mathtt{HTHTH}$, we have $\mathbb{E}_u T_u=32$, where $\mathbb{E}_u$ is the expected value if the shift register is initialized with $u$.

However, you ask for $\mathbb{E}_\varnothing T_u$, where I am using $\mathbb{E}_\varnothing$ to to denote the expectation if the initial state has no overlap with $u$ (or if the shift register is empty, if you will).

Conditioning on the first two coin flips we get \begin{align} \mathbb{E}_uT_u &= \frac{1}{2}(1+\mathbb{E}_{\mathtt{H}}T_u) + \frac{1}{4}2 + \frac{1}{4}(2+\mathbb{E}_\varnothing T_u) \;. \end{align} The first term is for when the first flip comes up $\mathtt{H}$, the second for when the first two flips turn out $\mathtt{TH}$ (hence returning to $u$) and the third for if the first two flips are $\mathtt{TT}$. I am writing $\mathbb{E}_{\mathtt{H}}$ for the expectation if the initial state has the form $w_0w_1w_2w_3 \mathtt{H}$ and the only possible overlap with $u$ is with the last bit.

A similar equation can be written for $\mathbb{E}_\varnothing T_u$ by conditioning on the first flip: \begin{align} \mathbb{E}_\varnothing T_u &= \frac{1}{2}(1+\mathbb{E}_{\mathtt{H}}T_u) + \frac{1}{2}(1+\mathbb{E}_{\varnothing}T_u) \end{align}

Solving the two equations for $\mathbb{E}_\varnothing T_u$ we get \begin{align} \mathbb{E}_\varnothing T_u &= \frac{1}{3} (4\cdot \mathbb{E}_u T_u - 2) = \frac{4\times 32 - 2}{3} = 42 \;. \end{align}

However, I hesitate to call this a solution using Kac's lemma, because the proof of Kac's lemma (the elementary version) is as simple, and uses the same kind of conditioning.

Infinite linear span vs closed linear span

2012-08-14T07:50:29Z

Hi,

Suppose we have a (real, separable) Banach space $V$ and a (linear) set $A\subseteq V$. I presume in general it might not be possible to write every element of the closed span of $A$ as an infinite linear combination $\sum_{i=1}^\infty\beta_i a_i$ of elements of $A$. Are there simple (non-trivial) conditions guaranteeing that the closed linear span of $A$ coincides with its infinite linear span (perhaps with unconditional/absolute convergence)?

My example of interest is the following: Let $X$ be a compact metric space and $F:X\to X$ a continuous map. My space $V$ is the space $C(X)$ of continuous (real-valued) functions on $X$, and $A$ is the subset of functions that can be written as $\varphi\circ F - \varphi$ for some $\varphi\in C(X)$.

Thank you for any help.

Answer by Algernon for If you were to axiomatize the notion of entropy .....

2012-07-19T11:48:43Z

The topological and measure-theoretic entropies of $(X,\varphi)$ formalize average entropy per iteration of partial observations ($\equiv$ the coarse-graining that Vaughn mentions above). (I am not familiar with other notions of entropy for dynamical systems.) In either case, one first needs an elementary notion of entropy for the class of allowed observations that is independent of $\varphi$.

Chris Hillman has some (sadly) unpublished notes in which he gives an elegant axiomatization of entropy that encompasses many more examples such as the Hausdorff dimension or what he calls the Galois entropy.

Answer by Algernon for Mathematics of quasicrystals

2012-06-19T15:18:39Z

Here is a hard-to-find but worthy book from the point of view of statistical mechanics:

Jacek Miękisz, Quasicrystals - Microscopic models of nonperiodic structure, Louven University Press, 1993.

There has been some progress since the writing of the book, but the main question (the construction of a lattice-gas model with translation-invariant finite range interactions admitting a quasi-crystalline phase) remains open.

If you don't like statistical mechanics, there is enormous literature on aperiodic tilings. The book

B. Grunbaum, G. C. Shephard, Tilings and Patterns, W. H. Freeman and Co., 1986

has two chapters on aperiodic tilings. For a more up-to-date account, I would recommend the lecture notes of Jarkko Kari.

If you tell us more specifically, which aspect of it you would like to study, maybe we could help better.

Answer by Algernon for Stone-Weierstrass for monotone functions

2012-05-04T20:33:40Z

In fact, the Bernstein polynomials approximating $f$ are non-decreasing on $[0,1]$. A cute way to see this is via coupling (I learned this from Lindvall's book Lectures on the Coupling Method):

The $n$th Bernstein polynomial $p_n(x)$ can be written as $\mathbf{E}\Big[f\big(\frac{\sum_{i=1}^n Z^x_i}{n}\big)\Big]$, where $Z^x_i$ are Bernoulli random variables with parameter $x$. If $0\leq x\leq y\leq 1$, then we can define the variables $Z^x_i$ and $Z^y_i$ on the same probability space, such that $Z^x_i\leq Z^y_i$, which immediately gives $p_n(x)\leq p_n(y)$.

Comment by Algernon

2013-05-18T13:46:34Z

Not quite sure if I get it. Are you assuming that the question has a solution for the given x?

Comment by Algernon

2013-05-17T16:39:04Z

... and you are of course right about the name of the wise fellow. I often make a point of not mentioning the names when quoting wise men, as big names have a tendency to bias our personal opinions.

Comment by Algernon

2013-05-17T16:38:32Z

@Amir: Absolutely. I just mentioned the quote as a funny reflection on how we understand things. I don't even completely agree with it myself. Human mind works with making associations, and it is the network of associations that we call understanding. We do get used to things, but in a highly selective fashion, highlighting the relevant connections and forgetting the rest.

Comment by Algernon

2013-05-17T07:51:50Z

"In mathematics you don't understand things. You just get used to them." -- some wise fellow

Comment by Algernon

2013-04-25T23:24:22Z

@Misha: Thanks for the comment. I updated my answer to elaborate the connection to OP's question. I also added reference to the relevant part in Arnold's article.

Comment by Algernon

2013-03-20T13:01:55Z

What is the meaning of the condition $B_i=s$ if $B_i$ is Boolean?

Comment by Algernon

2012-09-06T06:39:44Z

@Allan: But Knuth himself punctuates displayed formulas in his books.

Comment by Algernon

2012-08-14T13:57:27Z

The question was under what reasonable conditions $A_u$ or $A_a$ is the same as the closure of the linear span of $A$. But in case $A$ is a linear subspace itself (which was my primary interest), the answer is trivial as Wolfgang pointed out. Thanks for your time.

Comment by Algernon

2012-08-14T13:51:51Z

Oh well... You are right. What was I thinking! I ill-posed my problem, but your answer made things clearer in my mind. Thank you very much.

Comment by Algernon

2012-08-01T20:11:54Z

Right, so he/she accepts only ``computable'' functions as input.

Comment by Algernon

2012-08-01T08:20:28Z

I am afraid this does not make much sense. With your argument, you could also claim that whether a Boolean function $f:\lbrace 0,1\rbrace\to\lbrace 0,1\rbrace$ has a $0$ is undecidable. Indeed, you could consider the function $f(z)=\bigwedge_{j\in A}z$, where $A$ is a subset of $\mathbb{N}$. Then, $f$ has a zero if and only if $A$ is non-empty.

Comment by Algernon

2012-07-27T14:34:22Z

Do you consider random graphs, percolation theory, etc. as parts of probability theory?

Comment by Algernon

2012-07-10T18:41:59Z

@Simon: The real advantage of the Lebesgue integral is that it is meaningful for functions over other spaces than the Euclidean space, say, the symbolic space $\lbrace 0,1\rbrace^\mathbb{Z}$.