# Somewhere else, part 108

Some writings worth reading,

and “Global Traffic Map” http://telegeography.com/ … via @Geopolitics2020 see also http://wired.com/politics/security/… and

and “Sex Ratio in Europe” from http://appsso.eurostat.ec.europa.eu/nui/… via http://joyofdata.de/blog/… see

et un peu de lecture en français,

Did I miss something?

# Sequences defined using a Linear Recurrence

In the introduction to the time series course (MAT8181) this morning, we did spend some time on the expression of (deterministic) sequences defined using a linear recurence (we will need that later on, so I wanted to make sure that those results were familiar to everyone).

• First order recurence

The most simple case is the first order recurence, $u_n=a+b u_{n-1}$ where $b\neq 1$ (for convenience). Observe that we can remove the constant, using a simple translation $\underbrace{[u_n-m]}_{v_n} = b \underbrace{[u_{n-1}-m]}_{v_{n-1}}$ if $m=a/(1-b)$. So, starting from this point, we will always remove the constant in the recurent equation. Thus, ${v_n} = b{v_{n-1}}$. From this equation, observe that ${v_n} = b^n{v_{0}}$, which is the general expression of ${v_n}$.

• Second order recurence

Consider now a second order recurence, ${v_n} = a{v_{n-1}}+b{v_{n-2}}$. In order to find the general expression of ${v_n}$, define $\boldsymbol{V}_n =(v_{n}},{v_{n-1}})^{\sffamily T}$. Then $\underbrace{\begin{bmatrix}v_n\\v_{n-1} \end{bmatrix} }_{\boldsymbol{V}_n }= \underbrace{\begin{bmatrix}a& b \\ 1 & 0\end{bmatrix}}_B\underbrace{\begin{bmatrix}v_{n-1} \\v_{n-2} \end{bmatrix} }_{\boldsymbol{V}_{n-1} }$ This time, we have a vectorial linear recurent equation. But what we’ve done previously still holds. For instance, ${\boldsymbol{V}_n }=B{\boldsymbol{V}_{n-1} }=\cdots=B^n\boldsymbol{V}_{0}$ What could we say about $B^n$ ? If $B$ can be diagonalized, then $B=P\Delta P^{-1}$ and $B^n=P\Delta^n P^{-1}$. Thus, $\underbrace{\begin{bmatrix}v_n\\v_{n-1} \end{bmatrix} }_{\boldsymbol{V}_n }= B^n \underbrace{\begin{bmatrix}v_{0} \\v_{-1} \end{bmatrix} }_{\boldsymbol{V}_{0} }= P\underbrace{\begin{bmatrix}\lambda_1^n& 0 \\ 0 & \lambda_2^n\end{bmatrix}}_{\Delta^n} P^{-1}\underbrace{\begin{bmatrix}v_{0} \\v_{-1} \end{bmatrix} }_{\boldsymbol{V}_{0} }$ so what we’ll get here is something like$v_n = \alpha \lambda_1^n +\beta\lambda_2^n$ for some constant $\alpha$ and $\beta$. Recall that $\lambda_1$ and $\lambda_2$ are the eigenvalues of matrix $B$, and they are also the roots of the characteristic polynomial $P(x)=x^2 - ax - b$. Since $a$ and $b$ are real-valued, there are two roots for the polynomial, possibly identical, possibly complex (but then conjugate). An interesting case is obtained when the roots are $re^{\pm i\theta}$. In that case $v_n =r^n(\alpha\cos(n\theta) + \beta\sin(n\theta))$ To visualize this general term, consider the following code. A first strategy is to define the sequence, given the two parameters, and two starting values. E.g.

> a=.5
> b=-.9
> u1=1; u0=1

Then, we iterate to generate the sequence,

> v=c(u1,u0)
> while(length(v)<100) v=c(a*v[1]+b*v[2],v)
> plot(0:99,rev(v))

It is also possible to use the generic expression we’ve just seen. Here, the roots of the characteristic polynomial are

> r=polyroot(c(-b, -a, 1))
> r
[1] 0.25+0.9151503i 0.25-0.9151503i
> plot(r,xlim=c(-1.1,1.1),ylim=c(-1.1,1.1),pch=19,col="red")
> u=seq(-1,1,by=.01)
> lines(u,sqrt(1-u^2),lty=2)
> lines(u,-sqrt(1-u^2),lty=2)

Since, $v_n = \alpha \lambda_1^n +\beta\lambda_2^n$, then $\begin{cases} \alpha + \beta = v_0 \\ \alpha r_1 + \beta r_2 = v_1 \end{cases}$ it is possible to derive numerical expressions for the two parameters. If $v_n =r^n(A\cos(n\theta) + B\sin(n\theta))$, then $A=\lambda+\mu$ while $B=i(\lambda-\mu)$. Thus,

> A=sum(solve(matrix(c(1,r[1],1,r[2]),2,2),c(u0,u1)))
> B=diff(solve(matrix(c(1,r[1],1,r[2]),2,2),c(u0,u1)))* complex(real=0,imaginary=1)

We can plot the sequence of points

> plot(0:99,rev(v))

and then we can also plot the sine wave, too

> t=seq(0,100,by=.1)
> bv=function(t) Mod(r)[1]^t
> fv=function(t) Mod(r)[1]^t*(A*cos(t*Arg(r)[1])+B*sin(t*Arg(r)[1]))
> lines(t,Vectorize(bv)(t-1),col="red",lty=2)
> lines(t,-Vectorize(bv)(t-1),col="red",lty=2)
> lines(t,Vectorize(fv)(t-1),col="blue")

We will see a lot of graph like this in the course, when looking at autocorrelation functions.

• Higher order recurence

More generally, we can write $\underbrace{\begin{bmatrix}v_n\\v_{n-1}\\v_{n-2}\\ \vdots \\ v_{n-p+1} \end{bmatrix} }_{\boldsymbol{V}_n }= \underbrace{\begin{bmatrix}b_{1} & b_{2} &b_3& \cdots & b_{p} \\ 1 & 0 & 0& \cdots &0\\ 0 & 1 & 0& \cdots &0\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0& \cdots & 0\end{bmatrix}}_B\underbrace{\begin{bmatrix}v_{n-1} \\v_{n-2}\\v_{n-3} \\ \vdots \\ v_{n-p} \end{bmatrix} }_{\boldsymbol{V}_{n-1} }$ The matrix is a so called companion matrix. And similar results could be obtained for the expression of the general term of the sequence. If all that is not familar, I strongly recommand to read carefully a textbook on sequences and linear recurence.

# Central Limit Theorem

This week, in the MAT8595 course, before proving Fisher-Tippett theorem, we will get back on the proof of the Central Limit Theorem, and the class of stable distribution (in Lévy’s sense). In order to illustrate the problem of heavy tails, on the behavior of the mean, consider a sequence of i.i.d. Gaussian random variables $X_i$‘s. On top, we visualize the sequence, and below, we visualize the associate random walk

$S_n=\sum_{i=1}^n X_i$

(the central limit theorem will give a limiting distribution for $n^{-1}S_n$ in the case where the variance of the $X_i$‘s is finite)

If we consider a sequence of i.i.d. random variables $X_i$‘s whith heavier tails (possibly with infinite variance), we can still define $S_n$, but as we can see below, $S_n$ can be quite heratic.

As we will see this Thursday, the key to derive stable distribution for the central limit theorem, or possible limiting distributions for the maximum is Cauchy’s function equation. I strongly recommand to look at the proof.