1 iid Bernoulli model

Here we assume that the data \(y_{1:n}=\{y_1,\ldots,y_n\}\) is modeled as a random sample from \(Bernoulli(\theta)\). In our classroom example, the binary random variable \(y_i=1\) if individual \(i\) (attending the class) has three or more siblings, including himself or herself, with \(y_i=0\), otherwise. One of the main goals is to access the uncertainty around \(\theta\), i.e. the posterior \(p(\theta|y_{1:n})\), and then obtain \(Pr(y_{n+1}=1|y_{1:n})\), the probability that the \((n+1)\) individual has three or more siblings, including himself or herself.

1.1 Maximum likelihood estimation

From basic likelihood-based statistical inference, it is easy to see that \[ {\widehat \theta}_{mle} \equiv \mbox{arg}\max_{\theta \in (0,1)} L(\theta;y_{1:n}), \] where the likelihood function \(L(\theta;\mbox{data})\) is given by \[ L(\theta;\mbox{data}) = \prod_{i=1}^n \theta^{y_i}(1-\theta)^{1-y_i} = \theta^{s_n}(1-\theta)^{n-s_n}, \] where \(s_n = \sum_{i=1}^n y_i\) is the number of sucesses out of \(n\) (Bernoulli) trials. We compute the MLE of \(\theta\) based on \(n=10\) observations and \(y_{1:10}=\{0,0,0,1,0,1,0,1,0,1\}\), so $s_{10}=4 and \({\widehat \theta}_{mle}=4/10=0.4\).

n = 10
y = c(0,0,0,1,0,1,0,1,0,1)
s = sum(y==1)

mle = s/n
c(n,s,mle)
## [1] 10.0  4.0  0.4

1.2 Prior, likelihood and posterior for \(\theta\)

We have elicited a prior for \(\theta\) in class (with the help of Vitória) and arrived at the following Beta distribution: \(\theta \sim Beta(a,b)\) where \(a=2\) and \(b=6\), such that \[\begin{eqnarray*} E(\theta) &=& \frac{a}{a+b}\\ Mode(\theta) &=& \frac{a-1}{a+b-2}, \quad \qquad a,b>1\\ Median(\theta) &=& \frac{a-1/3}{a+b-2/3}, \qquad a,b>1 \ \ \mbox{(approximation)} \end{eqnarray*}\]

a = 2
b = 5
E = a/(a+b)
Mo = (a-1)/(a+b-2)
Me = (a-1/3)/(a+b-2/3)
c(E,Mo,Me)
## [1] 0.2857143 0.2000000 0.2631579

The Bernoulli likelihood and the Beta prior conjugate, which means that the posterior for \(\theta\) also follow a Beta distribution. The conjugacy property makes the Bayesian updating straightforward: \[\begin{eqnarray*} p(\theta|y_{1:n},a,b) &\equiv& p(\theta|n,s_n,a,b) = \frac{\left\{\frac{\Gamma(a+b)}{\Gamma(a)\Gamma(b)}\theta^{a-1}(1-\theta)^{b-1}\right\} \theta^{s_n}(1-\theta)^{n-s_n}}{p(y_{1:n}|a,b)}\\ &\propto& \theta^{a+s_n-1}(1-\theta)^{b+n-s_n-1} \equiv \theta^{a_n-1}(1-\theta)^{b_n-1}, \end{eqnarray*}\] where \[ p(y_{1:n}|n,a,b)=\int_0^1 \frac{\Gamma(a+b)}{\Gamma(a)\Gamma(b)} \theta^{a-1}(1-\theta)^{b-1} \theta^{s_n}(1-\theta)^{n-s_n}d\theta = \frac{\Gamma(a+b)}{\Gamma(a)\Gamma(b)} \frac{\Gamma(a+s_n)\Gamma(b+n-s_n)}{\Gamma(a+b+n)}, \] is the normalizing constant, also known as marginal likelihood or prior predictive, or even simply predictive.

It is easy to see that the posterior distribution of \(\theta\) is Beta with hypeparameters \[ a_n = a + s_n \ \ \ \mbox{and} \ \ \ b_n = b + n - s_n. \] Therefore, \[\begin{eqnarray*} E(\theta|y_{1:n},a,b) &=& \frac{a+s_n}{a+b+n},\\ Mode(\theta|y_{1:n},a,b) &=& \frac{a+s_n-1}{a+b+n-1},\\ Median(\theta|y_{1:n},a,b) &=& \frac{a+s_n-1/3}{a+b+n-2/3}. \end{eqnarray*}\]

a1 = a+s
b1 = b+n-s
E1 = a1/(a1+b1)
Mo1 = (a1-1)/(a1+b1-2)
Me1 = (a1-1/3)/(a1+b1-2/3)
tab = rbind(c(E,Mo,Me),c(E1,Mo1,Me1))
colnames(tab) = c("Mean","Mode","Median")
rownames(tab) = c("Prior","Posterior")
round(tab,3)
##            Mean  Mode Median
## Prior     0.286 0.200  0.263
## Posterior 0.353 0.333  0.347
predictive1 = (gamma(a+b)/(gamma(a)*gamma(b)))*gamma(a1)*gamma(b1)/gamma(a1+b1)
predictive1
## [1] 0.0006243756

1.3 Output: Prior and posterior densities

theta = seq(0,1,length=1000)
par(mfrow=c(1,1))
plot(theta,dbeta(theta,a,b),type="l",lwd=2,ylim=c(0,4),xlab=expression(theta),ylab="Density")
lines(theta,dbeta(theta,a1,b1),col=2,lwd=2)
abline(v=E)
abline(v=Mo,lty=2)
abline(v=Me,lty=3)
abline(v=E1,col=2)
abline(v=Mo1,lty=2,col=2)
abline(v=Me1,lty=3,col=2)
abline(v=mle,col=3,lwd=2)
legend("topright",legend=c("Prior density","Posterior density"),col=1:2,lty=1,bty="n",lwd=2)
legend("right",legend=c("Mean","Mode","Median","MLE"),lty=c(1:3,1),col=c(1,1,1,3),bty="n",lwd=2)

2 Logit Bernoulli model

We now bring to our modeling exercise the covariate \(x_i\) with is also binary with \(x_i=0\) if the age of the respondent \(i\) is less than 30, while \(x_i=1\) if the age is greater than equal to 30. In this way, this more complex model is given by \[ y_i|x_i,\theta \sim Bernoulli(\theta_i), \] where \[ \log\left(\frac{\theta_i}{1-\theta_i}\right) = \alpha + \beta x_i, \] such that \[\begin{eqnarray*} \theta_i &=& \frac{1}{1+\exp\{-\alpha\}} = \pi_0, \qquad \mbox{when} \ \ x_i=0\\ \theta_i &=& \frac{1}{1+\exp\{-(\alpha+\beta)\}} = \pi_1, \qquad \mbox{when} \ \ x_i=1. \end{eqnarray*}\]

In words, \(\theta_i\) can take only two possible values, the probabilities \(\pi_0\) and \(\pi_1\), which are equivalent to the probability \(\theta\) from the iid Bernoulli model.

n  = 10
y  = c(0,0,0,1,0,1,0,1,0,1)
x  = c(1,0,0,1,0,0,0,1,0,1)
n0 = sum(x==0)
n1 = sum(x==1)
s0 = sum(y[x==0])
s1 = sum(y[x==1])
c(n0,n1,s0,s1)
## [1] 6 4 1 3

2.1 Posterior inference

Posterior inference for \(\pi_0\) and \(\pi_1\) (or \(\alpha,\beta\)) is unavailable in closed form. We will us Monte Carlo method (here we use sampling importance resampling, SIR) to be able to approximate the posterior distribution and compute posterior means, modes, medians and other posterior summaries as needed.

2.2 Prior on \((\alpha,\beta)\)

We will assume \(\alpha\) and \(\beta\) are, a priori, independent Gaussians: \[ p(\alpha,\beta)=p(\alpha|\mu_\alpha,\sigma_\alpha^2)p(\beta|\mu_\beta,\sigma_\beta^2), \] with hyperparameters \(\mu_\alpha=-0.7\), \(\mu_\beta=1.4\) and \(\sigma_\mu=\sigma_\beta=1\). The intuition is that these marginal priors induce prior means for \(\pi_0\) and \(\pi_1\) around the following values: \[ \frac{1}{1+\exp\{0.7\}} \approx 1/3 \qquad \mbox{and} \qquad \frac{1}{1+\exp\{0.7-1.4\}} \approx 2/3. \] Below we show draws from the induced prior on \((\pi_0,\pi_1)\).

M     = 10000
alpha = rnorm(M,-0.7,1)
beta  = rnorm(M,1.4,1)

# Induced prior on (pi0,pi1)
pi0 = 1/(1+exp(-alpha))
pi1 = 1/(1+exp(-alpha-beta))

par(mfrow=c(2,2))
plot(alpha,beta,xlab=expression(alpha),ylab=expression(beta))
boxplot(alpha,alpha+beta,outline=FALSE,names=c(expression(alpha),expression(alpha+beta)))
plot(pi0,pi1,xlim=c(0,1),ylim=c(0,1),xlab=expression(pi[0]),ylab=expression(pi[1]))
abline(0,1,col=2,lwd=2)
boxplot(1/(1+exp(-alpha)),1/(1+exp(-alpha-beta)),names=c("Age<30 (i=0)","Age>=30 (i=1)"),ylab=expression(pi[i]))

2.3 Monte Carlo-based posterior inference

Obviously, the posterior distribution of \((\alpha,\beta)\) is of no known form and analytically intractable: \[ p(\alpha,\beta|y_{1:n},n,\mu_\alpha,\sigma_\alpha,\mu_\beta,\sigma_\beta) \propto p(\alpha,\beta|\mu_\alpha,\sigma_\alpha,\mu_\beta,\sigma_\beta)\prod_{i=1}^n \theta_i^{y_i}(1-\theta_i)^{1-y_i}. \] Recall that \(\theta_i = 1/(1+\exp\{-(\alpha+\beta x_i)\})\), for \(i=1,\ldots,n\), so the likelihood is a function of \((\alpha,\beta)\).

As we will see throughout this course, Monte Carlo-based posterior inference has become the most common scheme to be able to accurately approximate highly complex posterior distributions. The the dimension of the parameter is relatively low (here we have \(\alpha\) and \(\beta\), so 2-dimensional) a simple strategy is to sample draws from the prior and resample those draws with weights proportional to the likelihood, which translates into the well-known sampling importance resampling (SIR) scheme. The course notes is full of examples illustrating the implementation, and drawbacks, of SIR-based posterior inference. For now, let us just assume the following piece of code does the magic:

like = rep(0,M)
for (i in 1:M)
  like[i] = pi0[i]^s0*(1-pi0[i])^(n0-s0)*pi1[i]^s1*(1-pi1[i])^(n1-s1)
predictive2 = mean(like)
ind = sample(1:M,size=M,replace=TRUE,prob=like)
pi0.post = pi0[ind]
pi1.post = pi1[ind]
alpha.post = alpha[ind]
beta.post = beta[ind]
predictive2
## [1] 0.002290277

The variables pi0.post and pi1.post are samples (draws) from the joint posterior distribution \(p(\alpha,\beta|y_{1:n},n,\mu_\alpha,\sigma_\alpha,\mu_\beta,\sigma_\beta)\). Similarly for alpha.post and beta.post.

2.4 Graphical output

par(mfrow=c(2,2))
plot(pi0,pi1,xlim=c(0,1),ylim=c(0,1),xlab=expression(pi[0]),ylab=expression(pi[1]))
points(pi0.post,pi1.post,col=2)
legend("bottomright",legend=c("Prior draws","Posterior draws"),col=1:2,pch=16,bty="n")

plot(alpha,beta,xlab=expression(alpha),ylab=expression(beta))
points(alpha.post,beta.post,col=2)
title(paste("Correlation=",round(cor(alpha.post,beta.post),2),sep=""))

plot(density(pi0),ylim=c(0,4),xlim=c(0,1),main="",xlab=expression(pi[0]))
lines(density(pi0.post),col=2)
legend("topright",legend=c(expression(x[i]==0)))

plot(density(pi1),ylim=c(0,3),xlab=expression(pi[1]),xlim=c(0,1),main="")
lines(density(pi1.post),col=2)
legend("topright",legend=c(expression(x[i]==1)))

3 Comparing the two Bernoulli models

par(mfrow=c(1,1))
plot(theta,dbeta(theta,a1,b1),type="l",lwd=2,ylim=c(0,4),
     xlab="Probability of sucess",ylab="Posterior density")
lines(density(pi0[ind]),col=2,lwd=2)
lines(density(pi1[ind]),col=3,lwd=2)
legend("topright",legend=c(expression(theta),expression(pi[0]),expression(pi[1])),lty=1,lwd=2,col=1:3,bty="n")

A few commonly used posterior summaries are as follows:

tab = rbind(
qbeta(c(0.05,0.5,0.95),a1,b1),
quantile(pi0[ind],c(0.05,0.5,0.95)),
quantile(pi1[ind],c(0.05,0.5,0.95)))
rownames(tab) = c("theta","pi0","pi1")
round(tab,2)
##         5%  50%  95%
## theta 0.18 0.35 0.55
## pi0   0.11 0.27 0.50
## pi1   0.36 0.68 0.90

3.1 Bayes factor

Let call the iid Bernoulli model \(M_1\), while the logit Bernoulli model \(M_2\). Then, the Bayes factor is defined as \[ BF_{12} = \frac{p(y_{1:n}|a,b)}{p(y_{1:n}|x_{1:n},\mu_\alpha,\sigma_\alpha,\mu_\beta,\sigma_\beta)} \approx \frac{p(y_{1:n}|a,b)}{p_{SIR}(y_{1:n}|x_{1:n},\mu_\alpha,\sigma_\alpha,\mu_\beta,\sigma_\beta)}, \] where \(p_{SIR}(y_{1:n}|x_{1:n},\mu_\alpha,\sigma_\alpha,\mu_\beta,\sigma_\beta)\) is the SIR-based approximatin to the prior predictive under the logit Bernoulli model. We will explain why that is correct later!

c(predictive1,predictive2)
## [1] 0.0006243756 0.0022902770
BF12 = predictive1/predictive2
BF21 = 1/BF12
BF21
## [1] 3.668108

In a review paper entitled Bayes Factors, that appeared in JASA in 1995 (Volume 90, Issue 430), Robert E. Kass and Adrian E. Raftery suggested the following rule of thumb in order to quantity evidence against \(M_1\):

  • \(B_{21} \in (1,3)\): Not worth more than a bare mention
  • \(B_{21} \in (3,20)\): Positive
  • \(B_{21} \in (20,150)\): Strong
  • \(B_{21} \in (150,\infty)\): Very strong.

Therefore, in our case, the data provides positive evidence against \(M_1\).

LS0tCnRpdGxlOiAiVHdvIEJlcm5vdWxsaSBtb2RlbHMiCmF1dGhvcjogIkhlZGliZXJ0IEZyZWl0YXMgTG9wZXMiCmRhdGU6ICI4LzI3LzIwMjQiCm91dHB1dDoKICBodG1sX2RvY3VtZW50OgogICAgdG9jOiB0cnVlCiAgICB0b2NfZGVwdGg6IDMKICAgIHRvY19jb2xsYXBzZWQ6IHRydWUKICAgIGNvZGVfZG93bmxvYWQ6IHllcwogICAgbnVtYmVyX3NlY3Rpb25zOiB0cnVlCi0tLQoKIyBpaWQgQmVybm91bGxpIG1vZGVsCkhlcmUgd2UgYXNzdW1lIHRoYXQgdGhlIGRhdGEgJHlfezE6bn09XHt5XzEsXGxkb3RzLHlfblx9JCBpcyBtb2RlbGVkIGFzIGEgcmFuZG9tIHNhbXBsZSBmcm9tICRCZXJub3VsbGkoXHRoZXRhKSQuICBJbiBvdXIgY2xhc3Nyb29tIGV4YW1wbGUsIHRoZSBiaW5hcnkgcmFuZG9tIHZhcmlhYmxlICR5X2k9MSQgaWYgaW5kaXZpZHVhbCAkaSQgKGF0dGVuZGluZyB0aGUgY2xhc3MpIGhhcyB0aHJlZSBvciBtb3JlIHNpYmxpbmdzLCBpbmNsdWRpbmcgaGltc2VsZiBvciBoZXJzZWxmLCB3aXRoICR5X2k9MCQsIG90aGVyd2lzZS4gIE9uZSBvZiB0aGUgbWFpbiBnb2FscyBpcyB0byBhY2Nlc3MgdGhlIHVuY2VydGFpbnR5IGFyb3VuZCAkXHRoZXRhJCwgaS5lLiB0aGUgcG9zdGVyaW9yICRwKFx0aGV0YXx5X3sxOm59KSQsIGFuZCB0aGVuIG9idGFpbiAkUHIoeV97bisxfT0xfHlfezE6bn0pJCwgdGhlIHByb2JhYmlsaXR5IHRoYXQgdGhlICQobisxKSQgaW5kaXZpZHVhbCBoYXMgdGhyZWUgb3IgbW9yZSBzaWJsaW5ncywgaW5jbHVkaW5nIGhpbXNlbGYgb3IgaGVyc2VsZi4KCiMjIE1heGltdW0gbGlrZWxpaG9vZCBlc3RpbWF0aW9uCkZyb20gYmFzaWMgbGlrZWxpaG9vZC1iYXNlZCBzdGF0aXN0aWNhbCBpbmZlcmVuY2UsIGl0IGlzIGVhc3kgdG8gc2VlIHRoYXQKJCQKe1x3aWRlaGF0IFx0aGV0YX1fe21sZX0gXGVxdWl2IFxtYm94e2FyZ31cbWF4X3tcdGhldGEgXGluICgwLDEpfSBMKFx0aGV0YTt5X3sxOm59KSwKJCQKd2hlcmUgdGhlIGxpa2VsaWhvb2QgZnVuY3Rpb24gJEwoXHRoZXRhO1xtYm94e2RhdGF9KSQgaXMgZ2l2ZW4gYnkKJCQKTChcdGhldGE7XG1ib3h7ZGF0YX0pID0gXHByb2Rfe2k9MX1ebiBcdGhldGFee3lfaX0oMS1cdGhldGEpXnsxLXlfaX0gPSBcdGhldGFee3Nfbn0oMS1cdGhldGEpXntuLXNfbn0sCiQkCndoZXJlICRzX24gPSBcc3VtX3tpPTF9Xm4geV9pJCBpcyB0aGUgbnVtYmVyIG9mIHN1Y2Vzc2VzIG91dCBvZiAkbiQgKEJlcm5vdWxsaSkgdHJpYWxzLiAgV2UgY29tcHV0ZSB0aGUgTUxFIG9mICRcdGhldGEkIGJhc2VkIG9uICRuPTEwJCBvYnNlcnZhdGlvbnMgYW5kICR5X3sxOjEwfT1cezAsMCwwLDEsMCwxLDAsMSwwLDFcfSQsIHNvICRzX3sxMH09NCBhbmQgJHtcd2lkZWhhdCBcdGhldGF9X3ttbGV9PTQvMTA9MC40JC4KCmBgYHtyfQpuID0gMTAKeSA9IGMoMCwwLDAsMSwwLDEsMCwxLDAsMSkKcyA9IHN1bSh5PT0xKQoKbWxlID0gcy9uCmMobixzLG1sZSkKYGBgCgojIyBQcmlvciwgbGlrZWxpaG9vZCBhbmQgcG9zdGVyaW9yIGZvciAkXHRoZXRhJAoKV2UgaGF2ZSBlbGljaXRlZCBhIHByaW9yIGZvciAkXHRoZXRhJCBpbiBjbGFzcyAod2l0aCB0aGUgaGVscCBvZiBWaXTDs3JpYSkgYW5kIGFycml2ZWQgYXQgdGhlIGZvbGxvd2luZyAKQmV0YSBkaXN0cmlidXRpb246ICAkXHRoZXRhIFxzaW0gQmV0YShhLGIpJCB3aGVyZSAkYT0yJCBhbmQgJGI9NiQsIHN1Y2ggdGhhdApcYmVnaW57ZXFuYXJyYXkqfQpFKFx0aGV0YSkgICAgICAmPSYgXGZyYWN7YX17YStifVxcCk1vZGUoXHRoZXRhKSAgICY9JiBcZnJhY3thLTF9e2ErYi0yfSwgXHF1YWQgXHFxdWFkICBhLGI+MVxcCk1lZGlhbihcdGhldGEpICY9JiBcZnJhY3thLTEvM317YStiLTIvM30sIFxxcXVhZCBhLGI+MSBcIFwgXG1ib3h7KGFwcHJveGltYXRpb24pfQpcZW5ke2VxbmFycmF5Kn0KCmBgYHtyIGZpZy53aWR0aD02LCBmaWcuaGVpZ2h0PTEwLCBmaWcuYWxpZ249J2NlbnRlcid9CmEgPSAyCmIgPSA1CkUgPSBhLyhhK2IpCk1vID0gKGEtMSkvKGErYi0yKQpNZSA9IChhLTEvMykvKGErYi0yLzMpCmMoRSxNbyxNZSkKYGBgCgpUaGUgQmVybm91bGxpIGxpa2VsaWhvb2QgYW5kIHRoZSBCZXRhIHByaW9yIGNvbmp1Z2F0ZSwgd2hpY2ggbWVhbnMgdGhhdCB0aGUgcG9zdGVyaW9yIGZvciAkXHRoZXRhJCBhbHNvIGZvbGxvdyBhIEJldGEgZGlzdHJpYnV0aW9uLiAgVGhlIGNvbmp1Z2FjeSBwcm9wZXJ0eSBtYWtlcyB0aGUgQmF5ZXNpYW4gdXBkYXRpbmcgc3RyYWlnaHRmb3J3YXJkOgpcYmVnaW57ZXFuYXJyYXkqfQpwKFx0aGV0YXx5X3sxOm59LGEsYikgJlxlcXVpdiYgcChcdGhldGF8bixzX24sYSxiKSA9IApcZnJhY3tcbGVmdFx7XGZyYWN7XEdhbW1hKGErYil9e1xHYW1tYShhKVxHYW1tYShiKX1cdGhldGFee2EtMX0oMS1cdGhldGEpXntiLTF9XHJpZ2h0XH0KXHRoZXRhXntzX259KDEtXHRoZXRhKV57bi1zX259fXtwKHlfezE6bn18YSxiKX1cXAomXHByb3B0byYgXHRoZXRhXnthK3Nfbi0xfSgxLVx0aGV0YSlee2Irbi1zX24tMX0gXGVxdWl2IFx0aGV0YV57YV9uLTF9KDEtXHRoZXRhKV57Yl9uLTF9LApcZW5ke2VxbmFycmF5Kn0Kd2hlcmUgCiQkCnAoeV97MTpufXxuLGEsYik9XGludF8wXjEgXGZyYWN7XEdhbW1hKGErYil9e1xHYW1tYShhKVxHYW1tYShiKX0KXHRoZXRhXnthLTF9KDEtXHRoZXRhKV57Yi0xfSBcdGhldGFee3Nfbn0oMS1cdGhldGEpXntuLXNfbn1kXHRoZXRhID0gClxmcmFje1xHYW1tYShhK2IpfXtcR2FtbWEoYSlcR2FtbWEoYil9ClxmcmFje1xHYW1tYShhK3NfbilcR2FtbWEoYituLXNfbil9e1xHYW1tYShhK2Irbil9LAokJAppcyB0aGUgbm9ybWFsaXppbmcgY29uc3RhbnQsIGFsc28ga25vd24gYXMgbWFyZ2luYWwgbGlrZWxpaG9vZCBvciBwcmlvciBwcmVkaWN0aXZlLCBvciBldmVuIHNpbXBseSBwcmVkaWN0aXZlLiAgCgpJdCBpcyBlYXN5IHRvIHNlZSB0aGF0IHRoZSBwb3N0ZXJpb3IgZGlzdHJpYnV0aW9uIG9mICRcdGhldGEkIGlzIEJldGEgd2l0aCBoeXBlcGFyYW1ldGVycwokJAphX24gPSBhICsgc19uIFwgXCBcIFxtYm94e2FuZH0gXCBcIFwgYl9uID0gYiArIG4gLSBzX24uCiQkClRoZXJlZm9yZSwgClxiZWdpbntlcW5hcnJheSp9CkUoXHRoZXRhfHlfezE6bn0sYSxiKSAgICAgICY9JiBcZnJhY3thK3Nfbn17YStiK259LFxcCk1vZGUoXHRoZXRhfHlfezE6bn0sYSxiKSAgICY9JiBcZnJhY3thK3Nfbi0xfXthK2Irbi0xfSxcXApNZWRpYW4oXHRoZXRhfHlfezE6bn0sYSxiKSAmPSYgXGZyYWN7YStzX24tMS8zfXthK2Irbi0yLzN9LgpcZW5ke2VxbmFycmF5Kn0KCmBgYHtyfQphMSA9IGErcwpiMSA9IGIrbi1zCkUxID0gYTEvKGExK2IxKQpNbzEgPSAoYTEtMSkvKGExK2IxLTIpCk1lMSA9IChhMS0xLzMpLyhhMStiMS0yLzMpCnRhYiA9IHJiaW5kKGMoRSxNbyxNZSksYyhFMSxNbzEsTWUxKSkKY29sbmFtZXModGFiKSA9IGMoIk1lYW4iLCJNb2RlIiwiTWVkaWFuIikKcm93bmFtZXModGFiKSA9IGMoIlByaW9yIiwiUG9zdGVyaW9yIikKcm91bmQodGFiLDMpCgpwcmVkaWN0aXZlMSA9IChnYW1tYShhK2IpLyhnYW1tYShhKSpnYW1tYShiKSkpKmdhbW1hKGExKSpnYW1tYShiMSkvZ2FtbWEoYTErYjEpCnByZWRpY3RpdmUxCmBgYAoKIyMgT3V0cHV0OiBQcmlvciBhbmQgcG9zdGVyaW9yIGRlbnNpdGllcwpgYGB7ciBmaWcud2lkdGg9OCwgZmlnLmhlaWdodD02LCBmaWcuYWxpZ249J2NlbnRlcid9CnRoZXRhID0gc2VxKDAsMSxsZW5ndGg9MTAwMCkKcGFyKG1mcm93PWMoMSwxKSkKcGxvdCh0aGV0YSxkYmV0YSh0aGV0YSxhLGIpLHR5cGU9ImwiLGx3ZD0yLHlsaW09YygwLDQpLHhsYWI9ZXhwcmVzc2lvbih0aGV0YSkseWxhYj0iRGVuc2l0eSIpCmxpbmVzKHRoZXRhLGRiZXRhKHRoZXRhLGExLGIxKSxjb2w9Mixsd2Q9MikKYWJsaW5lKHY9RSkKYWJsaW5lKHY9TW8sbHR5PTIpCmFibGluZSh2PU1lLGx0eT0zKQphYmxpbmUodj1FMSxjb2w9MikKYWJsaW5lKHY9TW8xLGx0eT0yLGNvbD0yKQphYmxpbmUodj1NZTEsbHR5PTMsY29sPTIpCmFibGluZSh2PW1sZSxjb2w9Myxsd2Q9MikKbGVnZW5kKCJ0b3ByaWdodCIsbGVnZW5kPWMoIlByaW9yIGRlbnNpdHkiLCJQb3N0ZXJpb3IgZGVuc2l0eSIpLGNvbD0xOjIsbHR5PTEsYnR5PSJuIixsd2Q9MikKbGVnZW5kKCJyaWdodCIsbGVnZW5kPWMoIk1lYW4iLCJNb2RlIiwiTWVkaWFuIiwiTUxFIiksbHR5PWMoMTozLDEpLGNvbD1jKDEsMSwxLDMpLGJ0eT0ibiIsbHdkPTIpCmBgYAoKIyBMb2dpdCBCZXJub3VsbGkgbW9kZWwKV2Ugbm93IGJyaW5nIHRvIG91ciBtb2RlbGluZyBleGVyY2lzZSB0aGUgY292YXJpYXRlICR4X2kkIHdpdGggaXMgYWxzbyBiaW5hcnkgd2l0aCAkeF9pPTAkIGlmIHRoZSBhZ2Ugb2YgdGhlIHJlc3BvbmRlbnQgJGkkIGlzIGxlc3MgdGhhbiAzMCwgd2hpbGUgJHhfaT0xJCBpZiB0aGUgYWdlIGlzIGdyZWF0ZXIgdGhhbiBlcXVhbCB0byAzMC4gIEluIHRoaXMgd2F5LCB0aGlzIG1vcmUgY29tcGxleCBtb2RlbCBpcyBnaXZlbiBieQokJAp5X2l8eF9pLFx0aGV0YSBcc2ltIEJlcm5vdWxsaShcdGhldGFfaSksCiQkCndoZXJlIAokJApcbG9nXGxlZnQoXGZyYWN7XHRoZXRhX2l9ezEtXHRoZXRhX2l9XHJpZ2h0KSA9IFxhbHBoYSArIFxiZXRhIHhfaSwKJCQKc3VjaCB0aGF0IApcYmVnaW57ZXFuYXJyYXkqfQpcdGhldGFfaSAmPSYgXGZyYWN7MX17MStcZXhwXHstXGFscGhhXH19ID0gXHBpXzAsIFxxcXVhZCBcbWJveHt3aGVufSBcIFwgeF9pPTBcXApcdGhldGFfaSAmPSYgXGZyYWN7MX17MStcZXhwXHstKFxhbHBoYStcYmV0YSlcfX0gPSBccGlfMSwgXHFxdWFkIFxtYm94e3doZW59IFwgXCB4X2k9MS4KXGVuZHtlcW5hcnJheSp9CgpJbiB3b3JkcywgJFx0aGV0YV9pJCBjYW4gdGFrZSBvbmx5IHR3byBwb3NzaWJsZSB2YWx1ZXMsIHRoZSBwcm9iYWJpbGl0aWVzICRccGlfMCQgYW5kICRccGlfMSQsIHdoaWNoIGFyZSBlcXVpdmFsZW50IHRvIHRoZSBwcm9iYWJpbGl0eSAkXHRoZXRhJCBmcm9tIHRoZSBpaWQgQmVybm91bGxpIG1vZGVsLgoKYGBge3J9Cm4gID0gMTAKeSAgPSBjKDAsMCwwLDEsMCwxLDAsMSwwLDEpCnggID0gYygxLDAsMCwxLDAsMCwwLDEsMCwxKQpuMCA9IHN1bSh4PT0wKQpuMSA9IHN1bSh4PT0xKQpzMCA9IHN1bSh5W3g9PTBdKQpzMSA9IHN1bSh5W3g9PTFdKQpjKG4wLG4xLHMwLHMxKQpgYGAKCiMjIFBvc3RlcmlvciBpbmZlcmVuY2UKUG9zdGVyaW9yIGluZmVyZW5jZSBmb3IgJFxwaV8wJCBhbmQgJFxwaV8xJCAob3IgJFxhbHBoYSxcYmV0YSQpIGlzIHVuYXZhaWxhYmxlIGluIGNsb3NlZCBmb3JtLiAgV2Ugd2lsbCB1cyBNb250ZSBDYXJsbyBtZXRob2QgKGhlcmUgd2UgdXNlIHNhbXBsaW5nIGltcG9ydGFuY2UgcmVzYW1wbGluZywgU0lSKSB0byBiZSBhYmxlIHRvIGFwcHJveGltYXRlIHRoZSBwb3N0ZXJpb3IgZGlzdHJpYnV0aW9uIGFuZCBjb21wdXRlIHBvc3RlcmlvciBtZWFucywgbW9kZXMsIG1lZGlhbnMgYW5kIG90aGVyIHBvc3RlcmlvciBzdW1tYXJpZXMgYXMgbmVlZGVkLgoKIyMgUHJpb3Igb24gJChcYWxwaGEsXGJldGEpJAoKV2Ugd2lsbCBhc3N1bWUgJFxhbHBoYSQgYW5kICRcYmV0YSQgYXJlLCAqYSBwcmlvcmkqLCBpbmRlcGVuZGVudCBHYXVzc2lhbnM6IAokJApwKFxhbHBoYSxcYmV0YSk9cChcYWxwaGF8XG11X1xhbHBoYSxcc2lnbWFfXGFscGhhXjIpcChcYmV0YXxcbXVfXGJldGEsXHNpZ21hX1xiZXRhXjIpLAokJAp3aXRoIGh5cGVycGFyYW1ldGVycyAkXG11X1xhbHBoYT0tMC43JCwgJFxtdV9cYmV0YT0xLjQkIGFuZCAkXHNpZ21hX1xtdT1cc2lnbWFfXGJldGE9MSQuICBUaGUgaW50dWl0aW9uIGlzIHRoYXQgdGhlc2UgbWFyZ2luYWwgcHJpb3JzIGluZHVjZSBwcmlvciBtZWFucyBmb3IgJFxwaV8wJCBhbmQgJFxwaV8xJCBhcm91bmQgdGhlIGZvbGxvd2luZyB2YWx1ZXM6CiQkClxmcmFjezF9ezErXGV4cFx7MC43XH19IFxhcHByb3ggMS8zIFxxcXVhZCBcbWJveHthbmR9IFxxcXVhZApcZnJhY3sxfXsxK1xleHBcezAuNy0xLjRcfX0gXGFwcHJveCAyLzMuCiQkCkJlbG93IHdlIHNob3cgZHJhd3MgZnJvbSB0aGUgaW5kdWNlZCBwcmlvciBvbiAkKFxwaV8wLFxwaV8xKSQuCmBgYHtyIGZpZy53aWR0aD04LCBmaWcuaGVpZ2h0PTgsIGZpZy5hbGlnbj0nY2VudGVyJ30KTSAgICAgPSAxMDAwMAphbHBoYSA9IHJub3JtKE0sLTAuNywxKQpiZXRhICA9IHJub3JtKE0sMS40LDEpCgojIEluZHVjZWQgcHJpb3Igb24gKHBpMCxwaTEpCnBpMCA9IDEvKDErZXhwKC1hbHBoYSkpCnBpMSA9IDEvKDErZXhwKC1hbHBoYS1iZXRhKSkKCnBhcihtZnJvdz1jKDIsMikpCnBsb3QoYWxwaGEsYmV0YSx4bGFiPWV4cHJlc3Npb24oYWxwaGEpLHlsYWI9ZXhwcmVzc2lvbihiZXRhKSkKYm94cGxvdChhbHBoYSxhbHBoYStiZXRhLG91dGxpbmU9RkFMU0UsbmFtZXM9YyhleHByZXNzaW9uKGFscGhhKSxleHByZXNzaW9uKGFscGhhK2JldGEpKSkKcGxvdChwaTAscGkxLHhsaW09YygwLDEpLHlsaW09YygwLDEpLHhsYWI9ZXhwcmVzc2lvbihwaVswXSkseWxhYj1leHByZXNzaW9uKHBpWzFdKSkKYWJsaW5lKDAsMSxjb2w9Mixsd2Q9MikKYm94cGxvdCgxLygxK2V4cCgtYWxwaGEpKSwxLygxK2V4cCgtYWxwaGEtYmV0YSkpLG5hbWVzPWMoIkFnZTwzMCAoaT0wKSIsIkFnZT49MzAgKGk9MSkiKSx5bGFiPWV4cHJlc3Npb24ocGlbaV0pKQpgYGAKCiMjIE1vbnRlIENhcmxvLWJhc2VkIHBvc3RlcmlvciBpbmZlcmVuY2UKT2J2aW91c2x5LCB0aGUgcG9zdGVyaW9yIGRpc3RyaWJ1dGlvbiBvZiAkKFxhbHBoYSxcYmV0YSkkIGlzIG9mIG5vIGtub3duIGZvcm0gYW5kIGFuYWx5dGljYWxseSBpbnRyYWN0YWJsZToKJCQKcChcYWxwaGEsXGJldGF8eV97MTpufSxuLFxtdV9cYWxwaGEsXHNpZ21hX1xhbHBoYSxcbXVfXGJldGEsXHNpZ21hX1xiZXRhKSBccHJvcHRvIHAoXGFscGhhLFxiZXRhfFxtdV9cYWxwaGEsXHNpZ21hX1xhbHBoYSxcbXVfXGJldGEsXHNpZ21hX1xiZXRhKVxwcm9kX3tpPTF9Xm4gXHRoZXRhX2lee3lfaX0oMS1cdGhldGFfaSleezEteV9pfS4KJCQKUmVjYWxsIHRoYXQgJFx0aGV0YV9pID0gMS8oMStcZXhwXHstKFxhbHBoYStcYmV0YSB4X2kpXH0pJCwgZm9yICRpPTEsXGxkb3RzLG4kLCBzbyB0aGUgbGlrZWxpaG9vZCBpcyBhIGZ1bmN0aW9uIG9mICQoXGFscGhhLFxiZXRhKSQuCgpBcyB3ZSB3aWxsIHNlZSB0aHJvdWdob3V0IHRoaXMgY291cnNlLCBNb250ZSBDYXJsby1iYXNlZCBwb3N0ZXJpb3IgaW5mZXJlbmNlIGhhcyBiZWNvbWUgdGhlIG1vc3QgY29tbW9uIHNjaGVtZSB0byBiZSBhYmxlIHRvIGFjY3VyYXRlbHkgYXBwcm94aW1hdGUgaGlnaGx5IGNvbXBsZXggcG9zdGVyaW9yIGRpc3RyaWJ1dGlvbnMuICBUaGUgdGhlIGRpbWVuc2lvbiBvZiB0aGUgcGFyYW1ldGVyIGlzIHJlbGF0aXZlbHkgbG93IChoZXJlIHdlIGhhdmUgJFxhbHBoYSQgYW5kICRcYmV0YSQsIHNvIDItZGltZW5zaW9uYWwpIGEgc2ltcGxlIHN0cmF0ZWd5IGlzIHRvIHNhbXBsZSBkcmF3cyBmcm9tIHRoZSBwcmlvciBhbmQgcmVzYW1wbGUgdGhvc2UgZHJhd3Mgd2l0aCB3ZWlnaHRzIHByb3BvcnRpb25hbCB0byB0aGUgbGlrZWxpaG9vZCwgd2hpY2ggdHJhbnNsYXRlcyBpbnRvIHRoZSB3ZWxsLWtub3duICpzYW1wbGluZyBpbXBvcnRhbmNlIHJlc2FtcGxpbmcgKFNJUikqIHNjaGVtZS4gIFRoZSBjb3Vyc2Ugbm90ZXMgaXMgZnVsbCBvZiBleGFtcGxlcyBpbGx1c3RyYXRpbmcgdGhlIGltcGxlbWVudGF0aW9uLCBhbmQgZHJhd2JhY2tzLCBvZiBTSVItYmFzZWQgcG9zdGVyaW9yIGluZmVyZW5jZS4gIEZvciBub3csIGxldCB1cyBqdXN0IGFzc3VtZSB0aGUgZm9sbG93aW5nIHBpZWNlIG9mIGNvZGUgZG9lcyB0aGUgbWFnaWM6CgpgYGB7cn0KbGlrZSA9IHJlcCgwLE0pCmZvciAoaSBpbiAxOk0pCiAgbGlrZVtpXSA9IHBpMFtpXV5zMCooMS1waTBbaV0pXihuMC1zMCkqcGkxW2ldXnMxKigxLXBpMVtpXSleKG4xLXMxKQpwcmVkaWN0aXZlMiA9IG1lYW4obGlrZSkKaW5kID0gc2FtcGxlKDE6TSxzaXplPU0scmVwbGFjZT1UUlVFLHByb2I9bGlrZSkKcGkwLnBvc3QgPSBwaTBbaW5kXQpwaTEucG9zdCA9IHBpMVtpbmRdCmFscGhhLnBvc3QgPSBhbHBoYVtpbmRdCmJldGEucG9zdCA9IGJldGFbaW5kXQpwcmVkaWN0aXZlMgpgYGAKClRoZSB2YXJpYWJsZXMgcGkwLnBvc3QgYW5kIHBpMS5wb3N0IGFyZSBzYW1wbGVzIChkcmF3cykgZnJvbSB0aGUgam9pbnQgcG9zdGVyaW9yIGRpc3RyaWJ1dGlvbiAkcChcYWxwaGEsXGJldGF8eV97MTpufSxuLFxtdV9cYWxwaGEsXHNpZ21hX1xhbHBoYSxcbXVfXGJldGEsXHNpZ21hX1xiZXRhKSQuICBTaW1pbGFybHkgZm9yIGFscGhhLnBvc3QgYW5kIGJldGEucG9zdC4KCiMjIEdyYXBoaWNhbCBvdXRwdXQKYGBge3IgZmlnLndpZHRoPTgsIGZpZy5oZWlnaHQ9NywgZmlnLmFsaWduPSdjZW50ZXInfQpwYXIobWZyb3c9YygyLDIpKQpwbG90KHBpMCxwaTEseGxpbT1jKDAsMSkseWxpbT1jKDAsMSkseGxhYj1leHByZXNzaW9uKHBpWzBdKSx5bGFiPWV4cHJlc3Npb24ocGlbMV0pKQpwb2ludHMocGkwLnBvc3QscGkxLnBvc3QsY29sPTIpCmxlZ2VuZCgiYm90dG9tcmlnaHQiLGxlZ2VuZD1jKCJQcmlvciBkcmF3cyIsIlBvc3RlcmlvciBkcmF3cyIpLGNvbD0xOjIscGNoPTE2LGJ0eT0ibiIpCgpwbG90KGFscGhhLGJldGEseGxhYj1leHByZXNzaW9uKGFscGhhKSx5bGFiPWV4cHJlc3Npb24oYmV0YSkpCnBvaW50cyhhbHBoYS5wb3N0LGJldGEucG9zdCxjb2w9MikKdGl0bGUocGFzdGUoIkNvcnJlbGF0aW9uPSIscm91bmQoY29yKGFscGhhLnBvc3QsYmV0YS5wb3N0KSwyKSxzZXA9IiIpKQoKcGxvdChkZW5zaXR5KHBpMCkseWxpbT1jKDAsNCkseGxpbT1jKDAsMSksbWFpbj0iIix4bGFiPWV4cHJlc3Npb24ocGlbMF0pKQpsaW5lcyhkZW5zaXR5KHBpMC5wb3N0KSxjb2w9MikKbGVnZW5kKCJ0b3ByaWdodCIsbGVnZW5kPWMoZXhwcmVzc2lvbih4W2ldPT0wKSkpCgpwbG90KGRlbnNpdHkocGkxKSx5bGltPWMoMCwzKSx4bGFiPWV4cHJlc3Npb24ocGlbMV0pLHhsaW09YygwLDEpLG1haW49IiIpCmxpbmVzKGRlbnNpdHkocGkxLnBvc3QpLGNvbD0yKQpsZWdlbmQoInRvcHJpZ2h0IixsZWdlbmQ9YyhleHByZXNzaW9uKHhbaV09PTEpKSkKYGBgCgoKIyBDb21wYXJpbmcgdGhlIHR3byBCZXJub3VsbGkgbW9kZWxzCgpgYGB7ciBmaWcud2lkdGg9NSwgZmlnLmhlaWdodD01LCBmaWcuYWxpZ249J2NlbnRlcid9CnBhcihtZnJvdz1jKDEsMSkpCnBsb3QodGhldGEsZGJldGEodGhldGEsYTEsYjEpLHR5cGU9ImwiLGx3ZD0yLHlsaW09YygwLDQpLAogICAgIHhsYWI9IlByb2JhYmlsaXR5IG9mIHN1Y2VzcyIseWxhYj0iUG9zdGVyaW9yIGRlbnNpdHkiKQpsaW5lcyhkZW5zaXR5KHBpMFtpbmRdKSxjb2w9Mixsd2Q9MikKbGluZXMoZGVuc2l0eShwaTFbaW5kXSksY29sPTMsbHdkPTIpCmxlZ2VuZCgidG9wcmlnaHQiLGxlZ2VuZD1jKGV4cHJlc3Npb24odGhldGEpLGV4cHJlc3Npb24ocGlbMF0pLGV4cHJlc3Npb24ocGlbMV0pKSxsdHk9MSxsd2Q9Mixjb2w9MTozLGJ0eT0ibiIpCmBgYCAgICAgICAKCkEgZmV3IGNvbW1vbmx5IHVzZWQgcG9zdGVyaW9yIHN1bW1hcmllcyBhcmUgYXMgZm9sbG93czoKYGBge3J9CnRhYiA9IHJiaW5kKApxYmV0YShjKDAuMDUsMC41LDAuOTUpLGExLGIxKSwKcXVhbnRpbGUocGkwW2luZF0sYygwLjA1LDAuNSwwLjk1KSksCnF1YW50aWxlKHBpMVtpbmRdLGMoMC4wNSwwLjUsMC45NSkpKQpyb3duYW1lcyh0YWIpID0gYygidGhldGEiLCJwaTAiLCJwaTEiKQpyb3VuZCh0YWIsMikKYGBgCgojIyBCYXllcyBmYWN0b3IKTGV0IGNhbGwgdGhlIGlpZCBCZXJub3VsbGkgbW9kZWwgJE1fMSQsIHdoaWxlIHRoZSBsb2dpdCBCZXJub3VsbGkgbW9kZWwgJE1fMiQuICBUaGVuLCB0aGUgQmF5ZXMgZmFjdG9yIGlzIGRlZmluZWQgYXMKJCQKQkZfezEyfSA9IFxmcmFje3AoeV97MTpufXxhLGIpfXtwKHlfezE6bn18eF97MTpufSxcbXVfXGFscGhhLFxzaWdtYV9cYWxwaGEsXG11X1xiZXRhLFxzaWdtYV9cYmV0YSl9IFxhcHByb3gKXGZyYWN7cCh5X3sxOm59fGEsYil9e3Bfe1NJUn0oeV97MTpufXx4X3sxOm59LFxtdV9cYWxwaGEsXHNpZ21hX1xhbHBoYSxcbXVfXGJldGEsXHNpZ21hX1xiZXRhKX0sCiQkCndoZXJlICRwX3tTSVJ9KHlfezE6bn18eF97MTpufSxcbXVfXGFscGhhLFxzaWdtYV9cYWxwaGEsXG11X1xiZXRhLFxzaWdtYV9cYmV0YSkkIGlzIHRoZSBTSVItYmFzZWQgYXBwcm94aW1hdGluIHRvIHRoZSBwcmlvciBwcmVkaWN0aXZlIHVuZGVyIHRoZSBsb2dpdCBCZXJub3VsbGkgbW9kZWwuICBXZSB3aWxsIGV4cGxhaW4gd2h5IHRoYXQgaXMgY29ycmVjdCBsYXRlciEKCmBgYHtyfQpjKHByZWRpY3RpdmUxLHByZWRpY3RpdmUyKQpCRjEyID0gcHJlZGljdGl2ZTEvcHJlZGljdGl2ZTIKQkYyMSA9IDEvQkYxMgpCRjIxCmBgYAoKSW4gYSByZXZpZXcgcGFwZXIgZW50aXRsZWQgKkJheWVzIEZhY3RvcnMqLCB0aGF0IGFwcGVhcmVkIGluIEpBU0EgaW4gMTk5NSAoVm9sdW1lIDkwLCBJc3N1ZSA0MzApLCBSb2JlcnQgRS4gS2FzcyBhbmQgQWRyaWFuIEUuIFJhZnRlcnkgc3VnZ2VzdGVkIHRoZSBmb2xsb3dpbmcgcnVsZSBvZiB0aHVtYiBpbiBvcmRlciB0byBxdWFudGl0eSBldmlkZW5jZSBhZ2FpbnN0ICRNXzEkOgoKKiAkQl97MjF9IFxpbiAoMSwzKSQ6IE5vdCB3b3J0aCBtb3JlIHRoYW4gYSBiYXJlIG1lbnRpb24gCiogJEJfezIxfSBcaW4gKDMsMjApJDogUG9zaXRpdmUgCiogJEJfezIxfSBcaW4gKDIwLDE1MCkkOiBTdHJvbmcKKiAkQl97MjF9IFxpbiAoMTUwLFxpbmZ0eSkkOiBWZXJ5IHN0cm9uZy4KClRoZXJlZm9yZSwgaW4gb3VyIGNhc2UsIHRoZSBkYXRhIHByb3ZpZGVzIHBvc2l0aXZlIGV2aWRlbmNlIGFnYWluc3QgJE1fMSQuCg==