Assignment Objectives

  • Comprehend the likelihood function and its properties.

  • Master the maximum likelihood estimation framework and required components.

  • Understand the plug-in principle underlying MLE.

  • Implement maximum likelihood estimation procedures in R.


Gamma Distribution Revisited

Let \(X\) be the two parameter Gamma random variable with density function

\[ f(x \mid \alpha, \beta) = \frac{1}{\Gamma(\alpha)\beta^\alpha} x^{\alpha-1} e^{-x/\beta} \ \ \text{for} \ \ x > 0, \] L(α,β∣x1​,…,xn​)=i=1∏n​Γ(α)βα1​xiα−1​e−xi​/β.

where with \(\alpha > 0\) (shape), \(\beta>0\) (scale), and

\[ \Gamma(\alpha) = \int_{0}^{\infty} t^{\alpha-1} e^{-t} \, dt, \quad \alpha > 0. \]

\(\Gamma(x)\) can be computed in R using the gamma() function. The derivative of \(\Gamma(x)\) are given respectively by

\[ \Gamma^\prime(z) = \Gamma (z)\psi_0(z) \]

where \(\psi_0(z) = \frac{d}{dz} \ln \Gamma{z}\). In R, the digamma function \(\psi_0(z)\) is evaluated by digamma().


This assignment focuses on finding maximum likelihood estimate of parameters \(\alpha\) and \(\beta\) based on a real-world application data set.


Question 1: Derive gradient (first order partial derivative) of likelihood function

Assume that \(\{x_1, x_2, \cdots, x_n \} \to \text{ gamma }(\alpha, \beta)\) with density function given by

\[ f(x \mid \alpha, \beta) = \frac{1}{\Gamma(\alpha)\beta^\alpha} x^{\alpha-1} e^{-x/\beta} \ \ \text{for} \ \ x > 0, \]

Derive the gradient of the likelihood function with respect to the gamma distribution parameters \(\alpha\) and \(\beta\). To this end,

a). Write out the full likelihood function based on the given data and the density function provided above.

The likelihood function is \[ L(\alpha,\beta \mid x_1,\ldots,x_n)=\prod_{i=1}^{n}\frac{1}{\Gamma(\alpha)\beta^{\alpha}}\, x_i^{\alpha-1}\, e^{-x_i/\beta}. \] Taking logs, the log-likelihood is \[ \ell(\alpha,\beta)=- n\log\Gamma(\alpha)- n\alpha\log\beta+(\alpha-1)\sum_{i=1}^{n}\log x_i- \frac{1}{\beta}\sum_{i=1}^{n} x_i. \]

b). Derive the score functions (the gradient of the log-likelihood) from the full likelihood function in part (a).

Using \(\dfrac{d}{d\alpha}\log\Gamma(\alpha)=\psi_0(\alpha)\), the score for \(\alpha\) is

\[ \frac{\partial \ell(\alpha,\beta)}{\partial \alpha} = -n\psi_0(\alpha) -n\log\beta +\sum_{i=1}^{n}\log x_i. \]

The score for \(\beta\) is

\[ \frac{\partial \ell(\alpha,\beta)}{\partial \beta} = -\frac{n\alpha}{\beta} +\frac{1}{\beta^2}\sum_{i=1}^{n}x_i. \]


Question 2: Birth data set

The following R code reads in a data set containing, for each of 7 days, the lengths of time in hours spent by women in the delivery suite while giving birth (without a ceasarian section) at John Radcliffe Hospital in Oxford, England. The data are taken from Davison (Statistical Models. Cambridge University Press, 2003).

2.1, 3.4, 4.25, 5.6, 6.4, 7.3, 8.5, 8.75, 8.9, 9.5, 9.75, 10, 10.4, 10.4, 16, 19,
4, 4.1, 5, 5.5, 5.7, 6.5, 7.25, 7.3, 7.5, 8.2, 8.5, 9.75, 11, 11.2, 15, 16.5, 2.6, 
3.6, 3.6, 6.4, 6.8, 7.5, 7.5, 8.25, 8.5, 10.4, 10.75, 14.25, 14.5, 1.5, 4.7, 4.7, 
7.2, 7.25, 8.1, 8.5, 9.2, 9.5, 10.7, 11.5, 2.5, 2.5, 3.4, 4.2, 5.9, 6.25, 7.3, 7.5, 
7.8, 8.3, 8.3, 10.25, 12.9, 14.3, 4, 4, 5.25, 6.1, 6.5, 6.9, 7, 8.45, 9.25, 10.1, 
10.2, 12.75, 14.6, 2, 2.7, 2.75, 3.4, 4.2, 4.3, 4.9, 6.25, 7, 9, 9.25, 10.7

Assume the data are generated from a gamma distribution. The objective is to use these data and the designated algorithm to find the maximum likelihood estimates (MLEs) of the parameters \(\alpha\) and \(\beta\).

a). Find the MLEs of \(\alpha\) and \(\beta\), denoted by \(\hat{\alpha}\) and \(\hat{\beta}\), using gradient-based optimization via the R function optim() with the gradient vector derived in Question 1.

# Birth time data (hours)
x <- c(
  2.1, 3.4, 4.25, 5.6, 6.4, 7.3, 8.5, 8.75, 8.9, 9.5, 9.75, 10, 10.4, 10.4, 16, 19,
  4, 4.1, 5, 5.5, 5.7, 6.5, 7.25, 7.3, 7.5, 8.2, 8.5, 9.75, 11, 11.2, 15, 16.5, 2.6,
  3.6, 3.6, 6.4, 6.8, 7.5, 7.5, 8.25, 8.5, 10.4, 10.75, 14.25, 14.5, 1.5, 4.7, 4.7,
  7.2, 7.25, 8.1, 8.5, 9.2, 9.5, 10.7, 11.5, 2.5, 2.5, 3.4, 4.2, 5.9, 6.25, 7.3, 7.5,
  7.8, 8.3, 8.3, 10.25, 12.9, 14.3, 4, 4, 5.25, 6.1, 6.5, 6.9, 7, 8.45, 9.25, 10.1,
  10.2, 12.75, 14.6, 2, 2.7, 2.75, 3.4, 4.2, 4.3, 4.9, 6.25, 7, 9, 9.25, 10.7
)

n <- length(x)
sx <- sum(x)
slogx <- sum(log(x))
xbar <- mean(x)
s2 <- var(x)   # sample variance (uses n-1 denominator)

# Negative log-likelihood for Gamma(shape=alpha, scale=beta)
negloglik_gamma <- function(par, x) {
  alpha <- par[1]
  beta  <- par[2]
  if (alpha <= 0 || beta <= 0) return(Inf)

  n <- length(x)
  ll <- -n * lgamma(alpha) - n * alpha * log(beta) + (alpha - 1) * sum(log(x)) - (1 / beta) * sum(x)
  return(-ll)  # negative for minimization
}

# Gradient of negative log-likelihood ( = - score )
neggrad_gamma <- function(par, x) {
  alpha <- par[1]
  beta  <- par[2]
  n <- length(x)

  dlda <- -n * digamma(alpha) - n * log(beta) + sum(log(x))
  dldb <- -(n * alpha) / beta + sum(x) / (beta^2)

  return(c(-dlda, -dldb))
}

# Starting values: use Method of Moments (good, stable starting point)
alpha_start <- xbar^2 / s2
beta_start  <- s2 / xbar
start <- c(alpha_start, beta_start)

mle_fit <- optim(
  par = start,
  fn  = negloglik_gamma,
  gr  = neggrad_gamma,
  x   = x,
  method = "L-BFGS-B",
  lower = c(1e-8, 1e-8)   # enforce positivity
)

alpha_hat <- mle_fit$par[1]
beta_hat  <- mle_fit$par[2]

data.frame(
  alpha_hat = alpha_hat,
  beta_hat  = beta_hat,
  convergence = mle_fit$convergence
)
  alpha_hat beta_hat convergence
1  4.387855 1.760122           0

b). Apply the method of moments to obtain estimators for \(\alpha\) and \(\beta\). Denote these moment estimators as \(\tilde{\alpha}\) and \(\tilde{\beta}\).

alpha_tilde <- xbar^2 / s2
beta_tilde  <- s2 / xbar

data.frame(alpha_tilde = alpha_tilde, beta_tilde = beta_tilde)
  alpha_tilde beta_tilde
1    4.685073    1.64846

c). Conduct a brief literature review comparing the method of moments estimation (MME) and maximum likelihood estimation (MLE). Synthesize the key advantages and limitations of each, concluding with a practical recommendation.

Answer: The Method of Moments (MME) estimates parameters by matching sample moments (like the mean and variance) to the theoretical moments of the distribution. It is simple to compute and easy to understand, but it may not always provide the most efficient estimates.

Maximum Likelihood Estimation (MLE) chooses the parameter values that make the observed data most likely under the assumed model. When the model is appropriate and the sample size is large, MLE typically produces more accurate and statistically efficient estimates. However, it often requires numerical optimization.

In practice, MME is useful for quick estimation and as starting values, while MLE is generally preferred for final inference due to its stronger theoretical properties.

LS0tDQp0aXRsZTogIkFzc2lnbm1lbnQgNTogTWF4aW11bSBMaWtlbGlob29kIEVzdGltYXRpb24iDQphdXRob3I6ICJZb3VyIE5hbWU6IFhpYW95aW5nIE1hIg0KZGF0ZTogIiBEdWU6IDAzLzAzLzIwMjYiDQpvdXRwdXQ6DQogIGh0bWxfZG9jdW1lbnQ6IA0KICAgIHRvYzogeWVzDQogICAgdG9jX2RlcHRoOiA0DQogICAgdG9jX2Zsb2F0OiB5ZXMNCiAgICBudW1iZXJfc2VjdGlvbnM6IG5vDQogICAgdG9jX2NvbGxhcHNlZDogeWVzDQogICAgY29kZV9mb2xkaW5nOiBoaWRlDQogICAgY29kZV9kb3dubG9hZDogeWVzDQogICAgc21vb3RoX3Njcm9sbDogeWVzDQogICAgdGhlbWU6IGx1bWVuDQogIHBkZl9kb2N1bWVudDogDQogICAgdG9jOiB5ZXMNCiAgICB0b2NfZGVwdGg6IDQNCiAgICBmaWdfY2FwdGlvbjogeWVzDQogICAgbnVtYmVyX3NlY3Rpb25zOiB5ZXMNCiAgICBmaWdfd2lkdGg6IDMNCiAgICBmaWdfaGVpZ2h0OiAzDQogIHdvcmRfZG9jdW1lbnQ6IA0KICAgIHRvYzogeWVzDQogICAgdG9jX2RlcHRoOiA0DQogICAgZmlnX2NhcHRpb246IHllcw0KICAgIGtlZXBfbWQ6IHllcw0KZWRpdG9yX29wdGlvbnM6IA0KICBjaHVua19vdXRwdXRfdHlwZTogaW5saW5lDQotLS0NCg0KYGBge2NzcywgZWNobyA9IEZBTFNFfQ0KI1RPQzo6YmVmb3JlIHsNCiAgY29udGVudDogIlRhYmxlIG9mIENvbnRlbnRzIjsNCiAgZm9udC13ZWlnaC86IGJvbGQ7DQogIGZvbnQtc2l6ZTogMS4yZW07DQogIGRpc3BsYXk6IGJsb2NrOw0KICBjb2xvcjogbmF2eTsNCiAgbWFyZ2luLWJvdHRvbTogMTBweDsNCn0NCg0KDQpkaXYjVE9DIGxpIHsgICAgIC8qIHRhYmxlIG9mIGNvbnRlbnQgICovDQogICAgbGlzdC1zdHlsZTp1cHBlci1yb21hbjsNCiAgICBiYWNrZ3JvdW5kLWltYWdlOm5vbmU7DQogICAgYmFja2dyb3VuZC1yZXBlYXQ6bm9uZTsNCiAgICBiYWNrZ3JvdW5kLXBvc2l0aW9uOjA7DQp9DQoNCmgxLnRpdGxlIHsgICAgLyogbGV2ZWwgMSBoZWFkZXIgb2YgdGl0bGUgICovDQogIGZvbnQtc2l6ZTogMjJweDsNCiAgZm9udC13ZWlnaHQ6IGJvbGQ7DQogIGNvbG9yOiBEYXJrUmVkOw0KICB0ZXh0LWFsaWduOiBjZW50ZXI7DQogIGZvbnQtZmFtaWx5OiAiR2lsbCBTYW5zIiwgc2Fucy1zZXJpZjsNCn0NCg0KaDQuYXV0aG9yIHsgLyogSGVhZGVyIDQgLSBhbmQgdGhlIGF1dGhvciBhbmQgZGF0YSBoZWFkZXJzIHVzZSB0aGlzIHRvbyAgKi8NCiAgZm9udC1zaXplOiAxNXB4Ow0KICBmb250LXdlaWdodDogYm9sZDsNCiAgZm9udC1mYW1pbHk6IHN5c3RlbS11aTsNCiAgY29sb3I6IG5hdnk7DQogIHRleHQtYWxpZ246IGNlbnRlcjsNCn0NCg0KaDQuZGF0ZSB7IC8qIEhlYWRlciA0IC0gYW5kIHRoZSBhdXRob3IgYW5kIGRhdGEgaGVhZGVycyB1c2UgdGhpcyB0b28gICovDQogIGZvbnQtc2l6ZTogMThweDsNCiAgZm9udC13ZWlnaHQ6IGJvbGQ7DQogIGZvbnQtZmFtaWx5OiAiR2lsbCBTYW5zIiwgc2Fucy1zZXJpZjsNCiAgY29sb3I6IERhcmtCbHVlOw0KICB0ZXh0LWFsaWduOiBjZW50ZXI7DQp9DQoNCmgxIHsgLyogSGVhZGVyIDEgLSBhbmQgdGhlIGF1dGhvciBhbmQgZGF0YSBoZWFkZXJzIHVzZSB0aGlzIHRvbyAgKi8NCiAgICBmb250LXNpemU6IDIwcHg7DQogICAgZm9udC13ZWlnaHQ6IGJvbGQ7DQogICAgZm9udC1mYW1pbHk6ICJUaW1lcyBOZXcgUm9tYW4iLCBUaW1lcywgc2VyaWY7DQogICAgY29sb3I6IGRhcmtyZWQ7DQogICAgdGV4dC1hbGlnbjogY2VudGVyOw0KfQ0KDQpoMiB7IC8qIEhlYWRlciAyIC0gYW5kIHRoZSBhdXRob3IgYW5kIGRhdGEgaGVhZGVycyB1c2UgdGhpcyB0b28gICovDQogICAgZm9udC1zaXplOiAxOHB4Ow0KICAgIGZvbnQtd2VpZ2h0OiBib2xkOw0KICAgIGZvbnQtZmFtaWx5OiAiVGltZXMgTmV3IFJvbWFuIiwgVGltZXMsIHNlcmlmOw0KICAgIGNvbG9yOiBuYXZ5Ow0KICAgIHRleHQtYWxpZ246IGxlZnQ7DQp9DQoNCmgzIHsgLyogSGVhZGVyIDMgLSBhbmQgdGhlIGF1dGhvciBhbmQgZGF0YSBoZWFkZXJzIHVzZSB0aGlzIHRvbyAgKi8NCiAgICBmb250LXNpemU6IDE2cHg7DQogICAgZm9udC13ZWlnaHQ6IGJvbGQ7DQogICAgZm9udC1mYW1pbHk6ICJUaW1lcyBOZXcgUm9tYW4iLCBUaW1lcywgc2VyaWY7DQogICAgY29sb3I6IG5hdnk7DQogICAgdGV4dC1hbGlnbjogbGVmdDsNCn0NCg0KaDQgeyAvKiBIZWFkZXIgNCAtIGFuZCB0aGUgYXV0aG9yIGFuZCBkYXRhIGhlYWRlcnMgdXNlIHRoaXMgdG9vICAqLw0KICAgIGZvbnQtc2l6ZTogMTRweDsNCiAgZm9udC13ZWlnaHQ6IGJvbGQ7DQogICAgZm9udC1mYW1pbHk6ICJUaW1lcyBOZXcgUm9tYW4iLCBUaW1lcywgc2VyaWY7DQogICAgY29sb3I6IGRhcmtyZWQ7DQogICAgdGV4dC1hbGlnbjogbGVmdDsNCn0NCg0KLyogQWRkIGRvdHMgYWZ0ZXIgbnVtYmVyZWQgaGVhZGVycyAqLw0KLmhlYWRlci1zZWN0aW9uLW51bWJlcjo6YWZ0ZXIgew0KICBjb250ZW50OiAiLiI7DQoNCmJvZHkgeyBiYWNrZ3JvdW5kLWNvbG9yOndoaXRlOyB9DQoNCi5oaWdobGlnaHRtZSB7IGJhY2tncm91bmQtY29sb3I6eWVsbG93OyB9DQoNCnAgeyBiYWNrZ3JvdW5kLWNvbG9yOndoaXRlOyB9DQoNCn0NCmBgYA0KDQpgYGB7ciBzZXR1cCwgaW5jbHVkZT1GQUxTRX0NCiMgY29kZSBjaHVuayBzcGVjaWZpZXMgd2hldGhlciB0aGUgUiBjb2RlLCB3YXJuaW5ncywgYW5kIG91dHB1dCANCiMgd2lsbCBiZSBpbmNsdWRlZCBpbiB0aGUgb3V0cHV0IGZpbGVzLg0KaWYgKCFyZXF1aXJlKCJrbml0ciIpKSB7DQogICBpbnN0YWxsLnBhY2thZ2VzKCJrbml0ciIpDQogICBsaWJyYXJ5KGtuaXRyKQ0KfQ0KaWYgKCFyZXF1aXJlKCJwYW5kZXIiKSkgew0KICAgaW5zdGFsbC5wYWNrYWdlcygicGFuZGVyIikNCiAgIGxpYnJhcnkocGFuZGVyKQ0KfQ0KaWYgKCFyZXF1aXJlKCJnZ3Bsb3QyIikpIHsNCiAgaW5zdGFsbC5wYWNrYWdlcygiZ2dwbG90MiIpDQogIGxpYnJhcnkoZ2dwbG90MikNCn0NCmlmICghcmVxdWlyZSgidGlkeXZlcnNlIikpIHsNCiAgaW5zdGFsbC5wYWNrYWdlcygidGlkeXZlcnNlIikNCiAgbGlicmFyeSh0aWR5dmVyc2UpDQp9DQoNCmlmICghcmVxdWlyZSgicGxvdGx5IikpIHsNCiAgaW5zdGFsbC5wYWNrYWdlcygicGxvdGx5IikNCiAgbGlicmFyeShwbG90bHkpDQp9DQojIyMjDQprbml0cjo6b3B0c19jaHVuayRzZXQoZWNobyA9IFRSVUUsICAgICAgICMgaW5jbHVkZSBjb2RlIGNodW5rIGluIHRoZSBvdXRwdXQgZmlsZQ0KICAgICAgICAgICAgICAgICAgICAgIHdhcm5pbmcgPSBGQUxTRSwgICAjIHNvbWV0aW1lcywgeW91IGNvZGUgbWF5IHByb2R1Y2Ugd2FybmluZyBtZXNzYWdlcywNCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIyB5b3UgY2FuIGNob29zZSB0byBpbmNsdWRlIHRoZSB3YXJuaW5nIG1lc3NhZ2VzIGluDQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICMgdGhlIG91dHB1dCBmaWxlLiANCiAgICAgICAgICAgICAgICAgICAgICByZXN1bHRzID0gVFJVRSwgICAgIyB5b3UgY2FuIGFsc28gZGVjaWRlIHdoZXRoZXIgdG8gaW5jbHVkZSB0aGUgb3V0cHV0DQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICMgaW4gdGhlIG91dHB1dCBmaWxlLg0KICAgICAgICAgICAgICAgICAgICAgIG1lc3NhZ2UgPSBGQUxTRSwNCiAgICAgICAgICAgICAgICAgICAgICBjb21tZW50ID0gTkENCiAgICAgICAgICAgICAgICAgICAgICApICANCmBgYA0KIA0KXA0KIA0KIyMgKipBc3NpZ25tZW50IE9iamVjdGl2ZXMqKiANCg0KKiBDb21wcmVoZW5kIHRoZSBsaWtlbGlob29kIGZ1bmN0aW9uIGFuZCBpdHMgcHJvcGVydGllcy4NCg0KKiBNYXN0ZXIgdGhlIG1heGltdW0gbGlrZWxpaG9vZCBlc3RpbWF0aW9uIGZyYW1ld29yayBhbmQgcmVxdWlyZWQgY29tcG9uZW50cy4NCg0KKiBVbmRlcnN0YW5kIHRoZSBwbHVnLWluIHByaW5jaXBsZSB1bmRlcmx5aW5nIE1MRS4NCg0KKiBJbXBsZW1lbnQgbWF4aW11bSBsaWtlbGlob29kIGVzdGltYXRpb24gcHJvY2VkdXJlcyBpbiBSLg0KDQpcDQoNCioqR2FtbWEgRGlzdHJpYnV0aW9uIFJldmlzaXRlZCoqDQoNCkxldCAkWCQgYmUgdGhlIHR3byBwYXJhbWV0ZXIgR2FtbWEgcmFuZG9tIHZhcmlhYmxlIHdpdGggZGVuc2l0eSBmdW5jdGlvbg0KDQokJA0KZih4IFxtaWQgXGFscGhhLCBcYmV0YSkgPSBcZnJhY3sxfXtcR2FtbWEoXGFscGhhKVxiZXRhXlxhbHBoYX0geF57XGFscGhhLTF9IGVeey14L1xiZXRhfSAgXCBcIFx0ZXh0e2Zvcn0gXCBcICB4ID4gMCwNCiQkDQpMKM6xLM6y4oijeDHigIss4oCmLHhu4oCLKT1pPTHiiI9u4oCLzpMozrEpzrLOsTHigIt4ac6x4oiSMeKAi2XiiJJ4aeKAiy/Osi4NCg0Kd2hlcmUgd2l0aCAkXGFscGhhID4gMCQgKHNoYXBlKSwgJFxiZXRhPjAkIChzY2FsZSksIGFuZA0KDQokJA0KXEdhbW1hKFxhbHBoYSkgPSBcaW50X3swfV57XGluZnR5fSB0XntcYWxwaGEtMX0gZV57LXR9IFwsIGR0LCBccXVhZCBcYWxwaGEgPiAwLg0KJCQNCg0KJFxHYW1tYSh4KSQgY2FuIGJlIGNvbXB1dGVkIGluIFIgdXNpbmcgdGhlIGBnYW1tYSgpYCBmdW5jdGlvbi4gVGhlIGRlcml2YXRpdmUgb2YgJFxHYW1tYSh4KSQgYXJlIGdpdmVuIHJlc3BlY3RpdmVseSBieQ0KDQokJA0KXEdhbW1hXlxwcmltZSh6KSA9IFxHYW1tYSAoeilccHNpXzAoeikNCiQkDQoNCndoZXJlICRccHNpXzAoeikgPSBcZnJhY3tkfXtken0gXGxuIFxHYW1tYXt6fSQuIEluIFIsIHRoZSBkaWdhbW1hIGZ1bmN0aW9uICRccHNpXzAoeikkIGlzIGV2YWx1YXRlZCBieSBgZGlnYW1tYSgpYC4NCg0KDQoNClwNCg0KPGZvbnQgY29sb3IgPSAiYmx1ZSI+VGhpcyBhc3NpZ25tZW50IGZvY3VzZXMgb24gZmluZGluZyBtYXhpbXVtIGxpa2VsaWhvb2QgZXN0aW1hdGUgb2YgcGFyYW1ldGVycyAkXGFscGhhJCBhbmQgJFxiZXRhJCBiYXNlZCBvbiBhIHJlYWwtd29ybGQgYXBwbGljYXRpb24gZGF0YSBzZXQuPC9mb250Pg0KDQoNClwNCg0KIyMgKipRdWVzdGlvbiAxOiBEZXJpdmUgZ3JhZGllbnQgKGZpcnN0IG9yZGVyIHBhcnRpYWwgZGVyaXZhdGl2ZSkgb2YgbGlrZWxpaG9vZCBmdW5jdGlvbioqDQoNCkFzc3VtZSB0aGF0ICRce3hfMSwgeF8yLCBcY2RvdHMsIHhfbiBcfSBcdG8gXHRleHR7IGdhbW1hIH0oXGFscGhhLCBcYmV0YSkkIHdpdGggZGVuc2l0eSBmdW5jdGlvbiBnaXZlbiBieQ0KDQokJA0KZih4IFxtaWQgXGFscGhhLCBcYmV0YSkgPSBcZnJhY3sxfXtcR2FtbWEoXGFscGhhKVxiZXRhXlxhbHBoYX0geF57XGFscGhhLTF9IGVeey14L1xiZXRhfSAgXCBcIFx0ZXh0e2Zvcn0gXCBcICB4ID4gMCwNCiQkDQoNCkRlcml2ZSB0aGUgZ3JhZGllbnQgb2YgdGhlIGxpa2VsaWhvb2QgZnVuY3Rpb24gd2l0aCByZXNwZWN0IHRvIHRoZSBnYW1tYSBkaXN0cmlidXRpb24gcGFyYW1ldGVycyAkXGFscGhhJCBhbmQgJFxiZXRhJC4gVG8gdGhpcyBlbmQsDQoNCg0KYSkuIFdyaXRlIG91dCB0aGUgZnVsbCBsaWtlbGlob29kIGZ1bmN0aW9uIGJhc2VkIG9uIHRoZSBnaXZlbiBkYXRhIGFuZCB0aGUgZGVuc2l0eSBmdW5jdGlvbiBwcm92aWRlZCBhYm92ZS4NCg0KVGhlIGxpa2VsaWhvb2QgZnVuY3Rpb24gaXMNCiQkDQpMKFxhbHBoYSxcYmV0YSBcbWlkIHhfMSxcbGRvdHMseF9uKT1ccHJvZF97aT0xfV57bn1cZnJhY3sxfXtcR2FtbWEoXGFscGhhKVxiZXRhXntcYWxwaGF9fVwsIHhfaV57XGFscGhhLTF9XCwgZV57LXhfaS9cYmV0YX0uDQokJA0KVGFraW5nIGxvZ3MsIHRoZSBsb2ctbGlrZWxpaG9vZCBpcw0KJCQNClxlbGwoXGFscGhhLFxiZXRhKT0tIG5cbG9nXEdhbW1hKFxhbHBoYSktIG5cYWxwaGFcbG9nXGJldGErKFxhbHBoYS0xKVxzdW1fe2k9MX1ee259XGxvZyB4X2ktIFxmcmFjezF9e1xiZXRhfVxzdW1fe2k9MX1ee259IHhfaS4NCiQkDQoNCg0KYikuIERlcml2ZSB0aGUgc2NvcmUgZnVuY3Rpb25zICh0aGUgZ3JhZGllbnQgb2YgdGhlIGxvZy1saWtlbGlob29kKSBmcm9tIHRoZSBmdWxsIGxpa2VsaWhvb2QgZnVuY3Rpb24gaW4gcGFydCAoYSkuDQoNClVzaW5nICRcZGZyYWN7ZH17ZFxhbHBoYX1cbG9nXEdhbW1hKFxhbHBoYSk9XHBzaV8wKFxhbHBoYSkkLCB0aGUgc2NvcmUgZm9yICRcYWxwaGEkIGlzDQoNCiQkDQpcZnJhY3tccGFydGlhbCBcZWxsKFxhbHBoYSxcYmV0YSl9e1xwYXJ0aWFsIFxhbHBoYX0NCj0NCi1uXHBzaV8wKFxhbHBoYSkNCi1uXGxvZ1xiZXRhDQorXHN1bV97aT0xfV57bn1cbG9nIHhfaS4NCiQkDQoNClRoZSBzY29yZSBmb3IgJFxiZXRhJCBpcw0KDQokJA0KXGZyYWN7XHBhcnRpYWwgXGVsbChcYWxwaGEsXGJldGEpfXtccGFydGlhbCBcYmV0YX0NCj0NCi1cZnJhY3tuXGFscGhhfXtcYmV0YX0NCitcZnJhY3sxfXtcYmV0YV4yfVxzdW1fe2k9MX1ee259eF9pLg0KJCQNCg0KXA0KDQojIyAqKlF1ZXN0aW9uIDI6IEJpcnRoIGRhdGEgc2V0KioNCg0KVGhlIGZvbGxvd2luZyBSIGNvZGUgcmVhZHMgaW4gYSBkYXRhIHNldCBjb250YWluaW5nLCBmb3IgZWFjaCBvZiA3IGRheXMsIHRoZSBsZW5ndGhzIG9mIHRpbWUgaW4gaG91cnMgc3BlbnQgYnkNCndvbWVuIGluIHRoZSBkZWxpdmVyeSBzdWl0ZSB3aGlsZSBnaXZpbmcgYmlydGggKHdpdGhvdXQgYSBjZWFzYXJpYW4gc2VjdGlvbikgYXQgSm9obiBSYWRjbGlmZmUgSG9zcGl0YWwgaW4NCk94Zm9yZCwgRW5nbGFuZC4gVGhlIGRhdGEgYXJlIHRha2VuIGZyb20gRGF2aXNvbiAoU3RhdGlzdGljYWwgTW9kZWxzLiBDYW1icmlkZ2UgVW5pdmVyc2l0eSBQcmVzcywgMjAwMykuDQoNCmBgYA0KMi4xLCAzLjQsIDQuMjUsIDUuNiwgNi40LCA3LjMsIDguNSwgOC43NSwgOC45LCA5LjUsIDkuNzUsIDEwLCAxMC40LCAxMC40LCAxNiwgMTksDQo0LCA0LjEsIDUsIDUuNSwgNS43LCA2LjUsIDcuMjUsIDcuMywgNy41LCA4LjIsIDguNSwgOS43NSwgMTEsIDExLjIsIDE1LCAxNi41LCAyLjYsIA0KMy42LCAzLjYsIDYuNCwgNi44LCA3LjUsIDcuNSwgOC4yNSwgOC41LCAxMC40LCAxMC43NSwgMTQuMjUsIDE0LjUsIDEuNSwgNC43LCA0LjcsIA0KNy4yLCA3LjI1LCA4LjEsIDguNSwgOS4yLCA5LjUsIDEwLjcsIDExLjUsIDIuNSwgMi41LCAzLjQsIDQuMiwgNS45LCA2LjI1LCA3LjMsIDcuNSwgDQo3LjgsIDguMywgOC4zLCAxMC4yNSwgMTIuOSwgMTQuMywgNCwgNCwgNS4yNSwgNi4xLCA2LjUsIDYuOSwgNywgOC40NSwgOS4yNSwgMTAuMSwgDQoxMC4yLCAxMi43NSwgMTQuNiwgMiwgMi43LCAyLjc1LCAzLjQsIDQuMiwgNC4zLCA0LjksIDYuMjUsIDcsIDksIDkuMjUsIDEwLjcNCmBgYA0KDQpBc3N1bWUgdGhlIGRhdGEgYXJlIGdlbmVyYXRlZCBmcm9tIGEgZ2FtbWEgZGlzdHJpYnV0aW9uLiBUaGUgb2JqZWN0aXZlIGlzIHRvIHVzZSB0aGVzZSBkYXRhIGFuZCB0aGUgZGVzaWduYXRlZCBhbGdvcml0aG0gdG8gZmluZCB0aGUgbWF4aW11bSBsaWtlbGlob29kIGVzdGltYXRlcyAoTUxFcykgb2YgdGhlIHBhcmFtZXRlcnMgJFxhbHBoYSQgYW5kICRcYmV0YSQuDQoNCg0KYSkuIEZpbmQgdGhlIE1MRXMgb2YgJFxhbHBoYSQgYW5kICRcYmV0YSQsIGRlbm90ZWQgYnkgJFxoYXR7XGFscGhhfSQgYW5kICRcaGF0e1xiZXRhfSQsICB1c2luZyBncmFkaWVudC1iYXNlZCBvcHRpbWl6YXRpb24gdmlhIHRoZSBSIGZ1bmN0aW9uIGBvcHRpbSgpYCB3aXRoIHRoZSBncmFkaWVudCB2ZWN0b3IgZGVyaXZlZCBpbiBRdWVzdGlvbiAxLg0KDQpgYGB7cn0NCiMgQmlydGggdGltZSBkYXRhIChob3VycykNCnggPC0gYygNCiAgMi4xLCAzLjQsIDQuMjUsIDUuNiwgNi40LCA3LjMsIDguNSwgOC43NSwgOC45LCA5LjUsIDkuNzUsIDEwLCAxMC40LCAxMC40LCAxNiwgMTksDQogIDQsIDQuMSwgNSwgNS41LCA1LjcsIDYuNSwgNy4yNSwgNy4zLCA3LjUsIDguMiwgOC41LCA5Ljc1LCAxMSwgMTEuMiwgMTUsIDE2LjUsIDIuNiwNCiAgMy42LCAzLjYsIDYuNCwgNi44LCA3LjUsIDcuNSwgOC4yNSwgOC41LCAxMC40LCAxMC43NSwgMTQuMjUsIDE0LjUsIDEuNSwgNC43LCA0LjcsDQogIDcuMiwgNy4yNSwgOC4xLCA4LjUsIDkuMiwgOS41LCAxMC43LCAxMS41LCAyLjUsIDIuNSwgMy40LCA0LjIsIDUuOSwgNi4yNSwgNy4zLCA3LjUsDQogIDcuOCwgOC4zLCA4LjMsIDEwLjI1LCAxMi45LCAxNC4zLCA0LCA0LCA1LjI1LCA2LjEsIDYuNSwgNi45LCA3LCA4LjQ1LCA5LjI1LCAxMC4xLA0KICAxMC4yLCAxMi43NSwgMTQuNiwgMiwgMi43LCAyLjc1LCAzLjQsIDQuMiwgNC4zLCA0LjksIDYuMjUsIDcsIDksIDkuMjUsIDEwLjcNCikNCg0KbiA8LSBsZW5ndGgoeCkNCnN4IDwtIHN1bSh4KQ0Kc2xvZ3ggPC0gc3VtKGxvZyh4KSkNCnhiYXIgPC0gbWVhbih4KQ0KczIgPC0gdmFyKHgpICAgIyBzYW1wbGUgdmFyaWFuY2UgKHVzZXMgbi0xIGRlbm9taW5hdG9yKQ0KDQojIE5lZ2F0aXZlIGxvZy1saWtlbGlob29kIGZvciBHYW1tYShzaGFwZT1hbHBoYSwgc2NhbGU9YmV0YSkNCm5lZ2xvZ2xpa19nYW1tYSA8LSBmdW5jdGlvbihwYXIsIHgpIHsNCiAgYWxwaGEgPC0gcGFyWzFdDQogIGJldGEgIDwtIHBhclsyXQ0KICBpZiAoYWxwaGEgPD0gMCB8fCBiZXRhIDw9IDApIHJldHVybihJbmYpDQoNCiAgbiA8LSBsZW5ndGgoeCkNCiAgbGwgPC0gLW4gKiBsZ2FtbWEoYWxwaGEpIC0gbiAqIGFscGhhICogbG9nKGJldGEpICsgKGFscGhhIC0gMSkgKiBzdW0obG9nKHgpKSAtICgxIC8gYmV0YSkgKiBzdW0oeCkNCiAgcmV0dXJuKC1sbCkgICMgbmVnYXRpdmUgZm9yIG1pbmltaXphdGlvbg0KfQ0KDQojIEdyYWRpZW50IG9mIG5lZ2F0aXZlIGxvZy1saWtlbGlob29kICggPSAtIHNjb3JlICkNCm5lZ2dyYWRfZ2FtbWEgPC0gZnVuY3Rpb24ocGFyLCB4KSB7DQogIGFscGhhIDwtIHBhclsxXQ0KICBiZXRhICA8LSBwYXJbMl0NCiAgbiA8LSBsZW5ndGgoeCkNCg0KICBkbGRhIDwtIC1uICogZGlnYW1tYShhbHBoYSkgLSBuICogbG9nKGJldGEpICsgc3VtKGxvZyh4KSkNCiAgZGxkYiA8LSAtKG4gKiBhbHBoYSkgLyBiZXRhICsgc3VtKHgpIC8gKGJldGFeMikNCg0KICByZXR1cm4oYygtZGxkYSwgLWRsZGIpKQ0KfQ0KDQojIFN0YXJ0aW5nIHZhbHVlczogdXNlIE1ldGhvZCBvZiBNb21lbnRzIChnb29kLCBzdGFibGUgc3RhcnRpbmcgcG9pbnQpDQphbHBoYV9zdGFydCA8LSB4YmFyXjIgLyBzMg0KYmV0YV9zdGFydCAgPC0gczIgLyB4YmFyDQpzdGFydCA8LSBjKGFscGhhX3N0YXJ0LCBiZXRhX3N0YXJ0KQ0KDQptbGVfZml0IDwtIG9wdGltKA0KICBwYXIgPSBzdGFydCwNCiAgZm4gID0gbmVnbG9nbGlrX2dhbW1hLA0KICBnciAgPSBuZWdncmFkX2dhbW1hLA0KICB4ICAgPSB4LA0KICBtZXRob2QgPSAiTC1CRkdTLUIiLA0KICBsb3dlciA9IGMoMWUtOCwgMWUtOCkgICAjIGVuZm9yY2UgcG9zaXRpdml0eQ0KKQ0KDQphbHBoYV9oYXQgPC0gbWxlX2ZpdCRwYXJbMV0NCmJldGFfaGF0ICA8LSBtbGVfZml0JHBhclsyXQ0KDQpkYXRhLmZyYW1lKA0KICBhbHBoYV9oYXQgPSBhbHBoYV9oYXQsDQogIGJldGFfaGF0ICA9IGJldGFfaGF0LA0KICBjb252ZXJnZW5jZSA9IG1sZV9maXQkY29udmVyZ2VuY2UNCikNCg0KYGBgDQpiKS4gQXBwbHkgdGhlIG1ldGhvZCBvZiBtb21lbnRzIHRvIG9idGFpbiBlc3RpbWF0b3JzIGZvciAkXGFscGhhJCBhbmQgJFxiZXRhJC4gRGVub3RlIHRoZXNlIG1vbWVudCBlc3RpbWF0b3JzIGFzICRcdGlsZGV7XGFscGhhfSQgYW5kICRcdGlsZGV7XGJldGF9JC4NCg0KYGBge3J9DQphbHBoYV90aWxkZSA8LSB4YmFyXjIgLyBzMg0KYmV0YV90aWxkZSAgPC0gczIgLyB4YmFyDQoNCmRhdGEuZnJhbWUoYWxwaGFfdGlsZGUgPSBhbHBoYV90aWxkZSwgYmV0YV90aWxkZSA9IGJldGFfdGlsZGUpDQoNCmBgYA0KDQpjKS4gQ29uZHVjdCBhIGJyaWVmIGxpdGVyYXR1cmUgcmV2aWV3IGNvbXBhcmluZyB0aGUgbWV0aG9kIG9mIG1vbWVudHMgZXN0aW1hdGlvbiAoTU1FKSBhbmQgbWF4aW11bSBsaWtlbGlob29kIGVzdGltYXRpb24gKE1MRSkuIFN5bnRoZXNpemUgdGhlIGtleSBhZHZhbnRhZ2VzIGFuZCBsaW1pdGF0aW9ucyBvZiBlYWNoLCBjb25jbHVkaW5nIHdpdGggYSBwcmFjdGljYWwgcmVjb21tZW5kYXRpb24uDQoNCioqQW5zd2VyOioqDQpUaGUgTWV0aG9kIG9mIE1vbWVudHMgKE1NRSkgZXN0aW1hdGVzIHBhcmFtZXRlcnMgYnkgbWF0Y2hpbmcgc2FtcGxlIG1vbWVudHMgKGxpa2UgdGhlIG1lYW4gYW5kIHZhcmlhbmNlKSB0byB0aGUgdGhlb3JldGljYWwgbW9tZW50cyBvZiB0aGUgZGlzdHJpYnV0aW9uLiBJdCBpcyBzaW1wbGUgdG8gY29tcHV0ZSBhbmQgZWFzeSB0byB1bmRlcnN0YW5kLCBidXQgaXQgbWF5IG5vdCBhbHdheXMgcHJvdmlkZSB0aGUgbW9zdCBlZmZpY2llbnQgZXN0aW1hdGVzLg0KDQpNYXhpbXVtIExpa2VsaWhvb2QgRXN0aW1hdGlvbiAoTUxFKSBjaG9vc2VzIHRoZSBwYXJhbWV0ZXIgdmFsdWVzIHRoYXQgbWFrZSB0aGUgb2JzZXJ2ZWQgZGF0YSBtb3N0IGxpa2VseSB1bmRlciB0aGUgYXNzdW1lZCBtb2RlbC4gV2hlbiB0aGUgbW9kZWwgaXMgYXBwcm9wcmlhdGUgYW5kIHRoZSBzYW1wbGUgc2l6ZSBpcyBsYXJnZSwgTUxFIHR5cGljYWxseSBwcm9kdWNlcyBtb3JlIGFjY3VyYXRlIGFuZCBzdGF0aXN0aWNhbGx5IGVmZmljaWVudCBlc3RpbWF0ZXMuIEhvd2V2ZXIsIGl0IG9mdGVuIHJlcXVpcmVzIG51bWVyaWNhbCBvcHRpbWl6YXRpb24uDQoNCkluIHByYWN0aWNlLCBNTUUgaXMgdXNlZnVsIGZvciBxdWljayBlc3RpbWF0aW9uIGFuZCBhcyBzdGFydGluZyB2YWx1ZXMsIHdoaWxlIE1MRSBpcyBnZW5lcmFsbHkgcHJlZmVycmVkIGZvciBmaW5hbCBpbmZlcmVuY2UgZHVlIHRvIGl0cyBzdHJvbmdlciB0aGVvcmV0aWNhbCBwcm9wZXJ0aWVzLg0KXA0KDQoNCg0KDQoNCg0KDQo=