Brownian Motion 模拟
布朗运动又被称为Wienner过程。
标准布朗运动的数学性质
设连续时间随机过程\(B_t:0\leq t\leq T\)是\([0,T)\)上的标准布朗运动,
\(B_0=0\)
独立增量性:对于有限个时刻\(0\leq t_1< t_2<\dots<t_n\leq T,\)随机变量 \[
B_{t_2}-B_{t_1},B_{t_3}-B_{t_2},\dots,B_{t_n}-B_{t_{n-1}}
\] 是独立的。
正态性:对任意的\(0\leq s<t<T,B_t-B_s\sim N(0,t-s)\).
设\(B_0=0.\)对\(j=1,2,...,N,\)做以下几步
- \(t_j=t_{j-1}+\Delta t\)
- 产生\(Z_j\sim N(0,1)\)
- \(\Delta B_j=Z_j\sqrt{\Delta t}\)
- \(B_j=B_{j-1}+\Delta B_j\)
set.seed(123)
N <- 100 # 时间[0,T]分割的份数
T <- 1
Delta <- T/N # 时间间隔
B <- numeric(N+1) #初始化0向量
t <- seq(0,T,length=N+1)
for(i in 2:(N+1))
B[i] <- B[i-1]+rnorm(1)*sqrt(Delta)
plot(t,B,type="l", main="Brownian Motion",ylim = c(-1,1))

假设\(\{X_t,0\leq t\leq T\}\)是关于布朗运动生成的事件流适应的随机过程,满足\(\int_{0}^T\mathbb{E}(X_s^2)ds<+\infty.\)则\(X\)的\(It\hat{o}\)积分定义为: \[
I_t(X)=\int_{0}^TX_sdB_s=\lim_{||\Pi_n||\rightarrow 0}\sum_{i=0}^{n-1} X_{t_i}(B_{t_{i+1}}-B_{t_i})
\] 例如: \[
\begin{align}
\int_{t_0}^{t_1}dB_s & =\lim_{n\rightarrow \infty}\sum_{i=0}^{n-1}(B_{t_{i+1}}-B_{t_i})\\
& = B_t-B_{t_0}
\end{align}
\]
随机过程\(\{X_t,0\leq t\leq T\}\)可以写成如下形式: \[
X_t=X_0+\int_0^t u(s)ds+\int_{0}^tv(s)dB_s
\] 其中\(u(t,\omega),v(s,\omega)\)是两个适应过程,且满足 \[
\mathbb{P}\{\int_{0}^T|u(t,\omega)|dt<\infty\}=1\quad and\quad \mathbb{P}\{\int_{0}^Tv^2(t,\omega)dt<\infty\}=1
\] 则\(\{X_t,0\leq t\leq T\}\)被称为\(It\hat{o}\)过程。
随机微分方程(以下简称SDE)
\[
X_t=X_0+\int_{0}^t \mu(s,X_s)ds+\int_{0}^t\sigma(s,X_s)dB_s
\] 通常写成微分形式 \[
dX_t = \mu(t,X_t)dt+\sigma(t,X_t)dB_t
\] 其中\(\mu(\cdot)\)被称作漂移项,\(\sigma(\cdot)\)被称作扩散项。
下面介绍几个SDE
布朗运动: \[
dX_t=\mu dt+\sigma dB_t
\] 几何布朗运动: $$
dX_t = X_t dt+X_tdB_t $$ ## SDE的解 如果SDE的漂移项和扩散项满足下面的条件
- 全局Lipschitz条件:对于所有的\(x,y\in \mathbf{R},t\in[0,T],\)存在常数\(K<\infty\)使得 \[
|\mu(t,x)-\mu(t,y)|+|\sigma(t,x)-\sigma(t,y)|<K|x-y|
\]
- 线性增长条件:对于所有的\(x\in\mathbf{R},t\in [0,T],\)存在常数\(C<\infty\)使得 \[
|\mu(t,x)|+|\sigma(t,x)|<C(1+|x|)
\]
则SDE存在唯一的连续的强解使得 \[
\mathbb{E}\{\int_0^T |X_t|^2dt\}<\infty.
\]
布朗运动
\[
dX_t = \mu dt+\sigma dB_t
\] 在给定初值\(X_{t_0}\)的条件下,可以求出方程的解为 \[
X_t=X_0+\mu(t-t_0)+\sigma(B_t-B_{t_0})
\] ### 几何布朗运动
$$
dX_t = X_t dt+X_tdB_t \[
在给定初值$X_{t_0}$的条件下,可以求出方程的解:
\] \[\begin{align}
X_t &= X_{t_0}\exp\{(\mu-\frac{1}{2}\sigma^2)(t-t_0)+\sigma(B_t-B_{t_0}) \}
\end{align}\] $$
\(It\hat{o}\)引理
假设\(X_t\)满足SDE: \[
dX_t=\mu(t,X_t)dt+\sigma(t,X_t)dB_t.
\] \(f(X)\)是\(X\)的函数,则 \[
df(X)=f_X(X)dX+\frac{1}{2}f_{XX}(dX)^2
\] \((dX)^2\)展开时,有如下法则:
\[
dt\times dt=dt\times dB_t=dB_t\times dt=0;dB_t\times dB_t=dt.
\] ## \(It\hat{o}\)引理的应用
假设\(X_t\)满足SDE:
\[
dX_t=\mu X_tdt+\sigma X_tdB_t
\] 如何解\(X_t?\)
设\(Y_t = \ln X_t,\frac{\partial Y_t}{\partial X_t} = \frac{1}{X_t},\frac{\partial^2 Y_t}{\partial (X_t)^2}=-\frac{1}{X_t^2},\)由\(|t\hat{o}\)引理知: \[
\begin{align}
dY_t&=\frac{\partial Y_t}{\partial X_t}dX_t +\frac{1}{2}\frac{\partial^2 Y_t}{\partial X_t^2}(dX_t)^2\\
&=\frac{1}{X_t}(\mu X_tdt+\sigma X_tdB_t)+\frac{1}{2}(-\frac{1}{X_t^2})\sigma^2X_t^2dt\\
&=\mu dt+\sigma dB_t-\frac{1}{2}\sigma^2dt\\
&=(\mu-\frac{1}{2}\sigma^2)dt+\sigma dB_t
\end{align}
\] 于是可以看出\(Y_t\)是布朗运动,这是因为它服从布朗运动的随机微分方程。
我们选择的\(Y_t\)看似是比较有技巧的,选取的原则是由于\(dX_t\)表达式中有\(X_t\)的一次项,所以我们选择的对\(Y_t\)求导可以消掉一次项。
\(Y_t\)服从布朗运动,于是有 \[
\begin{align}
Y_t&=Y_{t_0}+\Big(\mu-\frac{1}{2}\sigma^2\Big)(t-t_0)+\sigma(B_{t}-B_{t_0})\\
X_t&=\exp(Y_t)\\
&=X_{t_0}\exp\Big[\Big(\mu-\frac{1}{2}\sigma^2\Big)(t-t_0)+\sigma(B_{t}-B_{t_0})\Big]
\end{align}
\]
几何布朗运动的模拟
设定初始值为\(X_0\), 对\(j=1,2,...,N,\)做以下几步
- \(t_j=t_{j-1}+\Delta t\)
- 产生\(Z_j\sim N(0,1)\)
- \(\Delta B_j=Z_j\sqrt{\Delta t}\)
- \(X_j=X_{j-1}\exp\Big((\mu-\frac{1}{2}\sigma^2)\Delta t+\sigma \Delta B_j\Big)\)
set.seed(111)
mu <- 1
sigma <- 0.5
x <- 10
N <- 100
Delta <- T/N #时间间隔
B <- numeric(N+1) #初始化向量 这里的t_0=0,B_{t_0}=0
t <- seq(0,T,length = N+1)
for(i in 2:(N+1))
B[i] <- B[i-1]+rnorm(1)*sqrt(Delta)
S <- x*exp((mu-sigma^2/2)*t+sigma*B)
plot(t,S,type="l",main="几何布朗运动")

并不是所有的SDE都能解出显式解,更多的SDE只能通过迭代求出数值解。求SDE数值解实际上也就是模拟出解的路径。
Euler格式
\[
Y_{i+1}=Y_i+\mu(t_i,Y_i)(t_{i+1}-t_i)+\sigma(t_i,Y_i)(B_{i+1}-B_i)
\] ### Milstein格式
\[
\begin{align}
Y_{i+1}&=Y_i+\mu(t_i,Y_i)(t_{i+1}-t_i)+\sigma(t_i,Y_i)(B_{i+1}-B_i)\\
&+\frac{1}{2}\sigma(t_i,Y_i)\sigma_x(t_i,Y_i)\{(B_{i+1}-B_i)^2-(t_{i+1}-t_i)\}
\end{align}
\] 其中\(B_{i+1}-B_i=\sqrt{t_{i+1}-t_i}Z_{i+1},\quad i=0,...,n-1.\)
SDE的参数估计
考虑下面的SDE: \[
dX_t=\mu(X_t;\theta)dt+\sigma(X_t,;\theta)dB_t
\] 其中\(\theta\in \Theta\subset \mathbf{R}^p\)是\(p\)维参数,\(\theta_0\)是参数的真实值。函数\(\mu:\mathbf{R}\times\Theta\rightarrow \mathbf{R}\)和\(\sigma:\mathbf{R}\times\Theta\rightarrow(0,+\infty)\)是已知的,并且使得SDE的解存在。如果我们观测到该SDE解的一条轨迹的离散采样\(\{X_n,n\in \mathbb{N}\},\)用这些数据来估计参数\(\theta,\)得到的参数的估计为\(\hat{\theta}\).
极大似然估计
假设\(x_0,...,x_N\)是\(X_t\)在均匀离散时刻\(t_i=\Delta t\)的观测,其中\(i=0,1,...,N,\Delta t=T/N.\)
令\(p(t_k,x_k|t_{k-1},x_{k-1};\theta)\)是从\((t_{k-1},x_{k-1})\)到\((t_k,x_k)\)的传递概率密度(条件密度?),假设初始状态的概率密度为\(p_0(x_0|\theta),\)则似然函数为:
\[
f(\theta)=p_0(x_0|\theta)\prod_{k=1}^Np(t_k,x_k|t_{k-1},x_{k-1};\theta).
\] 对数似然函数为:
\[
L(\theta)=\sum_{k=1}^N\ln p(t_k,x_k|t_{k-1},x_{k-1};\theta)+\ln p_0(x_0|\theta).
\] 对SDE的Euler近似,有
\[
X_{k}=X_{k-1}+\mu(t_{k-1},x_{k-1};\theta)\Delta t+\sigma(t_{k-1},x_{k-1};\theta)\sqrt{\Delta t}\eta_k.
\]
其中\(\eta_k\sim N(0,1).\)由上式可得,
\[
p(t_k,x_k|t_{k-1},x_{k-1};\theta)=\frac{1}{\sqrt{2\pi\sigma_k}}\exp\Big(-\frac{(x_k-\mu_k)^2}{2\sigma_k^2}\Big).
\] 其中\(\mu_k=x_{k-1}+\mu(t_{k-1},x_{k-1};\theta),\sigma_k=\sigma(t_{k-1},x_{k-1};\theta)\sqrt{\Delta t}\).
考虑美洲鹤1939–1985年的种群数据,假设\(t\)时刻种群大小\(X_t\)满足SDE:
\[
dX_t=\theta_1X_tdt+\theta_2\sqrt{X_t}dB_t,\quad X_0=18.
\]
LS0tDQp0aXRsZTogU3RvY2hhc3RpYyBQcm9ncmVzcw0Kb3V0cHV0OiBodG1sX25vdGVib29rDQotLS0NCg0KIyMgQnJvd25pYW4gTW90aW9uIOaooeaLnw0KDQrluIPmnJfov5Dliqjlj4jooqvnp7DkuLpXaWVubmVy6L+H56iL44CCDQoNCiMjIyDmoIflh4bluIPmnJfov5DliqjnmoTmlbDlrabmgKfotKggDQoNCuiuvui/nue7reaXtumXtOmaj+acuui/h+eoiyRCX3Q6MFxsZXEgdFxsZXEgVCTmmK8kWzAsVCkk5LiK55qE5qCH5YeG5biD5pyX6L+Q5Yqo77yMDQoNCi0gJEJfMD0wJA0KDQotIOeLrOeri+WinumHj+aAp++8muWvueS6juaciemZkOS4quaXtuWIuyQwXGxlcSB0XzE8IHRfMjxcZG90czx0X25cbGVxIFQsJOmaj+acuuWPmOmHjw0KJCQNCiAgQl97dF8yfS1CX3t0XzF9LEJfe3RfM30tQl97dF8yfSxcZG90cyxCX3t0X259LUJfe3Rfe24tMX19DQokJA0K5piv54us56uL55qE44CCDQoNCi0g5q2j5oCB5oCn77ya5a+55Lu75oSP55qEJDBcbGVxIHM8dDxULEJfdC1CX3Ncc2ltIE4oMCx0LXMpJC4NCg0K6K6+JEJfMD0wLiTlr7kkaj0xLDIsLi4uLE4sJOWBmuS7peS4i+WHoOatpQ0KDQotICR0X2o9dF97ai0xfStcRGVsdGEgdCQNCi0g5Lqn55SfJFpfalxzaW0gTigwLDEpJA0KLSAkXERlbHRhIEJfaj1aX2pcc3FydHtcRGVsdGEgdH0kDQotICRCX2o9Ql97ai0xfStcRGVsdGEgQl9qJA0KDQpgYGB7cn0NCnNldC5zZWVkKDEyMykNCk4gPC0gMTAwICMg5pe26Ze0WzAsVF3liIblibLnmoTku73mlbANClQgPC0gMQ0KRGVsdGEgPC0gVC9OICMg5pe26Ze06Ze06ZqUDQpCIDwtIG51bWVyaWMoTisxKSAj5Yid5aeL5YyWMOWQkemHjw0KdCA8LSBzZXEoMCxULGxlbmd0aD1OKzEpDQpmb3IoaSBpbiAyOihOKzEpKQ0KICBCW2ldIDwtIEJbaS0xXStybm9ybSgxKSpzcXJ0KERlbHRhKQ0KcGxvdCh0LEIsdHlwZT0ibCIsIG1haW49IkJyb3duaWFuIE1vdGlvbiIseWxpbSA9IGMoLTEsMSkpDQoNCmBgYA0KDQrlgYforr4kXHtYX3QsMFxsZXEgdFxsZXEgVFx9JOaYr+WFs+S6juW4g+acl+i/kOWKqOeUn+aIkOeahOS6i+S7tua1gemAguW6lOeahOmaj+acuui/h+eoi++8jOa7oei2syRcaW50X3swfV5UXG1hdGhiYntFfShYX3NeMilkczwrXGluZnR5LiTliJkkWCTnmoQkSXRcaGF0e299JOenr+WIhuWumuS5ieS4uu+8mg0KJCQNCklfdChYKT1caW50X3swfV5UWF9zZEJfcz1cbGltX3t8fFxQaV9ufHxccmlnaHRhcnJvdyAwfVxzdW1fe2k9MH1ee24tMX0gWF97dF9pfShCX3t0X3tpKzF9fS1CX3t0X2l9KQ0KJCQNCuS+i+Wmgu+8mg0KJCQNClxiZWdpbnthbGlnbn0NClxpbnRfe3RfMH1ee3RfMX1kQl9zICYgPVxsaW1fe25ccmlnaHRhcnJvdyBcaW5mdHl9XHN1bV97aT0wfV57bi0xfShCX3t0X3tpKzF9fS1CX3t0X2l9KVxcDQogJiA9IEJfdC1CX3t0XzB9DQogXGVuZHthbGlnbn0NCiQkDQoNCumaj+acuui/h+eoiyRce1hfdCwwXGxlcSB0XGxlcSBUXH0k5Y+v5Lul5YaZ5oiQ5aaC5LiL5b2i5byP77yaDQokJA0KICBYX3Q9WF8wK1xpbnRfMF50IHUocylkcytcaW50X3swfV50dihzKWRCX3MNCiQkDQrlhbbkuK0kdSh0LFxvbWVnYSksdihzLFxvbWVnYSkk5piv5Lik5Liq6YCC5bqU6L+H56iL77yM5LiU5ruh6LazDQokJA0KICBcbWF0aGJie1B9XHtcaW50X3swfV5UfHUodCxcb21lZ2EpfGR0PFxpbmZ0eVx9PTFccXVhZCBhbmRccXVhZCBcbWF0aGJie1B9XHtcaW50X3swfV5Udl4yKHQsXG9tZWdhKWR0PFxpbmZ0eVx9PTENCiQkDQrliJkkXHtYX3QsMFxsZXEgdFxsZXEgVFx9JOiiq+ensOS4uiRJdFxoYXR7b30k6L+H56iL44CCDQoNCiMjIOmaj+acuuW+ruWIhuaWueeoi++8iOS7peS4i+eugOensFNERe+8iQ0KJCQNCiAgWF90PVhfMCtcaW50X3swfV50IFxtdShzLFhfcylkcytcaW50X3swfV50XHNpZ21hKHMsWF9zKWRCX3MNCiQkDQrpgJrluLjlhpnmiJDlvq7liIblvaLlvI8NCiQkDQpkWF90ID0gXG11KHQsWF90KWR0K1xzaWdtYSh0LFhfdClkQl90DQokJA0K5YW25LitJFxtdShcY2RvdCkk6KKr56ew5L2c5ryC56e76aG577yMJFxzaWdtYShcY2RvdCkk6KKr56ew5L2c5omp5pWj6aG544CCDQoNCuS4i+mdouS7i+e7jeWHoOS4qlNERQ0KDQrluIPmnJfov5DliqjvvJoNCiQkDQogIGRYX3Q9XG11IGR0K1xzaWdtYSBkQl90DQokJA0K5Yeg5L2V5biD5pyX6L+Q5Yqo77yaDQokJA0KDQogIGRYX3QgPSBcbXUgWF90IGR0K1xzaWdtYSBYX3RkQl90DQokJA0KIyMgU0RF55qE6KejDQrlpoLmnpxTREXnmoTmvILnp7vpobnlkozmianmlaPpobnmu6HotrPkuIvpnaLnmoTmnaHku7YNCg0KLSDlhajlsYBMaXBzY2hpdHrmnaHku7bvvJrlr7nkuo7miYDmnInnmoQkeCx5XGluIFxtYXRoYmZ7Un0sdFxpblswLFRdLCTlrZjlnKjluLjmlbAkSzxcaW5mdHkk5L2/5b6XDQokJA0KfFxtdSh0LHgpLVxtdSh0LHkpfCt8XHNpZ21hKHQseCktXHNpZ21hKHQseSl8PEt8eC15fA0KJCQNCi0g57q/5oCn5aKe6ZW/5p2h5Lu277ya5a+55LqO5omA5pyJ55qEJHhcaW5cbWF0aGJme1J9LHRcaW4gWzAsVF0sJOWtmOWcqOW4uOaVsCRDPFxpbmZ0eSTkvb/lvpcNCiQkDQogIHxcbXUodCx4KXwrfFxzaWdtYSh0LHgpfDxDKDErfHh8KQ0KJCQNCg0K5YiZU0RF5a2Y5Zyo5ZSv5LiA55qE6L+e57ut55qE5by66Kej5L2/5b6XDQokJA0KXG1hdGhiYntFfVx7XGludF8wXlQgfFhfdHxeMmR0XH08XGluZnR5Lg0KJCQNCg0KIyMjIOW4g+acl+i/kOWKqA0KJCQNCmRYX3QgPSBcbXUgZHQrXHNpZ21hIGRCX3QNCiQkDQrlnKjnu5nlrprliJ3lgLwkWF97dF8wfSTnmoTmnaHku7bkuIvvvIzlj6/ku6XmsYLlh7rmlrnnqIvnmoTop6PkuLoNCiQkDQpYX3Q9WF8wK1xtdSh0LXRfMCkrXHNpZ21hKEJfdC1CX3t0XzB9KQ0KJCQNCiMjIyDlh6DkvZXluIPmnJfov5DliqgNCg0KJCQNCg0KICBkWF90ID0gXG11IFhfdCBkdCtcc2lnbWEgWF90ZEJfdA0KJCQNCuWcqOe7meWumuWIneWAvCRYX3t0XzB9JOeahOadoeS7tuS4i++8jOWPr+S7peaxguWHuuaWueeoi+eahOinozoNCiQkDQpcYmVnaW57YWxpZ259DQpYX3QgJj0gWF97dF8wfVxleHBceyhcbXUtXGZyYWN7MX17Mn1cc2lnbWFeMikodC10XzApK1xzaWdtYShCX3QtQl97dF8wfSkgIFx9DQpcZW5ke2FsaWdufQ0KJCQNCg0KIyMgJEl0XGhhdHtvfSTlvJXnkIYNCuWBh+iuviRYX3Qk5ruh6LazU0RFOg0KJCQNCmRYX3Q9XG11KHQsWF90KWR0K1xzaWdtYSh0LFhfdClkQl90Lg0KJCQNCiRmKFgpJOaYryRYJOeahOWHveaVsO+8jOWImQ0KJCQNCmRmKFgpPWZfWChYKWRYK1xmcmFjezF9ezJ9Zl97WFh9KGRYKV4yDQokJA0KJChkWCleMiTlsZXlvIDml7bvvIzmnInlpoLkuIvms5XliJnvvJoNCg0KJCQNCmR0XHRpbWVzIGR0PWR0XHRpbWVzIGRCX3Q9ZEJfdFx0aW1lcyBkdD0wO2RCX3RcdGltZXMgZEJfdD1kdC4NCiQkDQojIyAkSXRcaGF0e299JOW8leeQhueahOW6lOeUqA0KDQrlgYforr4kWF90JOa7oei2s1NERToNCg0KJCQNCmRYX3Q9XG11IFhfdGR0K1xzaWdtYSBYX3RkQl90DQokJA0K5aaC5L2V6KejJFhfdD8kDQoNCuiuviRZX3QgPSBcbG4gWF90LFxmcmFje1xwYXJ0aWFsIFlfdH17XHBhcnRpYWwgWF90fSA9IFxmcmFjezF9e1hfdH0sXGZyYWN7XHBhcnRpYWxeMiBZX3R9e1xwYXJ0aWFsIChYX3QpXjJ9PS1cZnJhY3sxfXtYX3ReMn0sJOeUsSR8dFxoYXR7b30k5byV55CG55+l77yaDQokJA0KXGJlZ2lue2FsaWdufQ0KZFlfdCY9XGZyYWN7XHBhcnRpYWwgWV90fXtccGFydGlhbCBYX3R9ZFhfdCArXGZyYWN7MX17Mn1cZnJhY3tccGFydGlhbF4yIFlfdH17XHBhcnRpYWwgWF90XjJ9KGRYX3QpXjJcXA0KJj1cZnJhY3sxfXtYX3R9KFxtdSBYX3RkdCtcc2lnbWEgWF90ZEJfdCkrXGZyYWN7MX17Mn0oLVxmcmFjezF9e1hfdF4yfSlcc2lnbWFeMlhfdF4yZHRcXA0KJj1cbXUgZHQrXHNpZ21hIGRCX3QtXGZyYWN7MX17Mn1cc2lnbWFeMmR0XFwNCiY9KFxtdS1cZnJhY3sxfXsyfVxzaWdtYV4yKWR0K1xzaWdtYSBkQl90DQpcZW5ke2FsaWdufQ0KJCQNCuS6juaYr+WPr+S7peeci+WHuiRZX3Qk5piv5biD5pyX6L+Q5Yqo77yM6L+Z5piv5Zug5Li65a6D5pyN5LuO5biD5pyX6L+Q5Yqo55qE6ZqP5py65b6u5YiG5pa556iL44CCDQoNCuaIkeS7rOmAieaLqeeahCRZX3Qk55yL5Ly85piv5q+U6L6D5pyJ5oqA5ben55qELOmAieWPlueahOWOn+WImeaYr+eUseS6jiRkWF90JOihqOi+vuW8j+S4reaciSRYX3Qk55qE5LiA5qyh6aG577yM5omA5Lul5oiR5Lus6YCJ5oup55qE5a+5JFlfdCTmsYLlr7zlj6/ku6XmtojmjonkuIDmrKHpobnjgIINCg0KJFlfdCTmnI3ku47luIPmnJfov5DliqjvvIzkuo7mmK/mnIkNCiQkDQogIFxiZWdpbnthbGlnbn0NCiAgWV90Jj1ZX3t0XzB9K1xCaWcoXG11LVxmcmFjezF9ezJ9XHNpZ21hXjJcQmlnKSh0LXRfMCkrXHNpZ21hKEJfe3R9LUJfe3RfMH0pXFwNCiAgWF90Jj1cZXhwKFlfdClcXA0KICAmPVhfe3RfMH1cZXhwXEJpZ1tcQmlnKFxtdS1cZnJhY3sxfXsyfVxzaWdtYV4yXEJpZykodC10XzApK1xzaWdtYShCX3t0fS1CX3t0XzB9KVxCaWddDQogIFxlbmR7YWxpZ259DQokJA0KDQojIyMg5Yeg5L2V5biD5pyX6L+Q5Yqo55qE5qih5oufDQoNCuiuvuWumuWIneWni+WAvOS4uiRYXzAkLCDlr7kkaj0xLDIsLi4uLE4sJOWBmuS7peS4i+WHoOatpQ0KDQotICR0X2o9dF97ai0xfStcRGVsdGEgdCQNCi0g5Lqn55SfJFpfalxzaW0gTigwLDEpJA0KLSAkXERlbHRhIEJfaj1aX2pcc3FydHtcRGVsdGEgdH0kDQotICRYX2o9WF97ai0xfVxleHBcQmlnKChcbXUtXGZyYWN7MX17Mn1cc2lnbWFeMilcRGVsdGEgdCtcc2lnbWEgXERlbHRhIEJfalxCaWcpJA0KDQpgYGB7cn0NCnNldC5zZWVkKDExMSkNCm11IDwtIDENCnNpZ21hIDwtIDAuNQ0KeCA8LSAxMA0KTiA8LSAxMDANCkRlbHRhIDwtIFQvTiAj5pe26Ze06Ze06ZqUDQpCIDwtIG51bWVyaWMoTisxKSAj5Yid5aeL5YyW5ZCR6YePICDov5nph4znmoR0XzA9MCxCX3t0XzB9PTANCnQgPC0gc2VxKDAsVCxsZW5ndGggPSBOKzEpDQpmb3IoaSBpbiAyOihOKzEpKQ0KICBCW2ldIDwtIEJbaS0xXStybm9ybSgxKSpzcXJ0KERlbHRhKQ0KDQpTIDwtIHgqZXhwKChtdS1zaWdtYV4yLzIpKnQrc2lnbWEqQikNCg0KcGxvdCh0LFMsdHlwZT0ibCIsbWFpbj0i5Yeg5L2V5biD5pyX6L+Q5YqoIikNCmBgYA0KDQoNCuW5tuS4jeaYr+aJgOacieeahFNERemDveiDveino+WHuuaYvuW8j+ino++8jOabtOWkmueahFNEReWPquiDvemAmui/h+i/reS7o+axguWHuuaVsOWAvOino+OAguaxglNEReaVsOWAvOino+WunumZheS4iuS5n+WwseaYr+aooeaLn+WHuuino+eahOi3r+W+hOOAgg0KDQojIyMgRXVsZXLmoLzlvI8NCg0KJCQNCiAgWV97aSsxfT1ZX2krXG11KHRfaSxZX2kpKHRfe2krMX0tdF9pKStcc2lnbWEodF9pLFlfaSkoQl97aSsxfS1CX2kpDQokJA0KIyMjIE1pbHN0ZWlu5qC85byPDQoNCiQkDQpcYmVnaW57YWxpZ259DQogIFlfe2krMX0mPVlfaStcbXUodF9pLFlfaSkodF97aSsxfS10X2kpK1xzaWdtYSh0X2ksWV9pKShCX3tpKzF9LUJfaSlcXA0KICAmK1xmcmFjezF9ezJ9XHNpZ21hKHRfaSxZX2kpXHNpZ21hX3godF9pLFlfaSlceyhCX3tpKzF9LUJfaSleMi0odF97aSsxfS10X2kpXH0NCiAgXGVuZHthbGlnbn0NCiQkDQrlhbbkuK0kQl97aSsxfS1CX2k9XHNxcnR7dF97aSsxfS10X2l9Wl97aSsxfSxccXVhZCBpPTAsLi4uLG4tMS4kDQoNCg0KIyMgU0RF55qE5Y+C5pWw5Lyw6K6hDQoNCuiAg+iZkeS4i+mdoueahFNERToNCiQkDQogIGRYX3Q9XG11KFhfdDtcdGhldGEpZHQrXHNpZ21hKFhfdCw7XHRoZXRhKWRCX3QNCiQkDQrlhbbkuK0kXHRoZXRhXGluIFxUaGV0YVxzdWJzZXQgXG1hdGhiZntSfV5wJOaYryRwJOe7tOWPguaVsO+8jCRcdGhldGFfMCTmmK/lj4LmlbDnmoTnnJ/lrp7lgLzjgILlh73mlbAkXG11OlxtYXRoYmZ7Un1cdGltZXNcVGhldGFccmlnaHRhcnJvdyBcbWF0aGJme1J9JOWSjCRcc2lnbWE6XG1hdGhiZntSfVx0aW1lc1xUaGV0YVxyaWdodGFycm93KDAsK1xpbmZ0eSkk5piv5bey55+l55qE77yM5bm25LiU5L2/5b6XU0RF55qE6Kej5a2Y5Zyo44CC5aaC5p6c5oiR5Lus6KeC5rWL5Yiw6K+lU0RF6Kej55qE5LiA5p2h6L2o6L+555qE56a75pWj6YeH5qC3JFx7WF9uLG5caW4gXG1hdGhiYntOfVx9LCTnlKjov5nkupvmlbDmja7mnaXkvLDorqHlj4LmlbAkXHRoZXRhLCTlvpfliLDnmoTlj4LmlbDnmoTkvLDorqHkuLokXGhhdHtcdGhldGF9JC4NCg0KIyMjIOaegeWkp+S8vOeEtuS8sOiuoQ0KDQrlgYforr4keF8wLC4uLix4X04k5pivJFhfdCTlnKjlnYfljIDnprvmlaPml7bliLskdF9pPVxEZWx0YSB0JOeahOingua1i++8jOWFtuS4rSRpPTAsMSwuLi4sTixcRGVsdGEgdD1UL04uJA0KDQrku6QkcCh0X2sseF9rfHRfe2stMX0seF97ay0xfTtcdGhldGEpJOaYr+S7jiQodF97ay0xfSx4X3trLTF9KSTliLAkKHRfayx4X2spJOeahOS8oOmAkuamgueOh+WvhuW6pu+8iOadoeS7tuWvhuW6pu+8n++8ie+8jOWBh+iuvuWIneWni+eKtuaAgeeahOamgueOh+WvhuW6puS4uiRwXzAoeF8wfFx0aGV0YSksJOWImeS8vOeEtuWHveaVsOS4uu+8mg0KDQokJA0KICBmKFx0aGV0YSk9cF8wKHhfMHxcdGhldGEpXHByb2Rfe2s9MX1eTnAodF9rLHhfa3x0X3trLTF9LHhfe2stMX07XHRoZXRhKS4NCiQkDQrlr7nmlbDkvLznhLblh73mlbDkuLrvvJoNCg0KJCQNCiAgTChcdGhldGEpPVxzdW1fe2s9MX1eTlxsbiBwKHRfayx4X2t8dF97ay0xfSx4X3trLTF9O1x0aGV0YSkrXGxuIHBfMCh4XzB8XHRoZXRhKS4NCiQkDQrlr7lTREXnmoRFdWxlcui/keS8vO+8jOaciQ0KDQokJA0KICBYX3trfT1YX3trLTF9K1xtdSh0X3trLTF9LHhfe2stMX07XHRoZXRhKVxEZWx0YSB0K1xzaWdtYSh0X3trLTF9LHhfe2stMX07XHRoZXRhKVxzcXJ0e1xEZWx0YSB0fVxldGFfay4NCiQkDQoNCuWFtuS4rSRcZXRhX2tcc2ltIE4oMCwxKS4k55Sx5LiK5byP5Y+v5b6X77yMDQoNCiQkDQogIHAodF9rLHhfa3x0X3trLTF9LHhfe2stMX07XHRoZXRhKT1cZnJhY3sxfXtcc3FydHsyXHBpXHNpZ21hX2t9fVxleHBcQmlnKC1cZnJhY3soeF9rLVxtdV9rKV4yfXsyXHNpZ21hX2teMn1cQmlnKS4NCiQkDQrlhbbkuK0kXG11X2s9eF97ay0xfStcbXUodF97ay0xfSx4X3trLTF9O1x0aGV0YSksXHNpZ21hX2s9XHNpZ21hKHRfe2stMX0seF97ay0xfTtcdGhldGEpXHNxcnR7XERlbHRhIHR9JC4NCg0K6ICD6JmR576O5rSy6bmkMTkzOS0tMTk4NeW5tOeahOenjee+pOaVsOaNru+8jOWBh+iuviR0JOaXtuWIu+enjee+pOWkp+WwjyRYX3Qk5ruh6LazU0RFOg0KDQokJA0KICBkWF90PVx0aGV0YV8xWF90ZHQrXHRoZXRhXzJcc3FydHtYX3R9ZEJfdCxccXVhZCBYXzA9MTguDQokJA0KDQoNCg0KDQoNCg0KDQoNCg0KDQoNCg0K