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.


Policies of Using AI Tools

Policy on AI Tool Use: Students must adhere to the AI tool policy specified in the course syllabus. The direct copying of AI-generated content is strictly prohibited. All submitted work must reflect your own understanding; where external tools are consulted, content must be thoroughly rephrased and synthesized in your own words.

Code Inclusion Requirement: Any code included in your essay must be properly commented to explain the purpose and/or expected output of key code lines. Submitting AI-generated code without meaningful, student-added comments will not be accepted.


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, \]

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 log-likelihood function with respect to the gamma distribution parameters \(\alpha\) and \(\beta\). To this end,

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

The likelihood function is:

\[ L(\alpha,\beta) = \prod_{i=1}^{n} \frac{1}{\Gamma(\alpha)\beta^\alpha} x_i^{\alpha-1} e^{-x_i/\beta}. \]

Taking the natural logarithm:

\[ \ell(\alpha,\beta) = log L(\alpha, \beta) \] We get the full log-likeihood function to be: \[ \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 log-likelihood function in part (a).

The derivative with respect to \(\alpha\):

\[ \frac{\partial \ell}{\partial \alpha} = - n \psi(\alpha) - n \log \beta + \sum_{i=1}^{n} \log x_i. \] The derivative with respect to \(\beta\):

\[ \frac{\partial \ell}{\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 in delivery suite)
birth_data <- 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
)

# Log-likelihood function (to be maximized)
loglik <- function(par, x) {
  alpha <- par[1]
  beta  <- par[2]
  
  # Return very large negative value if parameters invalid
  if(alpha <= 0 || beta <= 0) return(-1e10)
  
  n <- length(x)
  
  ll <- -n*lgamma(alpha) -
        n*alpha*log(beta) +
        (alpha-1)*sum(log(x)) -
        sum(x)/beta
  
  return(ll)
}

# Gradient (score function)
score <- function(par, x) {
  alpha <- par[1]
  beta  <- par[2]
  n <- length(x)
  
  d_alpha <- -n*digamma(alpha) -
             n*log(beta) +
             sum(log(x))
  
  d_beta  <- -n*alpha/beta +
             sum(x)/beta^2
  
  return(c(d_alpha, d_beta))
}

# Initial guesses (method of moments starting point)
start_alpha <- 2
start_beta  <- 2

# Use optim (maximize log-likelihood)
mle <- optim(
  par = c(start_alpha, start_beta),
  fn = loglik,
  gr = score,
  x = birth_data,
  method = "BFGS",
  control = list(fnscale = -1) # maximize
)

mle$par   # MLE estimates
[1] 4.387875 1.760113

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

xbar <- mean(birth_data)
s2   <- var(birth_data)

alpha_mom <- xbar^2 / s2
beta_mom  <- s2 / xbar

alpha_mom
[1] 4.685073
beta_mom
[1] 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.

The Method of Moments offers a straightforward approach to estimation. It requires only the sample mean and variance and produces closed-form solutions. This makes it computationally simple and fast. However, it does not fully exploit the distributional structure of the model and is generally less efficient than maximum likelihood estimation.

Maximum Likelihood Estimation, by contrast, uses the full likelihood function. Under regularity conditions, MLEs are consistent, asymptotically normal, and asymptotically efficient. They also allow for likelihood-based inference procedures, including confidence intervals and hypothesis testing. The primary disadvantage is that MLE often requires numerical optimization and may involve greater computational complexity.

In this application, both methods produce nearly identical estimates, which increases confidence in the modeling assumption. Nevertheless, from a theoretical standpoint, the maximum likelihood approach is preferred because of its superior large-sample properties and its foundation in likelihood theory.

LS0tDQp0aXRsZTogIkFzc2lnbm1lbnQgNDogTWF4aW11bSBMaWtlbGlob29kIEVzdGltYXRpb24iDQphdXRob3I6ICJLaWVyYW4gSGVmZmVyYW4gIg0KZGF0ZTogIiBEdWU6IDMvMy8yMDI2ICINCm91dHB1dDoNCiAgaHRtbF9kb2N1bWVudDogDQogICAgdG9jOiB5ZXMNCiAgICB0b2NfZGVwdGg6IDQNCiAgICB0b2NfZmxvYXQ6IHllcw0KICAgIG51bWJlcl9zZWN0aW9uczogbm8NCiAgICB0b2NfY29sbGFwc2VkOiB5ZXMNCiAgICBjb2RlX2ZvbGRpbmc6IGhpZGUNCiAgICBjb2RlX2Rvd25sb2FkOiB5ZXMNCiAgICBzbW9vdGhfc2Nyb2xsOiB5ZXMNCiAgICB0aGVtZTogbHVtZW4NCiAgcGRmX2RvY3VtZW50OiANCiAgICB0b2M6IHllcw0KICAgIHRvY19kZXB0aDogNA0KICAgIGZpZ19jYXB0aW9uOiB5ZXMNCiAgICBudW1iZXJfc2VjdGlvbnM6IHllcw0KICAgIGZpZ193aWR0aDogMw0KICAgIGZpZ19oZWlnaHQ6IDMNCiAgd29yZF9kb2N1bWVudDogDQogICAgdG9jOiB5ZXMNCiAgICB0b2NfZGVwdGg6IDQNCiAgICBmaWdfY2FwdGlvbjogeWVzDQogICAga2VlcF9tZDogeWVzDQplZGl0b3Jfb3B0aW9uczogDQogIGNodW5rX291dHB1dF90eXBlOiBpbmxpbmUNCi0tLQ0KDQpgYGB7Y3NzLCBlY2hvID0gRkFMU0V9DQojVE9DOjpiZWZvcmUgew0KICBjb250ZW50OiAiVGFibGUgb2YgQ29udGVudHMiOw0KICBmb250LXdlaWdodDogYm9sZDsNCiAgZm9udC1zaXplOiAxLjJlbTsNCiAgZGlzcGxheTogYmxvY2s7DQogIGNvbG9yOiBuYXZ5Ow0KICBtYXJnaW4tYm90dG9tOiAxMHB4Ow0KfQ0KDQoNCmRpdiNUT0MgbGkgeyAgICAgLyogdGFibGUgb2YgY29udGVudCAgKi8NCiAgICBsaXN0LXN0eWxlOnVwcGVyLXJvbWFuOw0KICAgIGJhY2tncm91bmQtaW1hZ2U6bm9uZTsNCiAgICBiYWNrZ3JvdW5kLXJlcGVhdDpub25lOw0KICAgIGJhY2tncm91bmQtcG9zaXRpb246MDsNCn0NCg0KaDEudGl0bGUgeyAgICAvKiBsZXZlbCAxIGhlYWRlciBvZiB0aXRsZSAgKi8NCiAgZm9udC1zaXplOiAyMnB4Ow0KICBmb250LXdlaWdodDogYm9sZDsNCiAgY29sb3I6IERhcmtSZWQ7DQogIHRleHQtYWxpZ246IGNlbnRlcjsNCiAgZm9udC1mYW1pbHk6ICJHaWxsIFNhbnMiLCBzYW5zLXNlcmlmOw0KfQ0KDQpoNC5hdXRob3IgeyAvKiBIZWFkZXIgNCAtIGFuZCB0aGUgYXV0aG9yIGFuZCBkYXRhIGhlYWRlcnMgdXNlIHRoaXMgdG9vICAqLw0KICBmb250LXNpemU6IDE1cHg7DQogIGZvbnQtd2VpZ2h0OiBib2xkOw0KICBmb250LWZhbWlseTogc3lzdGVtLXVpOw0KICBjb2xvcjogbmF2eTsNCiAgdGV4dC1hbGlnbjogY2VudGVyOw0KfQ0KDQpoNC5kYXRlIHsgLyogSGVhZGVyIDQgLSBhbmQgdGhlIGF1dGhvciBhbmQgZGF0YSBoZWFkZXJzIHVzZSB0aGlzIHRvbyAgKi8NCiAgZm9udC1zaXplOiAxOHB4Ow0KICBmb250LXdlaWdodDogYm9sZDsNCiAgZm9udC1mYW1pbHk6ICJHaWxsIFNhbnMiLCBzYW5zLXNlcmlmOw0KICBjb2xvcjogRGFya0JsdWU7DQogIHRleHQtYWxpZ246IGNlbnRlcjsNCn0NCg0KaDEgeyAvKiBIZWFkZXIgMSAtIGFuZCB0aGUgYXV0aG9yIGFuZCBkYXRhIGhlYWRlcnMgdXNlIHRoaXMgdG9vICAqLw0KICAgIGZvbnQtc2l6ZTogMjBweDsNCiAgICBmb250LXdlaWdodDogYm9sZDsNCiAgICBmb250LWZhbWlseTogIlRpbWVzIE5ldyBSb21hbiIsIFRpbWVzLCBzZXJpZjsNCiAgICBjb2xvcjogZGFya3JlZDsNCiAgICB0ZXh0LWFsaWduOiBjZW50ZXI7DQp9DQoNCmgyIHsgLyogSGVhZGVyIDIgLSBhbmQgdGhlIGF1dGhvciBhbmQgZGF0YSBoZWFkZXJzIHVzZSB0aGlzIHRvbyAgKi8NCiAgICBmb250LXNpemU6IDE4cHg7DQogICAgZm9udC13ZWlnaHQ6IGJvbGQ7DQogICAgZm9udC1mYW1pbHk6ICJUaW1lcyBOZXcgUm9tYW4iLCBUaW1lcywgc2VyaWY7DQogICAgY29sb3I6IG5hdnk7DQogICAgdGV4dC1hbGlnbjogbGVmdDsNCn0NCg0KaDMgeyAvKiBIZWFkZXIgMyAtIGFuZCB0aGUgYXV0aG9yIGFuZCBkYXRhIGhlYWRlcnMgdXNlIHRoaXMgdG9vICAqLw0KICAgIGZvbnQtc2l6ZTogMTZweDsNCiAgICBmb250LXdlaWdodDogYm9sZDsNCiAgICBmb250LWZhbWlseTogIlRpbWVzIE5ldyBSb21hbiIsIFRpbWVzLCBzZXJpZjsNCiAgICBjb2xvcjogbmF2eTsNCiAgICB0ZXh0LWFsaWduOiBsZWZ0Ow0KfQ0KDQpoNCB7IC8qIEhlYWRlciA0IC0gYW5kIHRoZSBhdXRob3IgYW5kIGRhdGEgaGVhZGVycyB1c2UgdGhpcyB0b28gICovDQogICAgZm9udC1zaXplOiAxNHB4Ow0KICBmb250LXdlaWdodDogYm9sZDsNCiAgICBmb250LWZhbWlseTogIlRpbWVzIE5ldyBSb21hbiIsIFRpbWVzLCBzZXJpZjsNCiAgICBjb2xvcjogZGFya3JlZDsNCiAgICB0ZXh0LWFsaWduOiBsZWZ0Ow0KfQ0KDQovKiBBZGQgZG90cyBhZnRlciBudW1iZXJlZCBoZWFkZXJzICovDQouaGVhZGVyLXNlY3Rpb24tbnVtYmVyOjphZnRlciB7DQogIGNvbnRlbnQ6ICIuIjsNCg0KYm9keSB7IGJhY2tncm91bmQtY29sb3I6d2hpdGU7IH0NCg0KLmhpZ2hsaWdodG1lIHsgYmFja2dyb3VuZC1jb2xvcjp5ZWxsb3c7IH0NCg0KcCB7IGJhY2tncm91bmQtY29sb3I6d2hpdGU7IH0NCg0KfQ0KYGBgDQoNCmBgYHtyIHNldHVwLCBpbmNsdWRlPUZBTFNFfQ0KIyBjb2RlIGNodW5rIHNwZWNpZmllcyB3aGV0aGVyIHRoZSBSIGNvZGUsIHdhcm5pbmdzLCBhbmQgb3V0cHV0IA0KIyB3aWxsIGJlIGluY2x1ZGVkIGluIHRoZSBvdXRwdXQgZmlsZXMuDQppZiAoIXJlcXVpcmUoImtuaXRyIikpIHsNCiAgIGluc3RhbGwucGFja2FnZXMoImtuaXRyIikNCiAgIGxpYnJhcnkoa25pdHIpDQp9DQppZiAoIXJlcXVpcmUoInBhbmRlciIpKSB7DQogICBpbnN0YWxsLnBhY2thZ2VzKCJwYW5kZXIiKQ0KICAgbGlicmFyeShwYW5kZXIpDQp9DQppZiAoIXJlcXVpcmUoImdncGxvdDIiKSkgew0KICBpbnN0YWxsLnBhY2thZ2VzKCJnZ3Bsb3QyIikNCiAgbGlicmFyeShnZ3Bsb3QyKQ0KfQ0KaWYgKCFyZXF1aXJlKCJ0aWR5dmVyc2UiKSkgew0KICBpbnN0YWxsLnBhY2thZ2VzKCJ0aWR5dmVyc2UiKQ0KICBsaWJyYXJ5KHRpZHl2ZXJzZSkNCn0NCg0KaWYgKCFyZXF1aXJlKCJwbG90bHkiKSkgew0KICBpbnN0YWxsLnBhY2thZ2VzKCJwbG90bHkiKQ0KICBsaWJyYXJ5KHBsb3RseSkNCn0NCiMjIyMNCmtuaXRyOjpvcHRzX2NodW5rJHNldChlY2hvID0gVFJVRSwgICAgICAgIyBpbmNsdWRlIGNvZGUgY2h1bmsgaW4gdGhlIG91dHB1dCBmaWxlDQogICAgICAgICAgICAgICAgICAgICAgd2FybmluZyA9IEZBTFNFLCAgICMgc29tZXRpbWVzLCB5b3UgY29kZSBtYXkgcHJvZHVjZSB3YXJuaW5nIG1lc3NhZ2VzLA0KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjIHlvdSBjYW4gY2hvb3NlIHRvIGluY2x1ZGUgdGhlIHdhcm5pbmcgbWVzc2FnZXMgaW4NCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIyB0aGUgb3V0cHV0IGZpbGUuIA0KICAgICAgICAgICAgICAgICAgICAgIHJlc3VsdHMgPSBUUlVFLCAgICAjIHlvdSBjYW4gYWxzbyBkZWNpZGUgd2hldGhlciB0byBpbmNsdWRlIHRoZSBvdXRwdXQNCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIyBpbiB0aGUgb3V0cHV0IGZpbGUuDQogICAgICAgICAgICAgICAgICAgICAgbWVzc2FnZSA9IEZBTFNFLA0KICAgICAgICAgICAgICAgICAgICAgIGNvbW1lbnQgPSBOQQ0KICAgICAgICAgICAgICAgICAgICAgICkgIA0KYGBgDQogDQpcDQogDQojIyAqKkFzc2lnbm1lbnQgT2JqZWN0aXZlcyoqIA0KDQoqIENvbXByZWhlbmQgdGhlIGxpa2VsaWhvb2QgZnVuY3Rpb24gYW5kIGl0cyBwcm9wZXJ0aWVzLg0KDQoqIE1hc3RlciB0aGUgbWF4aW11bSBsaWtlbGlob29kIGVzdGltYXRpb24gZnJhbWV3b3JrIGFuZCByZXF1aXJlZCBjb21wb25lbnRzLg0KDQoqIFVuZGVyc3RhbmQgdGhlIHBsdWctaW4gcHJpbmNpcGxlIHVuZGVybHlpbmcgTUxFLg0KDQoqIEltcGxlbWVudCBtYXhpbXVtIGxpa2VsaWhvb2QgZXN0aW1hdGlvbiBwcm9jZWR1cmVzIGluIFIuDQoNClwNCg0KIyMgKipQb2xpY2llcyBvZiBVc2luZyBBSSBUb29scyoqDQoNCioqUG9saWN5IG9uIEFJIFRvb2wgVXNlKio6IFN0dWRlbnRzIG11c3QgYWRoZXJlIHRvIHRoZSBBSSB0b29sIHBvbGljeSBzcGVjaWZpZWQgaW4gdGhlIGNvdXJzZSBzeWxsYWJ1cy4gVGhlIGRpcmVjdCBjb3B5aW5nIG9mIEFJLWdlbmVyYXRlZCBjb250ZW50IGlzIHN0cmljdGx5IHByb2hpYml0ZWQuIEFsbCBzdWJtaXR0ZWQgd29yayBtdXN0IHJlZmxlY3QgeW91ciBvd24gdW5kZXJzdGFuZGluZzsgd2hlcmUgZXh0ZXJuYWwgdG9vbHMgYXJlIGNvbnN1bHRlZCwgY29udGVudCBtdXN0IGJlIHRob3JvdWdobHkgcmVwaHJhc2VkIGFuZCBzeW50aGVzaXplZCBpbiB5b3VyIG93biB3b3Jkcy4NCg0KKipDb2RlIEluY2x1c2lvbiBSZXF1aXJlbWVudCoqOiBBbnkgY29kZSBpbmNsdWRlZCBpbiB5b3VyIGVzc2F5IG11c3QgYmUgcHJvcGVybHkgY29tbWVudGVkIHRvIGV4cGxhaW4gdGhlIHB1cnBvc2UgYW5kL29yIGV4cGVjdGVkIG91dHB1dCBvZiBrZXkgY29kZSBsaW5lcy4gU3VibWl0dGluZyBBSS1nZW5lcmF0ZWQgY29kZSB3aXRob3V0IG1lYW5pbmdmdWwsIHN0dWRlbnQtYWRkZWQgY29tbWVudHMgd2lsbCBub3QgYmUgYWNjZXB0ZWQuDQoNClwNCg0KKipHYW1tYSBEaXN0cmlidXRpb24gUmV2aXNpdGVkKioNCg0KTGV0ICRYJCBiZSB0aGUgdHdvIHBhcmFtZXRlciBHYW1tYSByYW5kb20gdmFyaWFibGUgd2l0aCBkZW5zaXR5IGZ1bmN0aW9uDQoNCiQkDQpmKHggXG1pZCBcYWxwaGEsIFxiZXRhKSA9IFxmcmFjezF9e1xHYW1tYShcYWxwaGEpXGJldGFeXGFscGhhfSB4XntcYWxwaGEtMX0gZV57LXgvXGJldGF9ICBcIFwgXHRleHR7Zm9yfSBcIFwgIHggPiAwLA0KJCQNCg0Kd2hlcmUgd2l0aCAkXGFscGhhID4gMCQgKHNoYXBlKSwgJFxiZXRhPjAkIChzY2FsZSksIGFuZA0KDQokJA0KXEdhbW1hKFxhbHBoYSkgPSBcaW50X3swfV57XGluZnR5fSB0XntcYWxwaGEtMX0gZV57LXR9IFwsIGR0LCBccXVhZCBcYWxwaGEgPiAwLg0KJCQNCg0KJFxHYW1tYSh4KSQgY2FuIGJlIGNvbXB1dGVkIGluIFIgdXNpbmcgdGhlIGBnYW1tYSgpYCBmdW5jdGlvbi4gVGhlIGRlcml2YXRpdmUgb2YgJFxHYW1tYSh4KSQgYXJlIGdpdmVuIHJlc3BlY3RpdmVseSBieQ0KDQokJA0KXEdhbW1hXlxwcmltZSh6KSA9IFxHYW1tYSAoeilccHNpXzAoeikNCiQkDQoNCndoZXJlICRccHNpXzAoeikgPSBcZnJhY3tkfXtken0gXGxuIFxHYW1tYXt6fSQuIEluIFIsIHRoZSBkaWdhbW1hIGZ1bmN0aW9uICRccHNpXzAoeikkIGlzIGV2YWx1YXRlZCBieSBgZGlnYW1tYSgpYC4NCg0KDQoNClwNCg0KPGZvbnQgY29sb3IgPSAiYmx1ZSI+VGhpcyBhc3NpZ25tZW50IGZvY3VzZXMgb24gZmluZGluZyBtYXhpbXVtIGxpa2VsaWhvb2QgZXN0aW1hdGUgb2YgcGFyYW1ldGVycyAkXGFscGhhJCBhbmQgJFxiZXRhJCBiYXNlZCBvbiBhIHJlYWwtd29ybGQgYXBwbGljYXRpb24gZGF0YSBzZXQuPC9mb250Pg0KDQoNClwNCg0KIyMgKipRdWVzdGlvbiAxOiBEZXJpdmUgZ3JhZGllbnQgKGZpcnN0IG9yZGVyIHBhcnRpYWwgZGVyaXZhdGl2ZSkgb2YgbGlrZWxpaG9vZCBmdW5jdGlvbioqDQoNCkFzc3VtZSB0aGF0ICRce3hfMSwgeF8yLCBcY2RvdHMsIHhfbiBcfSBcdG8gXHRleHR7IGdhbW1hIH0oXGFscGhhLCBcYmV0YSkkIHdpdGggZGVuc2l0eSBmdW5jdGlvbiBnaXZlbiBieQ0KDQokJA0KZih4IFxtaWQgXGFscGhhLCBcYmV0YSkgPSBcZnJhY3sxfXtcR2FtbWEoXGFscGhhKVxiZXRhXlxhbHBoYX0geF57XGFscGhhLTF9IGVeey14L1xiZXRhfSAgXCBcIFx0ZXh0e2Zvcn0gXCBcICB4ID4gMCwNCiQkDQoNCkRlcml2ZSB0aGUgZ3JhZGllbnQgb2YgdGhlICoqbG9nLWxpa2VsaWhvb2QgZnVuY3Rpb24qKiB3aXRoIHJlc3BlY3QgdG8gdGhlIGdhbW1hIGRpc3RyaWJ1dGlvbiBwYXJhbWV0ZXJzICRcYWxwaGEkIGFuZCAkXGJldGEkLiBUbyB0aGlzIGVuZCwNCg0KDQphKS4gV3JpdGUgb3V0IHRoZSBmdWxsICoqbG9nLWxpa2VsaWhvb2QgZnVuY3Rpb24qKiBiYXNlZCBvbiB0aGUgZ2l2ZW4gZGF0YSBhbmQgdGhlIGRlbnNpdHkgZnVuY3Rpb24gcHJvdmlkZWQgYWJvdmUuDQoNCg0KKipUaGUgbGlrZWxpaG9vZCBmdW5jdGlvbiBpczoqKg0KDQokJA0KTChcYWxwaGEsXGJldGEpDQo9DQpccHJvZF97aT0xfV57bn0NClxmcmFjezF9e1xHYW1tYShcYWxwaGEpXGJldGFeXGFscGhhfQ0KeF9pXntcYWxwaGEtMX0NCmVeey14X2kvXGJldGF9Lg0KJCQNCg0KKipUYWtpbmcgdGhlIG5hdHVyYWwgbG9nYXJpdGhtOioqDQoNCiQkDQpcZWxsKFxhbHBoYSxcYmV0YSkNCj0gDQpsb2cgTChcYWxwaGEsIFxiZXRhKQ0KJCQNCioqV2UgZ2V0IHRoZSBmdWxsIGxvZy1saWtlaWhvb2QgZnVuY3Rpb24gdG8gYmU6KioNCiQkDQpcZWxsKFxhbHBoYSxcYmV0YSkNCj0NCi0gblxsb2cgXEdhbW1hKFxhbHBoYSkNCi0gblxhbHBoYSBcbG9nIFxiZXRhDQorIChcYWxwaGEtMSlcc3VtX3tpPTF9XntufVxsb2cgeF9pDQotIFxmcmFjezF9e1xiZXRhfVxzdW1fe2k9MX1ee259IHhfaS4NCiQkDQoNCmIpLiBEZXJpdmUgdGhlIHNjb3JlIGZ1bmN0aW9ucyAodGhlIGdyYWRpZW50IG9mIHRoZSBsb2ctbGlrZWxpaG9vZCkgZnJvbSB0aGUgZnVsbCAqKmxvZy1saWtlbGlob29kIGZ1bmN0aW9uKiogaW4gcGFydCAoYSkuDQoNCg0KKipUaGUgZGVyaXZhdGl2ZSB3aXRoIHJlc3BlY3QgdG8gJFxhbHBoYSQ6KioNCg0KJCQNClxmcmFje1xwYXJ0aWFsIFxlbGx9e1xwYXJ0aWFsIFxhbHBoYX0NCj0NCi0gbiBccHNpKFxhbHBoYSkNCi0gbiBcbG9nIFxiZXRhDQorIFxzdW1fe2k9MX1ee259IFxsb2cgeF9pLg0KJCQNCioqVGhlIGRlcml2YXRpdmUgd2l0aCByZXNwZWN0IHRvICRcYmV0YSQ6KioNCg0KJCQNClxmcmFje1xwYXJ0aWFsIFxlbGx9e1xwYXJ0aWFsIFxiZXRhfQ0KPQ0KLVxmcmFje25cYWxwaGF9e1xiZXRhfQ0KKw0KXGZyYWN7MX17XGJldGFeMn1cc3VtX3tpPTF9XntufSB4X2kuDQokJA0KXA0KDQojIyAqKlF1ZXN0aW9uIDI6IEJpcnRoIGRhdGEgc2V0KioNCg0KVGhlIGZvbGxvd2luZyBSIGNvZGUgcmVhZHMgaW4gYSBkYXRhIHNldCBjb250YWluaW5nLCBmb3IgZWFjaCBvZiA3IGRheXMsIHRoZSBsZW5ndGhzIG9mIHRpbWUgaW4gaG91cnMgc3BlbnQgYnkNCndvbWVuIGluIHRoZSBkZWxpdmVyeSBzdWl0ZSB3aGlsZSBnaXZpbmcgYmlydGggKHdpdGhvdXQgYSBjZWFzYXJpYW4gc2VjdGlvbikgYXQgSm9obiBSYWRjbGlmZmUgSG9zcGl0YWwgaW4NCk94Zm9yZCwgRW5nbGFuZC4gVGhlIGRhdGEgYXJlIHRha2VuIGZyb20gRGF2aXNvbiAoU3RhdGlzdGljYWwgTW9kZWxzLiBDYW1icmlkZ2UgVW5pdmVyc2l0eSBQcmVzcywgMjAwMykuDQoNCmBgYA0KMi4xLCAzLjQsIDQuMjUsIDUuNiwgNi40LCA3LjMsIDguNSwgOC43NSwgOC45LCA5LjUsIDkuNzUsIDEwLCAxMC40LCAxMC40LCAxNiwgMTksDQo0LCA0LjEsIDUsIDUuNSwgNS43LCA2LjUsIDcuMjUsIDcuMywgNy41LCA4LjIsIDguNSwgOS43NSwgMTEsIDExLjIsIDE1LCAxNi41LCAyLjYsIA0KMy42LCAzLjYsIDYuNCwgNi44LCA3LjUsIDcuNSwgOC4yNSwgOC41LCAxMC40LCAxMC43NSwgMTQuMjUsIDE0LjUsIDEuNSwgNC43LCA0LjcsIA0KNy4yLCA3LjI1LCA4LjEsIDguNSwgOS4yLCA5LjUsIDEwLjcsIDExLjUsIDIuNSwgMi41LCAzLjQsIDQuMiwgNS45LCA2LjI1LCA3LjMsIDcuNSwgDQo3LjgsIDguMywgOC4zLCAxMC4yNSwgMTIuOSwgMTQuMywgNCwgNCwgNS4yNSwgNi4xLCA2LjUsIDYuOSwgNywgOC40NSwgOS4yNSwgMTAuMSwgDQoxMC4yLCAxMi43NSwgMTQuNiwgMiwgMi43LCAyLjc1LCAzLjQsIDQuMiwgNC4zLCA0LjksIDYuMjUsIDcsIDksIDkuMjUsIDEwLjcNCmBgYA0KDQpBc3N1bWUgdGhlIGRhdGEgYXJlIGdlbmVyYXRlZCBmcm9tIGEgZ2FtbWEgZGlzdHJpYnV0aW9uLiBUaGUgb2JqZWN0aXZlIGlzIHRvIHVzZSB0aGVzZSBkYXRhIGFuZCB0aGUgZGVzaWduYXRlZCBhbGdvcml0aG0gdG8gZmluZCB0aGUgbWF4aW11bSBsaWtlbGlob29kIGVzdGltYXRlcyAoTUxFcykgb2YgdGhlIHBhcmFtZXRlcnMgJFxhbHBoYSQgYW5kICRcYmV0YSQuDQoNCg0KYSkuIEZpbmQgdGhlIE1MRXMgb2YgJFxhbHBoYSQgYW5kICRcYmV0YSQsIGRlbm90ZWQgYnkgJFxoYXR7XGFscGhhfSQgYW5kICRcaGF0e1xiZXRhfSQsICB1c2luZyBncmFkaWVudC1iYXNlZCBvcHRpbWl6YXRpb24gdmlhIHRoZSBSIGZ1bmN0aW9uIGBvcHRpbSgpYCB3aXRoIHRoZSBncmFkaWVudCB2ZWN0b3IgZGVyaXZlZCBpbiBRdWVzdGlvbiAxLg0KDQpgYGB7cn0NCiMgQmlydGggdGltZSBkYXRhIChob3VycyBpbiBkZWxpdmVyeSBzdWl0ZSkNCmJpcnRoX2RhdGEgPC0gYygNCjIuMSwzLjQsNC4yNSw1LjYsNi40LDcuMyw4LjUsOC43NSw4LjksOS41LDkuNzUsMTAsMTAuNCwxMC40LDE2LDE5LA0KNCw0LjEsNSw1LjUsNS43LDYuNSw3LjI1LDcuMyw3LjUsOC4yLDguNSw5Ljc1LDExLDExLjIsMTUsMTYuNSwyLjYsDQozLjYsMy42LDYuNCw2LjgsNy41LDcuNSw4LjI1LDguNSwxMC40LDEwLjc1LDE0LjI1LDE0LjUsMS41LDQuNyw0LjcsDQo3LjIsNy4yNSw4LjEsOC41LDkuMiw5LjUsMTAuNywxMS41LDIuNSwyLjUsMy40LDQuMiw1LjksNi4yNSw3LjMsNy41LA0KNy44LDguMyw4LjMsMTAuMjUsMTIuOSwxNC4zLDQsNCw1LjI1LDYuMSw2LjUsNi45LDcsOC40NSw5LjI1LDEwLjEsDQoxMC4yLDEyLjc1LDE0LjYsMiwyLjcsMi43NSwzLjQsNC4yLDQuMyw0LjksNi4yNSw3LDksOS4yNSwxMC43DQopDQoNCiMgTG9nLWxpa2VsaWhvb2QgZnVuY3Rpb24gKHRvIGJlIG1heGltaXplZCkNCmxvZ2xpayA8LSBmdW5jdGlvbihwYXIsIHgpIHsNCiAgYWxwaGEgPC0gcGFyWzFdDQogIGJldGEgIDwtIHBhclsyXQ0KICANCiAgIyBSZXR1cm4gdmVyeSBsYXJnZSBuZWdhdGl2ZSB2YWx1ZSBpZiBwYXJhbWV0ZXJzIGludmFsaWQNCiAgaWYoYWxwaGEgPD0gMCB8fCBiZXRhIDw9IDApIHJldHVybigtMWUxMCkNCiAgDQogIG4gPC0gbGVuZ3RoKHgpDQogIA0KICBsbCA8LSAtbipsZ2FtbWEoYWxwaGEpIC0NCiAgICAgICAgbiphbHBoYSpsb2coYmV0YSkgKw0KICAgICAgICAoYWxwaGEtMSkqc3VtKGxvZyh4KSkgLQ0KICAgICAgICBzdW0oeCkvYmV0YQ0KICANCiAgcmV0dXJuKGxsKQ0KfQ0KDQojIEdyYWRpZW50IChzY29yZSBmdW5jdGlvbikNCnNjb3JlIDwtIGZ1bmN0aW9uKHBhciwgeCkgew0KICBhbHBoYSA8LSBwYXJbMV0NCiAgYmV0YSAgPC0gcGFyWzJdDQogIG4gPC0gbGVuZ3RoKHgpDQogIA0KICBkX2FscGhhIDwtIC1uKmRpZ2FtbWEoYWxwaGEpIC0NCiAgICAgICAgICAgICBuKmxvZyhiZXRhKSArDQogICAgICAgICAgICAgc3VtKGxvZyh4KSkNCiAgDQogIGRfYmV0YSAgPC0gLW4qYWxwaGEvYmV0YSArDQogICAgICAgICAgICAgc3VtKHgpL2JldGFeMg0KICANCiAgcmV0dXJuKGMoZF9hbHBoYSwgZF9iZXRhKSkNCn0NCg0KIyBJbml0aWFsIGd1ZXNzZXMgKG1ldGhvZCBvZiBtb21lbnRzIHN0YXJ0aW5nIHBvaW50KQ0Kc3RhcnRfYWxwaGEgPC0gMg0Kc3RhcnRfYmV0YSAgPC0gMg0KDQojIFVzZSBvcHRpbSAobWF4aW1pemUgbG9nLWxpa2VsaWhvb2QpDQptbGUgPC0gb3B0aW0oDQogIHBhciA9IGMoc3RhcnRfYWxwaGEsIHN0YXJ0X2JldGEpLA0KICBmbiA9IGxvZ2xpaywNCiAgZ3IgPSBzY29yZSwNCiAgeCA9IGJpcnRoX2RhdGEsDQogIG1ldGhvZCA9ICJCRkdTIiwNCiAgY29udHJvbCA9IGxpc3QoZm5zY2FsZSA9IC0xKSAjIG1heGltaXplDQopDQoNCm1sZSRwYXIgICAjIE1MRSBlc3RpbWF0ZXMNCmBgYA0KDQpiKS4gQXBwbHkgdGhlIG1ldGhvZCBvZiBtb21lbnRzIHRvIG9idGFpbiBlc3RpbWF0b3JzIGZvciAkXGFscGhhJCBhbmQgJFxiZXRhJC4gRGVub3RlIHRoZXNlIG1vbWVudCBlc3RpbWF0b3JzIGFzICRcdGlsZGV7XGFscGhhfSQgYW5kICRcdGlsZGV7XGJldGF9JC4NCg0KYGBge3J9DQp4YmFyIDwtIG1lYW4oYmlydGhfZGF0YSkNCnMyICAgPC0gdmFyKGJpcnRoX2RhdGEpDQoNCmFscGhhX21vbSA8LSB4YmFyXjIgLyBzMg0KYmV0YV9tb20gIDwtIHMyIC8geGJhcg0KDQphbHBoYV9tb20NCmJldGFfbW9tDQoNCmBgYA0KYykuIENvbmR1Y3QgYSBicmllZiBsaXRlcmF0dXJlIHJldmlldyBjb21wYXJpbmcgdGhlIG1ldGhvZCBvZiBtb21lbnRzIGVzdGltYXRpb24gKE1NRSkgYW5kIG1heGltdW0gbGlrZWxpaG9vZCBlc3RpbWF0aW9uIChNTEUpLiBTeW50aGVzaXplIHRoZSBrZXkgYWR2YW50YWdlcyBhbmQgbGltaXRhdGlvbnMgb2YgZWFjaCwgY29uY2x1ZGluZyB3aXRoIGEgcHJhY3RpY2FsIHJlY29tbWVuZGF0aW9uLg0KDQoqKlRoZSBNZXRob2Qgb2YgTW9tZW50cyBvZmZlcnMgYSBzdHJhaWdodGZvcndhcmQgYXBwcm9hY2ggdG8gZXN0aW1hdGlvbi4gSXQgcmVxdWlyZXMgb25seSB0aGUgc2FtcGxlIG1lYW4gYW5kIHZhcmlhbmNlIGFuZCBwcm9kdWNlcyBjbG9zZWQtZm9ybSBzb2x1dGlvbnMuIFRoaXMgbWFrZXMgaXQgY29tcHV0YXRpb25hbGx5IHNpbXBsZSBhbmQgZmFzdC4gSG93ZXZlciwgaXQgZG9lcyBub3QgZnVsbHkgZXhwbG9pdCB0aGUgZGlzdHJpYnV0aW9uYWwgc3RydWN0dXJlIG9mIHRoZSBtb2RlbCBhbmQgaXMgZ2VuZXJhbGx5IGxlc3MgZWZmaWNpZW50IHRoYW4gbWF4aW11bSBsaWtlbGlob29kIGVzdGltYXRpb24uKioNCg0KKipNYXhpbXVtIExpa2VsaWhvb2QgRXN0aW1hdGlvbiwgYnkgY29udHJhc3QsIHVzZXMgdGhlIGZ1bGwgbGlrZWxpaG9vZCBmdW5jdGlvbi4gVW5kZXIgcmVndWxhcml0eSBjb25kaXRpb25zLCBNTEVzIGFyZSBjb25zaXN0ZW50LCBhc3ltcHRvdGljYWxseSBub3JtYWwsIGFuZCBhc3ltcHRvdGljYWxseSBlZmZpY2llbnQuIFRoZXkgYWxzbyBhbGxvdyBmb3IgbGlrZWxpaG9vZC1iYXNlZCBpbmZlcmVuY2UgcHJvY2VkdXJlcywgaW5jbHVkaW5nIGNvbmZpZGVuY2UgaW50ZXJ2YWxzIGFuZCBoeXBvdGhlc2lzIHRlc3RpbmcuIFRoZSBwcmltYXJ5IGRpc2FkdmFudGFnZSBpcyB0aGF0IE1MRSBvZnRlbiByZXF1aXJlcyBudW1lcmljYWwgb3B0aW1pemF0aW9uIGFuZCBtYXkgaW52b2x2ZSBncmVhdGVyIGNvbXB1dGF0aW9uYWwgY29tcGxleGl0eS4qKg0KDQoqKkluIHRoaXMgYXBwbGljYXRpb24sIGJvdGggbWV0aG9kcyBwcm9kdWNlIG5lYXJseSBpZGVudGljYWwgZXN0aW1hdGVzLCB3aGljaCBpbmNyZWFzZXMgY29uZmlkZW5jZSBpbiB0aGUgbW9kZWxpbmcgYXNzdW1wdGlvbi4gTmV2ZXJ0aGVsZXNzLCBmcm9tIGEgdGhlb3JldGljYWwgc3RhbmRwb2ludCwgdGhlIG1heGltdW0gbGlrZWxpaG9vZCBhcHByb2FjaCBpcyBwcmVmZXJyZWQgYmVjYXVzZSBvZiBpdHMgc3VwZXJpb3IgbGFyZ2Utc2FtcGxlIHByb3BlcnRpZXMgYW5kIGl0cyBmb3VuZGF0aW9uIGluIGxpa2VsaWhvb2QgdGhlb3J5LioqDQoNCg0KDQoNCg0KDQo=