## Tag Archives: Robinson

### Some simple dynamical systems

Dynamical formulation of Prisoner’s dilemma
Originally, consider the two players, each has a set of stratagies, say $\mathcal{A}=\{a_{i}\}$ and $\mathcal{B}=\{b_{j}\}$. The pay-off $P_k=P_k(a_{i},b_{j})$ for player $k$ depends on the choices of both players.

Now consider two dynamical systems $(M_i,f_i)$. The set of stratagies consists of the invariant probability measures, and the pay-off functions can be

$\phi_k(\mu_1,\mu_2)=\int \Phi_k(x,y)d\mu_1 d\mu_2$, where $\mu_i\in\mathcal{M}(f_i)$;

$\psi_k(\mu_1,\mu_2)=\int \Phi_k(x,y)d\mu_1 d\mu_2-h(f_i,\mu_i)$.

The frist one is related to Ergodic optimization. The second one does sound better, since one may want to avoid a complicated (measured by its entropy) stratagy that has the same $\phi$ pay-off.

Gambler’s Ruin Problem
A gambler starts with an initial fortune of $i, and then either wins$1 (with $p$) or loses \$1 (with $q=1-p$) on each successive gamble (independent of the past). Let $S_n$ denote the total fortune after the n-th gamble. Given $N>i$, the gambler stops either when $S_n=0$ (broke), or $S_n=N$ (win), whichever happens first.

Let $\tau$ be the stopping time and $P_i(N)=P(S_\tau=N)$ be the probability that the gambler wins. It is easy to see that $P_0(N)=0$ and $P_N(N)=1$. We need to figure out $P_i(N)$ for all $i=1,\cdots,N-1$.

Let $S_0=i$, and $S_n=S_{n-1}+X_n$. There are two cases according to $X_1$:

$X_1=1$ (prob $p$): win eventually with prob $P_{i+1}(N)$;

$X_1=-1$ (prob $q$): win eventually with prob $P_{i-1}(N)$.

So $P_i(N)=p\cdot P_{i+1}(N)+q\cdot P_{i-1}(N)$, or equivalently,
$p\cdot (P_{i+1}(N)-P_i(N))=q\cdot (P_i(N)-P_{i-1}(N))$ (since $p+q=1$), $i=1,\cdots,N-1$.

Recall that $P_0(N)=0$ and $P_N(N)=1$. Therefore $P_{i+1}(N)-P_i(N)=\frac{q^i}{p^i}(P_1(N)-P_{0}(N))=\frac{q^i}{p^i}P_1(N)$, $i=1,\cdots,N-1$. Summing over $i$, we get $1-P_1(N)=P_1(N)\cdot\sum_{1}^{N-1}\frac{q^i}{p^i}$, $P_1(N)=\frac{1}{\sum_{0}^{N-1}\frac{q^i}{p^i}}=\frac{1-q/p}{1-q^N/p^N}$ (if $p\neq .5$) and $P_1(N)=\frac{1}{N}$ (if $p= .5$). Generally $P_i(N)=P_1(N)\cdots\sum_{0}^{i-1}\frac{q^j}{p^j}=\frac{1-q^i/p^i}{1-q^N/p^N}$ (if $p\neq .5$) and $P_1(N)=\frac{i}{N}$ (if $p= .5$).

Observe that for fixed $i$, the limit $P_i(\infty)=1-q^i/p^i>0$ only when $p>.5$, and $P_i(\infty)=0$ whenever $p\le .5$.

Finite Blaschke products
Let $f$ be an analytic function on the unit disc $\mathbb{D}=\{z\in\mathbb{C}: |z|<1 \}$ with a continuous extension to $\overline{\mathbb{D}}$ with $f(S^1)\subset S^1$. Then $f$ is of the form

$\displaystyle f(z)=\zeta\cdot\prod_{i=1}^n\left({{z-a_i}\over {1-\bar{a_i}z}}\right)^{m_i}$,

where $\zeta\in S^1$, and $m_i$ is the multiplicity of the zero $a_i\in \mathbb{D}$ of $f$. Such $f$ is called a finite Blaschke product.

Proposition. Let $f$ be a finite Blaschke product. Then the restriction $f:S^1\to S^1$ is measure-preserving if and only if $f(0)=0$. That is, $a_i=0$ for some $i$.

Proof. Let $\phi$ be an analytic function on $\overline{\mathbb{D}}$. Then $\int_{S_1}\phi d(\theta)=\phi(0)$ and $\int_{S_1}\phi\circ f d(\theta)=\phi\circ f(0)$.

Significance: there are a lot of measure-preserving covering maps on $S^1$.

Kalikov’s Random Walk Random Scenery
Let $X=\{1,-1\}^{\mathbb{Z}}$, and $\sigma:X\to X$ to the shift $\sigma((x_n))=(x_{n+1})$. More generally, let $A$ be a finite alphabet and $p$ be probability vector on $A$, and $Y=A^{\mathbb{Z}}$, $\nu=p^{\times\mathbb{Z}}$. Consider the skew-product $T:X\times Y\to X\times Y$, $(x,y)\mapsto (\sigma x, \sigma^{x_0}y)$. It is clear that $T$ preserves any $\mu\times \nu$, where $\mu$ is $\sigma$-invariant.

Proposition. Let $\mu=(.5,.5)^{\times\mathbb{Z}}$. Then $h(T,\mu\times \nu)=h(\sigma,\mu)=\log 2$ for all $(A,p)$.

Proof. Note that $T^n(x,y)\mapsto (\sigma^n x, \sigma^{x_0+\cdot+x_{n-1}}y)$. CLT tells that $\mu(x:|x_0+\cdot+x_{n-1}|\ge\kappa\cdot \sqrt{n})< \delta(\kappa)$ as $n\to\infty$, where $\delta(\kappa)\to 0$ as $\kappa\to\infty$. There are only $2^{n+\kappa \sqrt{n}}$ different $n$-strings (up to an error).

Significance: this gives a natural family of examples that are K, but not isomorphic to Bernoulli.

Creation of one sink. 1D case. Consider the family $f_t:x\mapsto x^2+2-t$, where $0\le t\le 2$. Let $t_\ast$ the first parameter such that the graph is tangent to the diagonal at $x_\ast=f_{t_\ast}(x_\ast)$. Note that $x_\ast$ is parabolic. Then for $t\in(t_\ast,t_\ast+\epsilon)$, $f_t(x)=x$ has two solutions $x_1(t), where $x_1(t)$ is a sink, and $x_2(t)$ is a source.

2D case. Let $B=[-1,1]\times[-\epsilon,\epsilon]$ be a rectangle, $f$ be a diffeomorphism such that $f(B)$ is a horseshoe lying  above $B$ of shape ‘V’. Moreover we assume $|\det Df|<1$. Let $f_t(x,y)=f(x,y)-(0,t)$ such that $f_1(B)$ is the regular horseshoe intersection:  V . Clearly there exists a fixed point $p_1$ of $f_1$ in $B$. We assume $\lambda_1(1)<-1<\lambda_2(1)<0$. Then Robinson proved that $f_t$ admits a fixed point in $B$ which is a sink.

First note that for any $t$, and any fixed point of $f_t$ (if exists), it is not on the boundary of $B$. Since $p_1$ is a nondegenerate fixed point of $f_1$, the fixed point continues to exist for some open interval $(t_1,1)$ (assume it is maximal, and denote the fixed point by $p_t$). Clearly $t_1>0$. Note that $p_{t_1}$ is also fixed by $f_{t_1}$, since it is a closed property. If there is some moment with $\lambda_1(t)=\lambda_2(t)$ for the fixed point $p_t$ of $f_t$, then it is already a sink, since $\det Df=\lambda_1\cdot\lambda_2<1$. So in the following we consider the case $\lambda_1\neq\lambda_2$ for all $p_t$, $t\in[t_1,1]$. Then the continuous dependence of parameters implies that both are continuous functions of $t$. The fixed point $p_{t_1}$ must be degenerate, since the fixed point ceases to exist beyond $t_1$, which means: $\lambda_i(t_1)=1$ for some $i\in\{1,2\}$.

Case 1. $\lambda_1(t_1)=1$. Note that $\lambda_1(1)<-1$. So $\text{Re}\lambda_1(t_\ast)=0$ for some $t_\ast\in(t_1,1)$, which implies that $\lambda_1(t_\ast)=ai$ for some $a\neq 0$. In particular, $\lambda_2(t_\ast)=-ai$, and $a^2=|\det Df|<1$. So $p_{t_\ast}$ is a (complex) sink.

Case 2. $\lambda_2(t_1)=1$. Note that $\lambda_2(1)<0$. Similarly $\text{Re}\lambda_2(t_\ast)=0$ for some $t_\ast\in(t_1,1)$.

So in the orientation-preserving case there always exists a complex sink. In the orientation-reversing case ($\lambda_2(1)\in(0,1)$), we need modify the argument for case 2:

Case 2′. $\lambda_2(t_1)=1$. Note that $\lambda_2(1)\in(0,1)$. So $|\lambda_1(t_\ast)|<1$ for some $t_\ast\in(t_1,1)$. We pick $t_\ast$ close to $t_1$ in the sense that $|\lambda_1(t_\ast)|>|\det Df|$, which implies $|\lambda_1(t_\ast)|\ast<1$, too. So $p_{t_\ast}$ is also a sink.