Gaussian model
Here we will perform maximum likelihood and Bayesian inference for a
one-parameter example. We will assume that \(x_1,\ldots,x_n\) for a independent and
identically distributed (iid) sample from a Gaussian distribution with
mean \(\theta\) and variance \(\sigma^2\), denoted by \(x_i\theta \sim N(\theta,\sigma^2)\), for
\(i=1,2,\ldots,n\) andknown \(\sigma^2\). In other words, only \(\theta\) is unknown in this model
structure. When dealing with linear models, as Gaussian linear
regressions or state-space models, it is useful to rewrite the model as
\[
x_i = \theta + \epsilon_i \qquad \epsilon_i \sim N(0,\sigma^2).
\] Such parametrization, allows us to naturally extend the model
to allow for regressors, such as \(\theta_i=z_i'\beta\), in linear
regression models, such as \(\theta_t =
g(z_i,\beta)\), in nonlinear regression models, or time-varying
parameters, such as \(\theta_t=\theta_{t-1}+u_t\), in state-space
modeling.
Maximum likelihood
inference
The likelihood function is easily derived from the joint density of
the data given \(\theta\) \[
p(x_1,\ldots,x_n | \theta) = \prod_{i=1}^n p(x_i|\theta),
\] such that \[
L(\theta;\mbox{data}) = \prod_{i=1}^n
(2\pi\sigma^2)^{-1/2}\exp\left\{-\frac{0.5}{\sigma^2}(x_i-\theta)^2\right\}
\propto \exp\left\{-\frac{0.5}{\sigma^2}(n\theta^2 - 2n\bar{x}\theta)
\right\},
\] which resembles a Gaussian distribution with mean \(\bar{x}\) and variance \(\sigma^2/n\). In fact, the maximum
likelihood estimator (MLE) of \(\theta\) is \[
{\widehat \theta}_{MLE} = \bar{x},
\] such that \({\widehat
\theta}_{MLE}|\theta \sim N(\theta,\sigma^2/n)\).
x = c(-2.33,-0.52,-0.51,-0.38,0.25,0.77,0.79,0.80,1.35,1.40)
n = length(x)
sigma = 1
# ML estimation
theta.mle = mean(x)
L = theta.mle + qnorm(0.025)*sigma/sqrt(n)
U = theta.mle + qnorm(0.975)*sigma/sqrt(n)
N = 200
thetas = seq(-2,2,length=N)
like = rep(0,N)
for (i in 1:N)
like[i] = prod(dnorm(x,thetas[i],sigma))
par(mfrow=c(1,1))
plot(thetas,like,type="l",ylab="Likelihood",xlab=expression(theta))
abline(v=theta.mle,col=2,lwd=2)
abline(v=L,lty=2,col=2)
abline(v=U,lty=2,col=2)
title(paste("MLE = ",round(theta.mle,3),
"\n95% CI = (",round(L,3),",",round(U,3),")",sep=""))

Bayesian
inference
We will use here a conjugate prior for \(\theta\) \[
\theta \sim N(\theta_0,\tau_0^2),
\] for known hyperparameters \(\theta_0\) and \(\tau_0\). The Gaussian prior conjugates
with the Gaussian likelihood function, which leads to a Gaussian
posterior, ie. \[\begin{eqnarray*}
p(\theta|\mbox{data}) &\propto& p(\theta)L(\theta;\mbox{data)}\\
&\propto& \exp\left\{-\frac{0.5}{\tau_0^2}(\theta^2-2\theta
\theta_0)\right\}
\exp\left\{-\frac{0.5}{\sigma^2}(n\theta^2-2\theta n \bar{x})\right\}\\
&\propto& \exp\left\{-\frac{0.5}{\tau_1^2}(\theta^2-2\theta
\theta_1)\right\},
\end{eqnarray*}\] where \[
\tau_1^{-2} = \tau_0^{-2} + n \sigma^{-2} \ \ \ \mbox{and} \ \ \
\theta_1 = \tau_1^2(\theta_0/\tau_0^2 + n \bar{x}/\sigma^2),
\] and \(n \bar{x} =
\sum_{i=1}^n\). Notice that the posterior precision, \(\tau_1^{-2}\), is the sum of the prior
precision, \(\tau_0^{-2}\), and the
likelihood precision, \(\sigma^2/n\).
As \(n\) gets much larger than \(\tau_0^{-2}\), the posterior precision goes
to infinity and the posterior distribution of \(\theta\) concentrates around \({\bar x}\). A non-informative, improper
prior assumes that \(\theta_0=0\) and
\(\tau_0^{-1}=0\). In this case, \(\theta_1={\bar x}\) and \(\tau_1^2=\sigma^2/n\) and both ML and
Bayesian inference coincide.
Conjugacy, consequently, permits that all posterior summaries are
obtained in closed form, such as the posterior mean and posterior
variance, as well as posterior quantiles which are useful to construct,
say, a 95% credibility interval for \(\theta\).
theta0 = 0
tau02 = 2
tau12 = 1/(1/tau02+n/sigma^2)
theta1 = round(tau12*(theta0/tau02+sum(x)/sigma^2),3)
post = dnorm(thetas,theta1,sqrt(tau12))
L.b = round(theta1 + qnorm(0.025)*sqrt(tau12),3)
U.b = round(theta1 + qnorm(0.975)*sqrt(tau12),3)
plot(thetas,post,type="l",ylab="Posterior density",xlab=expression(theta))
abline(v=theta1,col=2,lwd=2)
abline(v=L.b,lty=2,col=2)
abline(v=U.b,lty=2,col=2)
title(paste("Posterior mean = ",theta1,"\n95% Credibility interval = (",L.b,",",U.b,")",
sep=""))

Comparison
plot(thetas,post,type="l",ylab="Density",xlab=expression(theta))
abline(v=theta1)
abline(v=L.b,lty=2)
abline(v=U.b,lty=2)
lines(thetas,like/max(like)*max(post),col=2)
abline(v=theta.mle,col=2)
abline(v=L,lty=2,col=2)
abline(v=U,lty=2,col=2)
legend("topleft",legend=c("Likelihood","Posterior"),col=1:2,lty=1,bty="n")

Student’s t model
Here, we will learn that posterior inference is virtually never
easily obtained in closed form. Despite the coherent and clean
combination of information provided by Bayesian thinking, computation is
and will always be an important ingredient to allow for accurate
posterior approximation in more complex problems.
Here, we will simply assume that the data might allow for fatter
tails than the Gaussian. More precisely, we will replace the Gaussian
model with a Student’s \(t\) model with
\(\nu\) degrees of freedom, for known
\(\nu\). More precisely, \(x_1,\ldots,x_n\) are still iid, but now
\(t_\nu(\theta,\sigma_0^2)\), for known
\(\sigma_0^2=\frac{\nu-2}{\nu}\sigma^2\), for
\(\nu>2\), \[
p(x_i | \theta, \sigma_0^2, \nu) =
\frac{\Gamma\left(\frac{\nu+1}{2}\right)}{\Gamma\left(\frac{\nu}{2}\right)
(\nu\pi\sigma_0^2)^{1/2}} \left[ 1 + \frac{1}{\nu} \frac{(x_i -
\theta)^2}{\sigma_0^2} \right]^{-\frac{\nu+1}{2}}.
\]
It is easy to see that \[
E(x_i|\theta)=\theta \ \ \ \mbox{and} \ \
\ V(x_i|\theta)=\frac{\nu}{\nu-2}\sigma_0^2=\sigma^2,
\] such that both models, Gaussian and Student’s \(t\), assume the data has the same mean and
the same variance, conditionally on \(\theta\).
The likelihood function is now written as \[
L(\theta;\mbox{data}) = \prod_{i=1}^n p(x_i | \theta, \sigma_0^2, \nu)
\propto
\prod_{i=1}^n \left[ 1 + \frac{1}{\nu} \frac{(x_i -
\theta)^2}{\sigma_0^2} \right]^{-\frac{\nu+1}{2}},
\] which does not conjugate with \(p(\theta) \equiv N(\theta_0,\tau_0^2)\).
Consequently, posterior inference is performed with the assistance of
Monte Carlo integration and simulation.
Sampling importance
sampling (SIR)
Here conjugacy is lost and we will a Monte Carlo simulation scheme to
approximate Bayesian posterior inference. More precisely, we will use a
SIR algorithm to produce draws from \(p(\theta|\mbox{data})\). More precisely,
the algorithm works as follows:
Sample (large) \(M\) draws from
the prior \(p(\theta)\) \[
\{\widetilde{\theta}^{(1)},\ldots,\widetilde{\theta}^{(M)}\};
\]
Evalute the weights \(\omega^{(i)}
\propto L(\widetilde{\theta}^{(i)}|\mbox{data})\);
Resample \(N \leq M\) from the
discrete set \(\{\widetilde{\theta}^{(1)},\ldots,\widetilde{\theta}^{(M)}\}\)
with probabilities \(\{\omega^{(1)},\ldots,\omega^{(M)}\}\).
It can be shown that the final sampled set, say \[
\{\theta^{(1)},\ldots,\theta^{(N)}\},
\] approximates a sample from \(p(\theta|\mbox{data})\). More details about
Monte Carlo integration, MC simulation, SIR and other Monte Carlo
schemes, can be found in my course notes here.
nu = 4
sigma0 = sqrt((nu-2)/nu)*sigma
M = 100000
# Step 1: Sampling from the prior
theta.draws = rnorm(M,theta0,sqrt(tau02))
# Step 2: Computing resampling weights
w = rep(0,M)
for (i in 1:M)
w[i] = sum(dt((x-theta.draws[i])/sigma0,df=nu,log=TRUE))
w = exp(w-max(w))
# Step 3: resampling
ind = sample(1:M,replace=TRUE,size=M/2,prob=w)
theta.post = theta.draws[ind]
# Posterior quantiles and density plot
L.t = quantile(theta.post,0.025)
U.t = quantile(theta.post,0.975)
plot(density(theta.post),ylab="Posterior density",
xlab=expression(theta),main="",lwd=2,ylim=c(0,1.4))
lines(thetas,post,col=2,lwd=2)
segments(L.b,0.0,U.b,0.0,lwd=2,col=2,lty=2)
segments(L.t,0.04,U.t,0.04,lwd=2,lty=2)
points(L.b,0.0,pch=16,col=2)
points(U.b,0.0,pch=16,col=2)
points(L.t,0.04,pch=16)
points(U.t,0.04,pch=16)
legend("topleft",legend=c("Gaussian","Student's t(4)"),col=2:1,lty=1,bty="n",lwd=2)
legend("topright",legend=c("Data",x),bty="n")
title(paste("Sample mean=",round(theta.mle,2),"\n Sample stdev=",
round(sqrt(var(x)),2),sep=""))

Playing around with
\(\nu\)
In the exercise below, we vary \(\nu\) from \(3\) to \(30\) and compare the 95% credibility
intervals. As the figure below reveals, as \(\nu\) increases the Student’s \(t\) converges to the Gaussian distribution
and the credibility intervals become quite similar. Only for small \(\nu\) there is some departure from
Gaussianity.
M = 100000
nus = 3:30
nnu = length(nus)
quants = matrix(0,nnu,3)
theta.draws = rnorm(M,theta0,sqrt(tau02))
for (j in 1:nnu){
nu = nus[j]
sigma0 = sqrt((nu-2)/nu)*sigma
w = rep(0,M)
for (i in 1:M)
w[i] = sum(dt((x-theta.draws[i])/sigma0,df=nu,log=TRUE))
w = exp(w-max(w))
ind = sample(1:M,replace=TRUE,size=M/2,prob=w)
theta.post = theta.draws[ind]
quants[j,] = quantile(theta.post,c(0.025,0.5,0.975))
}
plot(nus,quants[,1],pch=16,type="l",ylab="95% interval",xlab=expression(nu),ylim=c(-0.5,1))
abline(h=L.b,col=2,lwd=2)
abline(h=U.b,col=2,lwd=2)
abline(h=theta1,col=2,lwd=2)
lines(nus,quants[,1],lwd=2)
lines(nus,quants[,2],lwd=2)
lines(nus,quants[,3],lwd=2)
legend("topright",legend=c("Gaussian","Student's t"),col=2:1,lty=1,bty="n",lwd=2)

LS0tCnRpdGxlOiAiR2F1c3NpYW4gdnMgU3R1ZGVudCdzIHQgZGF0YSIKc3VidGl0bGU6ICJDbG9zZWQtZm9ybSBpbmZlcmVuY2UgdnMgTUMtYmFzZWQgaW5mZXJlbmNlIgphdXRob3I6ICJIZWRpYmVydCBGcmVpdGFzIExvcGVzIgpkYXRlOiAiYHIgU3lzLkRhdGUoKWAiCm91dHB1dDoKICBodG1sX2RvY3VtZW50OgogICAgdGhlbWU6IHBhcGVyCiAgICBoaWdobGlnaHQ6IHB5Z21lbnRzCiAgICB0b2M6IHRydWUKICAgIHRvY19kZXB0aDogMwogICAgdG9jX2NvbGxhcHNlZDogdHJ1ZQogICAgdG9jX2Zsb2F0OiB0cnVlCiAgICBjb2RlX2Rvd25sb2FkOiB0cnVlCiAgICBudW1iZXJfc2VjdGlvbnM6IHRydWUKLS0tCgoKIyBHYXVzc2lhbiBtb2RlbApIZXJlIHdlIHdpbGwgcGVyZm9ybSBtYXhpbXVtIGxpa2VsaWhvb2QgYW5kIEJheWVzaWFuIGluZmVyZW5jZSBmb3IgYSBvbmUtcGFyYW1ldGVyIGV4YW1wbGUuCldlIHdpbGwgYXNzdW1lIHRoYXQgJHhfMSxcbGRvdHMseF9uJCBmb3IgYSBpbmRlcGVuZGVudCBhbmQgaWRlbnRpY2FsbHkgZGlzdHJpYnV0ZWQgKGlpZCkgc2FtcGxlIGZyb20gYSBHYXVzc2lhbiBkaXN0cmlidXRpb24gd2l0aCBtZWFuICRcdGhldGEkIGFuZCB2YXJpYW5jZSAkXHNpZ21hXjIkLCBkZW5vdGVkIGJ5ICR4X2lcdGhldGEgXHNpbSBOKFx0aGV0YSxcc2lnbWFeMikkLCBmb3IgJGk9MSwyLFxsZG90cyxuJCBhbmRrbm93biAkXHNpZ21hXjIkLiAgSW4gb3RoZXIgd29yZHMsIG9ubHkgJFx0aGV0YSQgaXMgdW5rbm93biBpbiB0aGlzIG1vZGVsIHN0cnVjdHVyZS4gICBXaGVuIGRlYWxpbmcgd2l0aCBsaW5lYXIgbW9kZWxzLCBhcyBHYXVzc2lhbiBsaW5lYXIgcmVncmVzc2lvbnMgb3Igc3RhdGUtc3BhY2UgbW9kZWxzLCBpdCBpcyB1c2VmdWwgdG8gcmV3cml0ZSB0aGUgbW9kZWwgYXMKJCQKeF9pID0gXHRoZXRhICsgXGVwc2lsb25faSBccXF1YWQgXGVwc2lsb25faSBcc2ltIE4oMCxcc2lnbWFeMikuCiQkClN1Y2ggcGFyYW1ldHJpemF0aW9uLCBhbGxvd3MgdXMgdG8gbmF0dXJhbGx5IGV4dGVuZCB0aGUgbW9kZWwgdG8gYWxsb3cgZm9yIHJlZ3Jlc3NvcnMsIHN1Y2ggYXMgJFx0aGV0YV9pPXpfaSdcYmV0YSQsIGluIGxpbmVhciByZWdyZXNzaW9uIG1vZGVscywgc3VjaCBhcyAkXHRoZXRhX3QgPSBnKHpfaSxcYmV0YSkkLCBpbiBub25saW5lYXIgcmVncmVzc2lvbiBtb2RlbHMsIG9yIHRpbWUtdmFyeWluZyBwYXJhbWV0ZXJzLCBzdWNoIGFzICRcdGhldGFfdD1cdGhldGFfe3QtMX0rdV90JCwgaW4gc3RhdGUtc3BhY2UgbW9kZWxpbmcuCgojIyBNYXhpbXVtIGxpa2VsaWhvb2QgaW5mZXJlbmNlCgpUaGUgbGlrZWxpaG9vZCBmdW5jdGlvbiBpcyBlYXNpbHkgZGVyaXZlZCBmcm9tIHRoZSBqb2ludCBkZW5zaXR5IG9mIHRoZSBkYXRhIGdpdmVuICRcdGhldGEkCiQkCnAoeF8xLFxsZG90cyx4X24gfCBcdGhldGEpID0gXHByb2Rfe2k9MX1ebiBwKHhfaXxcdGhldGEpLAokJApzdWNoIHRoYXQKJCQKTChcdGhldGE7XG1ib3h7ZGF0YX0pID0gXHByb2Rfe2k9MX1ebiAoMlxwaVxzaWdtYV4yKV57LTEvMn1cZXhwXGxlZnRcey1cZnJhY3swLjV9e1xzaWdtYV4yfSh4X2ktXHRoZXRhKV4yXHJpZ2h0XH0gClxwcm9wdG8gXGV4cFxsZWZ0XHstXGZyYWN7MC41fXtcc2lnbWFeMn0oblx0aGV0YV4yIC0gMm5cYmFye3h9XHRoZXRhKSBccmlnaHRcfSwKJCQKd2hpY2ggcmVzZW1ibGVzIGEgR2F1c3NpYW4gZGlzdHJpYnV0aW9uIHdpdGggbWVhbiAkXGJhcnt4fSQgYW5kIHZhcmlhbmNlICRcc2lnbWFeMi9uJC4gIEluIGZhY3QsIHRoZSBtYXhpbXVtIGxpa2VsaWhvb2QgZXN0aW1hdG9yIChNTEUpIG9mICRcdGhldGEkIGlzIAokJAp7XHdpZGVoYXQgXHRoZXRhfV97TUxFfSA9IFxiYXJ7eH0sCiQkCnN1Y2ggdGhhdCAke1x3aWRlaGF0IFx0aGV0YX1fe01MRX18XHRoZXRhIFxzaW0gTihcdGhldGEsXHNpZ21hXjIvbikkLgoKYGBge3IgZmlnLmFsaWduPSdjZW50ZXInLCBmaWcud2lkdGg9MTAsIGZpZy5oZWlnaHQ9Nn0KeCA9IGMoLTIuMzMsLTAuNTIsLTAuNTEsLTAuMzgsMC4yNSwwLjc3LDAuNzksMC44MCwxLjM1LDEuNDApCm4gPSBsZW5ndGgoeCkKc2lnbWEgICAgID0gMQoKIyBNTCBlc3RpbWF0aW9uCnRoZXRhLm1sZSA9IG1lYW4oeCkKTCAgICAgICAgID0gdGhldGEubWxlICsgcW5vcm0oMC4wMjUpKnNpZ21hL3NxcnQobikKVSAgICAgICAgID0gdGhldGEubWxlICsgcW5vcm0oMC45NzUpKnNpZ21hL3NxcnQobikKCk4gICAgICA9IDIwMAp0aGV0YXMgPSBzZXEoLTIsMixsZW5ndGg9TikKbGlrZSAgID0gcmVwKDAsTikKZm9yIChpIGluIDE6TikKICBsaWtlW2ldID0gcHJvZChkbm9ybSh4LHRoZXRhc1tpXSxzaWdtYSkpCgpwYXIobWZyb3c9YygxLDEpKQpwbG90KHRoZXRhcyxsaWtlLHR5cGU9ImwiLHlsYWI9Ikxpa2VsaWhvb2QiLHhsYWI9ZXhwcmVzc2lvbih0aGV0YSkpCmFibGluZSh2PXRoZXRhLm1sZSxjb2w9Mixsd2Q9MikKYWJsaW5lKHY9TCxsdHk9Mixjb2w9MikKYWJsaW5lKHY9VSxsdHk9Mixjb2w9MikKdGl0bGUocGFzdGUoIk1MRSA9ICIscm91bmQodGhldGEubWxlLDMpLAogICAgICAiXG45NSUgQ0kgPSAoIixyb3VuZChMLDMpLCIsIixyb3VuZChVLDMpLCIpIixzZXA9IiIpKQpgYGAKCgojIyBCYXllc2lhbiBpbmZlcmVuY2UKCldlIHdpbGwgdXNlIGhlcmUgYSBjb25qdWdhdGUgcHJpb3IgZm9yICRcdGhldGEkCiQkClx0aGV0YSBcc2ltIE4oXHRoZXRhXzAsXHRhdV8wXjIpLAokJApmb3Iga25vd24gaHlwZXJwYXJhbWV0ZXJzICRcdGhldGFfMCQgYW5kICRcdGF1XzAkLiAgVGhlIEdhdXNzaWFuIHByaW9yIGNvbmp1Z2F0ZXMgd2l0aCB0aGUgR2F1c3NpYW4gbGlrZWxpaG9vZCBmdW5jdGlvbiwgd2hpY2ggbGVhZHMgdG8gYSBHYXVzc2lhbiBwb3N0ZXJpb3IsIGllLgpcYmVnaW57ZXFuYXJyYXkqfQpwKFx0aGV0YXxcbWJveHtkYXRhfSkgJlxwcm9wdG8mIHAoXHRoZXRhKUwoXHRoZXRhO1xtYm94e2RhdGEpfVxcCiZccHJvcHRvJiBcZXhwXGxlZnRcey1cZnJhY3swLjV9e1x0YXVfMF4yfShcdGhldGFeMi0yXHRoZXRhIFx0aGV0YV8wKVxyaWdodFx9ClxleHBcbGVmdFx7LVxmcmFjezAuNX17XHNpZ21hXjJ9KG5cdGhldGFeMi0yXHRoZXRhIG4gXGJhcnt4fSlccmlnaHRcfVxcCiZccHJvcHRvJiBcZXhwXGxlZnRcey1cZnJhY3swLjV9e1x0YXVfMV4yfShcdGhldGFeMi0yXHRoZXRhIFx0aGV0YV8xKVxyaWdodFx9LApcZW5ke2VxbmFycmF5Kn0Kd2hlcmUgCiQkClx0YXVfMV57LTJ9ID0gXHRhdV8wXnstMn0gKyBuIFxzaWdtYV57LTJ9IFwgXCBcIFxtYm94e2FuZH0gXCBcIFwgClx0aGV0YV8xID0gXHRhdV8xXjIoXHRoZXRhXzAvXHRhdV8wXjIgKyBuIFxiYXJ7eH0vXHNpZ21hXjIpLAokJAphbmQgJG4gXGJhcnt4fSA9IFxzdW1fe2k9MX1ebiQuICBOb3RpY2UgdGhhdCB0aGUgcG9zdGVyaW9yIHByZWNpc2lvbiwgJFx0YXVfMV57LTJ9JCwgaXMgdGhlIHN1bSBvZiB0aGUgcHJpb3IgcHJlY2lzaW9uLCAkXHRhdV8wXnstMn0kLCBhbmQgdGhlIGxpa2VsaWhvb2QgcHJlY2lzaW9uLCAkXHNpZ21hXjIvbiQuIEFzICRuJCBnZXRzIG11Y2ggbGFyZ2VyIHRoYW4gJFx0YXVfMF57LTJ9JCwgdGhlIHBvc3RlcmlvciBwcmVjaXNpb24gZ29lcyB0byBpbmZpbml0eSBhbmQgdGhlIHBvc3RlcmlvciBkaXN0cmlidXRpb24gb2YgJFx0aGV0YSQgY29uY2VudHJhdGVzIGFyb3VuZCAke1xiYXIgeH0kLiAgQSBub24taW5mb3JtYXRpdmUsIGltcHJvcGVyIHByaW9yIGFzc3VtZXMgdGhhdCAkXHRoZXRhXzA9MCQgYW5kICRcdGF1XzBeey0xfT0wJC4gIEluIHRoaXMgY2FzZSwgJFx0aGV0YV8xPXtcYmFyIHh9JCBhbmQgJFx0YXVfMV4yPVxzaWdtYV4yL24kIGFuZCBib3RoIE1MIGFuZCBCYXllc2lhbiBpbmZlcmVuY2UgY29pbmNpZGUuCgpDb25qdWdhY3ksIGNvbnNlcXVlbnRseSwgcGVybWl0cyB0aGF0IGFsbCBwb3N0ZXJpb3Igc3VtbWFyaWVzIGFyZSBvYnRhaW5lZCBpbiBjbG9zZWQgZm9ybSwgc3VjaCBhcyB0aGUgcG9zdGVyaW9yIG1lYW4gYW5kIHBvc3RlcmlvciB2YXJpYW5jZSwgYXMgd2VsbCBhcyBwb3N0ZXJpb3IgcXVhbnRpbGVzIHdoaWNoIGFyZSB1c2VmdWwgdG8gY29uc3RydWN0LCBzYXksIGEgOTVcJSBjcmVkaWJpbGl0eSBpbnRlcnZhbCBmb3IgJFx0aGV0YSQuCgpgYGB7ciBmaWcuYWxpZ249J2NlbnRlcicsIGZpZy53aWR0aD0xMCwgZmlnLmhlaWdodD02fQp0aGV0YTAgPSAwCnRhdTAyICA9IDIKdGF1MTIgID0gMS8oMS90YXUwMituL3NpZ21hXjIpCnRoZXRhMSA9IHJvdW5kKHRhdTEyKih0aGV0YTAvdGF1MDIrc3VtKHgpL3NpZ21hXjIpLDMpCnBvc3QgICA9IGRub3JtKHRoZXRhcyx0aGV0YTEsc3FydCh0YXUxMikpCkwuYiAgICA9IHJvdW5kKHRoZXRhMSArIHFub3JtKDAuMDI1KSpzcXJ0KHRhdTEyKSwzKQpVLmIgICAgPSByb3VuZCh0aGV0YTEgKyBxbm9ybSgwLjk3NSkqc3FydCh0YXUxMiksMykKCnBsb3QodGhldGFzLHBvc3QsdHlwZT0ibCIseWxhYj0iUG9zdGVyaW9yIGRlbnNpdHkiLHhsYWI9ZXhwcmVzc2lvbih0aGV0YSkpCmFibGluZSh2PXRoZXRhMSxjb2w9Mixsd2Q9MikKYWJsaW5lKHY9TC5iLGx0eT0yLGNvbD0yKQphYmxpbmUodj1VLmIsbHR5PTIsY29sPTIpCnRpdGxlKHBhc3RlKCJQb3N0ZXJpb3IgbWVhbiA9ICIsdGhldGExLCJcbjk1JSBDcmVkaWJpbGl0eSBpbnRlcnZhbCA9ICgiLEwuYiwiLCIsVS5iLCIpIiwKICAgICAgICAgICAgc2VwPSIiKSkKYGBgCgojIyBDb21wYXJpc29uCgpgYGB7ciBmaWcuYWxpZ249J2NlbnRlcicsIGZpZy53aWR0aD0xMCwgZmlnLmhlaWdodD02fQpwbG90KHRoZXRhcyxwb3N0LHR5cGU9ImwiLHlsYWI9IkRlbnNpdHkiLHhsYWI9ZXhwcmVzc2lvbih0aGV0YSkpCmFibGluZSh2PXRoZXRhMSkKYWJsaW5lKHY9TC5iLGx0eT0yKQphYmxpbmUodj1VLmIsbHR5PTIpCmxpbmVzKHRoZXRhcyxsaWtlL21heChsaWtlKSptYXgocG9zdCksY29sPTIpCmFibGluZSh2PXRoZXRhLm1sZSxjb2w9MikKYWJsaW5lKHY9TCxsdHk9Mixjb2w9MikKYWJsaW5lKHY9VSxsdHk9Mixjb2w9MikKbGVnZW5kKCJ0b3BsZWZ0IixsZWdlbmQ9YygiTGlrZWxpaG9vZCIsIlBvc3RlcmlvciIpLGNvbD0xOjIsbHR5PTEsYnR5PSJuIikKYGBgCgojIFN0dWRlbnQncyB0IG1vZGVsCgpIZXJlLCB3ZSB3aWxsIGxlYXJuIHRoYXQgcG9zdGVyaW9yIGluZmVyZW5jZSBpcyB2aXJ0dWFsbHkgbmV2ZXIgZWFzaWx5IG9idGFpbmVkIGluIGNsb3NlZCBmb3JtLiAgRGVzcGl0ZSB0aGUgY29oZXJlbnQgYW5kIGNsZWFuIGNvbWJpbmF0aW9uIG9mIGluZm9ybWF0aW9uIHByb3ZpZGVkIGJ5IEJheWVzaWFuIHRoaW5raW5nLCBjb21wdXRhdGlvbiBpcyBhbmQgd2lsbCBhbHdheXMgYmUgYW4gaW1wb3J0YW50IGluZ3JlZGllbnQgdG8gYWxsb3cgZm9yIGFjY3VyYXRlIHBvc3RlcmlvciBhcHByb3hpbWF0aW9uIGluIG1vcmUgY29tcGxleCBwcm9ibGVtcy4KCkhlcmUsIHdlIHdpbGwgc2ltcGx5IGFzc3VtZSB0aGF0IHRoZSBkYXRhIG1pZ2h0IGFsbG93IGZvciBmYXR0ZXIgdGFpbHMgdGhhbiB0aGUgR2F1c3NpYW4uICBNb3JlIHByZWNpc2VseSwgd2Ugd2lsbCByZXBsYWNlIHRoZSBHYXVzc2lhbiBtb2RlbCB3aXRoIGEgU3R1ZGVudCdzICR0JCBtb2RlbCB3aXRoICRcbnUkIGRlZ3JlZXMgb2YgZnJlZWRvbSwgZm9yIGtub3duICRcbnUkLiAgTW9yZSBwcmVjaXNlbHksICR4XzEsXGxkb3RzLHhfbiQgYXJlIHN0aWxsIGlpZCwgYnV0IG5vdyAkdF9cbnUoXHRoZXRhLFxzaWdtYV8wXjIpJCwgZm9yIGtub3duICRcc2lnbWFfMF4yPVxmcmFje1xudS0yfXtcbnV9XHNpZ21hXjIkLCBmb3IgJFxudT4yJCwKJCQKcCh4X2kgfCBcdGhldGEsIFxzaWdtYV8wXjIsIFxudSkgPSBcZnJhY3tcR2FtbWFcbGVmdChcZnJhY3tcbnUrMX17Mn1ccmlnaHQpfXtcR2FtbWFcbGVmdChcZnJhY3tcbnV9ezJ9XHJpZ2h0KSAoXG51XHBpXHNpZ21hXzBeMileezEvMn19IFxsZWZ0WyAxICsgXGZyYWN7MX17XG51fSBcZnJhY3soeF9pIC0gXHRoZXRhKV4yfXtcc2lnbWFfMF4yfSBccmlnaHRdXnstXGZyYWN7XG51KzF9ezJ9fS4KJCQKCkl0IGlzIGVhc3kgdG8gc2VlIHRoYXQKJCQKRSh4X2l8XHRoZXRhKT1cdGhldGEgXCBcIFwgXG1ib3h7YW5kfSBcIFwgXCAgVih4X2l8XHRoZXRhKT1cZnJhY3tcbnV9e1xudS0yfVxzaWdtYV8wXjI9XHNpZ21hXjIsCiQkCnN1Y2ggdGhhdCBib3RoIG1vZGVscywgR2F1c3NpYW4gYW5kIFN0dWRlbnQncyAkdCQsIGFzc3VtZSB0aGUgZGF0YSBoYXMgdGhlIHNhbWUgbWVhbiBhbmQgdGhlIHNhbWUgdmFyaWFuY2UsIGNvbmRpdGlvbmFsbHkgb24gJFx0aGV0YSQuCgpUaGUgbGlrZWxpaG9vZCBmdW5jdGlvbiBpcyBub3cgd3JpdHRlbiBhcwokJApMKFx0aGV0YTtcbWJveHtkYXRhfSkgPSBccHJvZF97aT0xfV5uIHAoeF9pIHwgXHRoZXRhLCBcc2lnbWFfMF4yLCBcbnUpIFxwcm9wdG8KXHByb2Rfe2k9MX1ebiBcbGVmdFsgMSArIFxmcmFjezF9e1xudX0gXGZyYWN7KHhfaSAtIFx0aGV0YSleMn17XHNpZ21hXzBeMn0gXHJpZ2h0XV57LVxmcmFje1xudSsxfXsyfX0sCiQkCndoaWNoIGRvZXMgbm90IGNvbmp1Z2F0ZSB3aXRoICRwKFx0aGV0YSkgXGVxdWl2IE4oXHRoZXRhXzAsXHRhdV8wXjIpJC4gIENvbnNlcXVlbnRseSwgcG9zdGVyaW9yIGluZmVyZW5jZSBpcyBwZXJmb3JtZWQgd2l0aCB0aGUgYXNzaXN0YW5jZSBvZiBNb250ZSBDYXJsbyBpbnRlZ3JhdGlvbiBhbmQgc2ltdWxhdGlvbi4KCiMjIFNhbXBsaW5nIGltcG9ydGFuY2Ugc2FtcGxpbmcgKFNJUikKCkhlcmUgY29uanVnYWN5IGlzIGxvc3QgYW5kIHdlIHdpbGwgYSBNb250ZSBDYXJsbyBzaW11bGF0aW9uIHNjaGVtZSB0byBhcHByb3hpbWF0ZSBCYXllc2lhbiBwb3N0ZXJpb3IgaW5mZXJlbmNlLiAgTW9yZSBwcmVjaXNlbHksIHdlIHdpbGwgdXNlIGEgU0lSIGFsZ29yaXRobSB0byBwcm9kdWNlIGRyYXdzIGZyb20gJHAoXHRoZXRhfFxtYm94e2RhdGF9KSQuICBNb3JlIHByZWNpc2VseSwgdGhlIGFsZ29yaXRobSB3b3JrcyBhcyBmb2xsb3dzOgoKMSkgU2FtcGxlIChsYXJnZSkgJE0kIGRyYXdzIGZyb20gdGhlIHByaW9yICRwKFx0aGV0YSkkCiQkClx7XHdpZGV0aWxkZXtcdGhldGF9XnsoMSl9LFxsZG90cyxcd2lkZXRpbGRle1x0aGV0YX1eeyhNKX1cfTsKJCQKCjIpIEV2YWx1dGUgdGhlIHdlaWdodHMgJFxvbWVnYV57KGkpfSBccHJvcHRvIEwoXHdpZGV0aWxkZXtcdGhldGF9XnsoaSl9fFxtYm94e2RhdGF9KSQ7CgozKSBSZXNhbXBsZSAkTiBcbGVxIE0kIGZyb20gdGhlIGRpc2NyZXRlIHNldCAkXHtcd2lkZXRpbGRle1x0aGV0YX1eeygxKX0sXGxkb3RzLFx3aWRldGlsZGV7XHRoZXRhfV57KE0pfVx9JCAgd2l0aCBwcm9iYWJpbGl0aWVzICRce1xvbWVnYV57KDEpfSxcbGRvdHMsXG9tZWdhXnsoTSl9XH0kLgoKSXQgY2FuIGJlIHNob3duIHRoYXQgdGhlIGZpbmFsIHNhbXBsZWQgc2V0LCBzYXkgCiQkClx7XHRoZXRhXnsoMSl9LFxsZG90cyxcdGhldGFeeyhOKX1cfSwKJCQKYXBwcm94aW1hdGVzIGEgc2FtcGxlIGZyb20gJHAoXHRoZXRhfFxtYm94e2RhdGF9KSQuICBNb3JlIGRldGFpbHMgYWJvdXQgTW9udGUgQ2FybG8gaW50ZWdyYXRpb24sIE1DIHNpbXVsYXRpb24sIFNJUiBhbmQgb3RoZXIgTW9udGUgQ2FybG8gc2NoZW1lcywgY2FuIGJlIGZvdW5kIGluIG15IGNvdXJzZSBub3RlcyBbaGVyZV0oaHR0cHM6Ly9oZWRpYmVydC5vcmcvd3AtY29udGVudC91cGxvYWRzLzIwMjAvMDEvYXByZW5kaXphZ2VtYmF5ZXNpYW5hLWJheWVzaWFuY29tcHV0YXRpb24ucGRmKS4KCmBgYHtyIGZpZy5hbGlnbj0nY2VudGVyJywgZmlnLndpZHRoPTEwLCBmaWcuaGVpZ2h0PTZ9Cm51ICAgICA9IDQKc2lnbWEwID0gc3FydCgobnUtMikvbnUpKnNpZ21hCk0gICAgICA9IDEwMDAwMAoKIyBTdGVwIDE6IFNhbXBsaW5nIGZyb20gdGhlIHByaW9yCnRoZXRhLmRyYXdzID0gcm5vcm0oTSx0aGV0YTAsc3FydCh0YXUwMikpCgojIFN0ZXAgMjogQ29tcHV0aW5nIHJlc2FtcGxpbmcgd2VpZ2h0cwp3ID0gcmVwKDAsTSkKZm9yIChpIGluIDE6TSkKICB3W2ldID0gc3VtKGR0KCh4LXRoZXRhLmRyYXdzW2ldKS9zaWdtYTAsZGY9bnUsbG9nPVRSVUUpKQp3ID0gZXhwKHctbWF4KHcpKQoKIyBTdGVwIDM6IHJlc2FtcGxpbmcKaW5kID0gc2FtcGxlKDE6TSxyZXBsYWNlPVRSVUUsc2l6ZT1NLzIscHJvYj13KQp0aGV0YS5wb3N0ID0gdGhldGEuZHJhd3NbaW5kXQoKIyBQb3N0ZXJpb3IgcXVhbnRpbGVzIGFuZCBkZW5zaXR5IHBsb3QKTC50ID0gcXVhbnRpbGUodGhldGEucG9zdCwwLjAyNSkKVS50ID0gcXVhbnRpbGUodGhldGEucG9zdCwwLjk3NSkKCnBsb3QoZGVuc2l0eSh0aGV0YS5wb3N0KSx5bGFiPSJQb3N0ZXJpb3IgZGVuc2l0eSIsCiAgICAgeGxhYj1leHByZXNzaW9uKHRoZXRhKSxtYWluPSIiLGx3ZD0yLHlsaW09YygwLDEuNCkpCmxpbmVzKHRoZXRhcyxwb3N0LGNvbD0yLGx3ZD0yKQpzZWdtZW50cyhMLmIsMC4wLFUuYiwwLjAsbHdkPTIsY29sPTIsbHR5PTIpCnNlZ21lbnRzKEwudCwwLjA0LFUudCwwLjA0LGx3ZD0yLGx0eT0yKQpwb2ludHMoTC5iLDAuMCxwY2g9MTYsY29sPTIpCnBvaW50cyhVLmIsMC4wLHBjaD0xNixjb2w9MikKcG9pbnRzKEwudCwwLjA0LHBjaD0xNikKcG9pbnRzKFUudCwwLjA0LHBjaD0xNikKbGVnZW5kKCJ0b3BsZWZ0IixsZWdlbmQ9YygiR2F1c3NpYW4iLCJTdHVkZW50J3MgdCg0KSIpLGNvbD0yOjEsbHR5PTEsYnR5PSJuIixsd2Q9MikKbGVnZW5kKCJ0b3ByaWdodCIsbGVnZW5kPWMoIkRhdGEiLHgpLGJ0eT0ibiIpCnRpdGxlKHBhc3RlKCJTYW1wbGUgbWVhbj0iLHJvdW5kKHRoZXRhLm1sZSwyKSwiXG4gU2FtcGxlIHN0ZGV2PSIsCiAgICAgICAgICAgIHJvdW5kKHNxcnQodmFyKHgpKSwyKSxzZXA9IiIpKQpgYGAKCiMjIFBsYXlpbmcgYXJvdW5kIHdpdGggJFxudSQKSW4gdGhlIGV4ZXJjaXNlIGJlbG93LCB3ZSB2YXJ5ICRcbnUkIGZyb20gJDMkIHRvICQzMCQgYW5kIGNvbXBhcmUgdGhlIDk1XCUgY3JlZGliaWxpdHkgaW50ZXJ2YWxzLiAgQXMgdGhlIGZpZ3VyZSBiZWxvdyByZXZlYWxzLCBhcyAkXG51JCBpbmNyZWFzZXMgdGhlIFN0dWRlbnQncyAkdCQgY29udmVyZ2VzIHRvIHRoZSBHYXVzc2lhbiBkaXN0cmlidXRpb24gYW5kIHRoZSBjcmVkaWJpbGl0eSBpbnRlcnZhbHMgYmVjb21lIHF1aXRlIHNpbWlsYXIuICBPbmx5IGZvciBzbWFsbCAkXG51JCB0aGVyZSBpcyBzb21lIGRlcGFydHVyZSBmcm9tIEdhdXNzaWFuaXR5LgoKYGBge3IgZmlnLmFsaWduPSdjZW50ZXInLCBmaWcud2lkdGg9MTAsIGZpZy5oZWlnaHQ9Nn0KTSAgID0gMTAwMDAwCm51cyA9IDM6MzAKbm51ID0gbGVuZ3RoKG51cykKcXVhbnRzID0gbWF0cml4KDAsbm51LDMpCnRoZXRhLmRyYXdzID0gcm5vcm0oTSx0aGV0YTAsc3FydCh0YXUwMikpCmZvciAoaiBpbiAxOm5udSl7CiAgbnUgPSBudXNbal0KICBzaWdtYTAgPSBzcXJ0KChudS0yKS9udSkqc2lnbWEKICB3ID0gcmVwKDAsTSkKICBmb3IgKGkgaW4gMTpNKQogICAgd1tpXSA9IHN1bShkdCgoeC10aGV0YS5kcmF3c1tpXSkvc2lnbWEwLGRmPW51LGxvZz1UUlVFKSkKICB3ID0gZXhwKHctbWF4KHcpKQogIGluZCA9IHNhbXBsZSgxOk0scmVwbGFjZT1UUlVFLHNpemU9TS8yLHByb2I9dykKICB0aGV0YS5wb3N0ID0gdGhldGEuZHJhd3NbaW5kXQogIHF1YW50c1tqLF0gPSBxdWFudGlsZSh0aGV0YS5wb3N0LGMoMC4wMjUsMC41LDAuOTc1KSkKfQoKcGxvdChudXMscXVhbnRzWywxXSxwY2g9MTYsdHlwZT0ibCIseWxhYj0iOTUlIGludGVydmFsIix4bGFiPWV4cHJlc3Npb24obnUpLHlsaW09YygtMC41LDEpKQphYmxpbmUoaD1MLmIsY29sPTIsbHdkPTIpCmFibGluZShoPVUuYixjb2w9Mixsd2Q9MikKYWJsaW5lKGg9dGhldGExLGNvbD0yLGx3ZD0yKQpsaW5lcyhudXMscXVhbnRzWywxXSxsd2Q9MikKbGluZXMobnVzLHF1YW50c1ssMl0sbHdkPTIpCmxpbmVzKG51cyxxdWFudHNbLDNdLGx3ZD0yKQpsZWdlbmQoInRvcHJpZ2h0IixsZWdlbmQ9YygiR2F1c3NpYW4iLCJTdHVkZW50J3MgdCIpLGNvbD0yOjEsbHR5PTEsYnR5PSJuIixsd2Q9MikKYGBgCgo=