http://www.geeksforgeeks.org/lowest-common-ancestor-binary-tree-set-1/

# A good explanation of mean field game

# Reproducing Kernel Hilbert Space

Since writing about the simulation of fractional Brownian motion, I’ll spend an hour to write RKHS.

**Definition**: A Hilbert space is a RKHS if

**Theorem**: If is a RKHS, then for each there exists a function (called the representer of ) with the reproducing property

Therefore, .

**Definition**: is a reproducing kernel if it’s symmetric and positive definite.

**Theorem**: A RKHS defines a corresponding reproducing kernel. Conversely, a reproducing kernel defines a unique RKHS.

Once we have the kernels, if ,

then

When it comes to the fractional Brownian motion

**Theorem**: For fBm RKHS is symmetric and positive definite, , there exists s.t

Take Wiener integral as an example:

where ,

and

For example, when , , we can check

**Claim**: By previous theorem, the reproducing kernel uniquely defines a RKHS with the inner product

# how to simulate a fractional Brownian motion?

A fractional Brownian motion is a Gaussian process satisfying

a)

b) is Gaussian

c)

As for simulation, we just need to simulate the correlated Gaussian , where

,

,

Now the question is just simulating where is the Cholesky decomposition of , i.e ()

Method 1: find first and then use Cholesky decomposition to compute . This works theoretically, but not practically because it’s too time and space costy to record , not to mention decomposition step.

Method 2:

We denote

Denote a circulant matrix

of which is the left up block matrix.

**The idea is**, suppose where , now if we generate ,

We can conclude that

denote , then and

let Q is the unitary matrix defined by

and thus

so how to achieve ? The property of circulant matrix shows that

, i.e

that can be achieved by FFT.

Next, according to the idea stated before,

And the first n component of will be

Reference : Coeurjolly, JF. Simulation and identification of the fractional Brownian motion

Matlab code:

function []=fBM(n,H)

r=nan(n+1,1); r(1) = 1;

for k=1:n

r(k+1) = 0.5*((k+1)^(2*H) – 2*k^(2*H) + (k-1)^(2*H));

end

r=[r; r(end-1:-1:2)]; % first rwo of circulant matrix

lambda=real(fft(r))/(2*n); % eigenvalues

W=fft(sqrt(lambda).*complex(randn(2*n,1),randn(2*n,1)));

W = n^(-H)*cumsum(real(W(1:n+1))); % rescale

plot((0:n)/n,W);

%Terminal=W(n+1);%terminal value of fBM

end

# Somewhere