1 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.

1.1 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=""))

1.2 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=""))

1.3 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")

2 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.

2.1 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:

  1. Sample (large) \(M\) draws from the prior \(p(\theta)\) \[ \{\widetilde{\theta}^{(1)},\ldots,\widetilde{\theta}^{(M)}\}; \]

  2. Evalute the weights \(\omega^{(i)} \propto L(\widetilde{\theta}^{(i)}|\mbox{data})\);

  3. 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=""))

2.2 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=