Topics

Reference

  • Wasserman (2004), Chapters 2, 3, and 5

Sample Space

Sample space \(\Omega\) is the set of possible outcomes.

  • examples: \(\Omega = \{H, T\}\) for a coin toss

  • \(\Omega = \{HH, HT, TH, TT\}\) for two coin tosses

Outcome \(\omega\): an element of sample space \(\Omega\)

  • example: \(\omega=H\) for a coin toss

Event \(A\): subset of sample space \(\Omega\)

  • example: \(\Omega = \{HT, TH\}\) for tow coin tosses

Probability \(P(A)\) of an event \(A\) represents the frequency of observing \(A\)

  • Probability distribution \(P\) is a function that satisfies:

    • \(P(A) \ge 0\) for every event \(A\)
    • \(P(\Omega) = 1\)
    • If \(A\) and \(B\) are disjoint, \(P(A\cup B) = P(A) + P(B)\)

Random Variable

Random variable \(X\) is a mapping from each outcome \(\omega\in\Omega\) to a real number

  • example: \(X\) is the number of heads in two coin tosses

    • \(X(\omega)=1\) for both \(\omega=HT\) and \(\omega=TH\).

Probability for a random variable for the events that give the value:

- $P(X=1) = P({HT,TH}) = 1/2$  
- $P(X\le 1) = P({TT,HT,TH}) = 3/4$

  • In general:

    • \(P(X=x) = P(\omega\in\Omega; X(\omega)=x)\)
    • \(P(X\in A) = P(\omega\in\Omega; X(\omega)=A)\)

Probability function (or probability mass function)

  • For discrete radom variable: \(f_X(x)=P(X=x)\)

  • Example: # of heads in two coin tosses

p = 0.3
x = 0:2
f = c((1-p)^2, 2*p*(1-p), p^2)
plot(x, f, type="h", lwd=3, ylim=c(0, 1))  # "h" for histogram-like

Probability density function (PDF)

  • For continuous random variable \(X\).

    • \(f_X(x) \ge 0\) for all \(x\)

    • \(\int_{-\infty}^{\infty} f_X(x)dx = 1\)

    • \(P(a<X<b) = \int_{a}^{b} f_X(x)dx\)

  • Example: Uniform distribution in \([0,1]\)

Probability density function:

x = seq(-0.5, 1.5, 0.01)
f = dunif(x, 0, 1)
plot(x, f, type="l")

Cumulative distribution function (CDF)

  • \(F_X(x)=P(X\le x)\)

  • CDF is related with PDF as:

    • \(F_X(x) = \int_{-\infty}^{x} f_X(x)dx\)
    • \(f_X(x) = F'_X(x)\) where \(F_X\) is differentiable

  • CDF allows dealing with discrete and continuous random variables in a unified way.

Inverse CDF (or quantile function)

  • \(F^{-1}(q) = \inf\{x: F(x)>q\}\)

  • Example: # of heads in two coin tosses

p = 0.5
f = c((1-p)^2, 2*p*(1-p), p^2)
# CDF
F = rep( c(0, cumsum(f)), each=2)
x = c(-1, rep(0:2, each=2), 3)
par(mfrow=c(1, 2))  # side by side 
plot(x, F, type="l")
# Inverse CDF
plot(F, x, type="l", xlab="q", ylab="x=F^-1(q)")

  • Example: Uniform distribution in \([0,1]\)
x = seq(-0.5, 1.5, 0.01)
# CDF
F = punif(x, 0, 1)
par(mfrow=c(1, 2))  # side by side 
plot(x, F, type="l")
# Inverse CDF
plot(F, x, type="l", xlab="q", ylab="x=F^-1(q)")

Discrete Random Variables

\(X \sim F\) means \(X\) has distribution \(F\)

Uniform distribution on integers \({1,...,k}\):

\[f(x) = \frac{1}{k}\]

k = 5
x = 1:k
f = matrix(1/k, 1, k)
plot(x, f, type="h", lwd=3, ylim=c(0,1))

Bernoulli Distribution

\[X \sim \mbox{Bernoulli}(p)\]

  • coin toss with the probability of head \(p\)

\[P(X=1) = p\] \[P(X=0) = 1-p\]

The probability (mass) function can be represented as: \[f(x) = p^x(1-p)^{1-x}\]

p = 0.3
x = 0:1
f = p^x * (1-p)^(1-x)  # = c(1-p, p)
plot(x, f, type="h", lwd=3, ylim=c(0,1))

Binomial Distribution

\[X \sim \mbox{Binomial}(n, p)\]

  • number of heads in \(n\) coin tosses the probability of head \(p\)

\[f(x) = {n \choose x} p^x(1-p)^{n-x}\] \({n \choose x}=\frac{n!}{x!(n-x)!}\): the number of ways choosing \(x\) items out of \(n\).

n = 5
p = 0.6
x = 0:n
f = choose(n,x) * p^x * (1-p)^(n-x)
#f = dbinom(x, n, p)
plot(x, f, type="h", lwd=3, ylim=c(0,1))

Probability distributions in R

Most popular distributions are available with the convention:

  • d...(): probability density or mass function
  • p...(): CDF
  • q...(): Quantile function (inverse CDF)
  • r...(): draw samples
# binomial distribution
n = 5
p = 0.3
par(mfcol=c(2,2))  # in 2x2 grid
# mass function
x = 0:n
plot(x, dbinom(x, n, p), type="h", lwd=3, ylim=c(0,1))
# CDF
x = seq(0, n, 0.05)
plot(x, pbinom(x, n, p), type="l")
# Quantile function
q = seq(0, 1, 0.01)
plot(q, qbinom(q, n, p), type="l")
# draw samples
plot(rbinom(100, n, p))

Poisson Disbribution

\[X \sim \mbox{Poisson}(\lambda)\]

  • count of events that occur at average rate \(\lambda\)

\[f(x) = e^{-\lambda} \frac{\lambda^x}{x!}\]

lambda = 2
x = 0:10
f = dpois(x, lambda)
plot(x, f, type="h", lwd=3, ylim=c(0,1))

Multinomial distribution

\[X \sim \mbox{Multinomial}(n,p)\]

  • For \(k\) possible outcomes with probabiliies \(p=(p_1,..,p_k)\), number of each outcome after \(n\) draws \(X=(X_1,...,X_k)\)

\[f(x) = {n \choose x_1...x_k} p_1^{x_1}...p_k^{x_k}\] \({n \choose x_1...x_k} = \frac{n!}{x_1!...x_k!}\)

p = c(0.4, 0.5, 0.1)  # k=3
n = 10
dmn <-function(x1, x2){
  if(x1+x2 > n){
    return(0)  # cannot happen
  }else{
    x = c(x1, x2, n-x1-x2)  # sum up to n
    return(dmultinom(x, prob=p))
  }
}
x1 = x2 = 0:n
f = outer(x1, x2, Vectorize(dmn))
persp(x1, x2, f, theta=60)

Continuous Random Variables

Uniform Distribution

\[X \sim \mbox{Uniform}(a,b)\]

\[f(x) = \left\{\begin{array}{cl} \frac{1}{b-a} & \mbox{for } x \in [a,b]\\ 0 & \mbox{otherwise}\end{array}\right.\]

x = seq(-2, 2, 0.01)
f = dunif(x, -1, 1)
plot(x, f, type="l")

Exponential Distribution

\[X \sim \mbox{Exp}(\lambda)\]

  • Interval of events happening at rate \(\lambda\)

\[f(x) = \lambda e^{-\lambda x}\]

Defined for \(x \ge 0\) and \(\lambda > 0\).

lambda = .5
x = seq(-5, 10, 0.1)
f = dexp(x, lambda)
plot(x, f, type="l")

It is sometimes parameterized by \(\beta = \frac{1}{\lambda}\).

Gamma Distribution

\[X \sim \mbox{Gamma}(a,b)\]

Sum of \(a\) independent samples from Exp(\(b\))

\[f(x) = \frac{b^a}{\Gamma(a)} x^{a-1} e^{-bx}\] where the “Gamma function” is defined as \[\Gamma(a) =\int_0^\infty t^{a-1}e^{-t}dt\] For integer values of \(a\), \(\Gamma(a)=a!\).

a = 1  # same as exp
b = 1
x = seq(-2, 10, 0.01)
f = dgamma(x, a, b)
plot(x, f, type="l")
for (a in 2:6){  # see the change with a
  lines(x, dgamma(x, a, b), col=a)
}

For independent random variables \(X_i \sim \mbox{Gamma}(a_i,b)\), \[\sum_{i=1}^n X_i \sim \mbox{Gamma}(\sum_{i=1}^n a_i, b)\]

Normal (Gaussian) Distribution

\[X \sim \mathcal{N}(\mu,\sigma)\] mean \(\mu\) and standard deviation \(\sigma\)

\[f(x) = \frac{1}{\sigma\sqrt{2\pi}} e^{-\frac{(x-\mu)^2}{2\sigma^2}}\]

x = seq(-5, 5, 0.1)
f = dnorm(x)  # default: mu=0, sigma=1
plot(x, f, type="l")

Expectation

Expectation (or mean, or first moment) of random variable \(X\):

\[E(X) = \int x dF(x)\]

\[E(X) = \sum_x x f(x)\]

\[E(X) = \int_{-\infty}^{\infty} x f(x) dx\]

Expectation is often denoted as \(E(X)=\mu_X=\mu\).

Properties of Expectations

  • Expectation of a function \(Y=r(X)\):

\[E(Y) = E(r(X)) = \int r(x)dF_X(x)\]

  • Linear sum:

\[E(\sum_i a_i X_i) =\sum_i a_i E(X_i)\]

  • Product of independent random variables:

\[E(\prod_i X_i) =\prod_i E(X_i)\]

Variance

Variance is a measure of the spread of a distribution.

\[V(X) = E((X-\mu)^2) = \int(x-\mu)^2 dF(x)\]

\[V(\sum_i a_i X_i) =\sum_i a_i^2 V(X_i)\]

Limit Theory

The Law of Large Numbers

The sample average \(\bar{X}_n=\frac{1}{n}\sum_{i=1}^n X_i\) converges in probability to the expectation \(\mu=EE(X_i)\).

  • \(X_n\) converges to \(X\) in probability

\[X_n\stackrel{P}{\rightarrow}X\]

For every \(\epsilon>0\), as \(n\rightarrow\infty\), \[P(|X_n-X|>\epsilon)\rightarrow 0\]

The Central Limit Theorem

For any distribution of \(X\) with mean \(\mu\) and variance \(\sigma^2\), the distribution of sample averages \(X_n\) follows a Normal distribution \(\mathcal{N}(\mu,\frac{\sigma^2}{n})\)

  • Deviation of the sample average from the true mean, scaled by \(n\) as \(\sqrt{n}(\bar{X}_n-\mu)\), converges in distribution to a Normal distribution \(\mathcal{N}(0,\sigma^2)\).

  • \(X_n\) converges to \(X\) in distribution

\[X_n\leadsto X\]

The cumulative distribution function \(F_n(X_n)\) converges to \(F(X)\) at every point \(x\) where \(F\) is continuous. \[\lim_{n\rightarrow\infty}F_n(x)=F(x)\]

Exercise

1. PDF and CDF

  1. For an exponential distribution, plot the PDF, CDF and inverse CDF (quantile function) by dexp, pexp and qexp.
  1. Derive the mathematical form of the CDF of the exponential distribution from its PDF \[f(x) = \lambda e^{-\lambda x}\]

and compare with the plot above.

  1. Derive the mathematical form of the inverse CDF (quantile function) of the exponential distribution

and compare with the plot above.

2. Relationships between distributions

  1. Make a sample by summing samples from Bernoulli distribution. Plot its histgram and chek if that fits with the Binomial distribution give by dbinom().
  1. By taking \(n\) large and scaling \(p\) by \(\frac{1}{n}\) in Binomial distribution, see if the distribution comes close to Poisson distribution
  1. Draw a sequence of samples from a Bernoulli distribution with small \(p\). Make a histogram of the time intervals between 1s and see what distribution it follows.
  1. Divide the above sequence into time bins of length \(T\) and count 1s in each bin. What distribution does it follow?
  1. By summing up multiple samples from exponential distribution, check whether that follows Gamma distribution.
  1. See in what case Gamma distribution become close to the normal distribution.

3. Expectation and Variance

*is optional for those with mathematical background

  1. Derive the mean and the variance of Bernoulli distribution.

  2. Derive the mean and the variance of Binomial distribution.

  3. Drive the mean and the variance of uniform distribution.

4*) Compute the mean of the exponential distribution from PDF: \[E(X) = \int_0^\infty x f(x) dx\]

5*) Compute the mean of the exponential distribution from CDF: \[E(X) = \int x dF(x) = \int_0^1 F^{-1}(q) dq\]

6*) Derive the variance of the exponential distribution.

  1. Derive the mean and the variance of Gamma distribution as a sum of the samples from exponential distribution.
LS0tCnRpdGxlOiAiMi4gUHJvYmFiaWxpdHkgRGlzdHJpYnV0aW9ucyIKb3V0cHV0OiBodG1sX25vdGVib29rCi0tLQoKIyBUb3BpY3MKCiogU2FtcGxlIHNwYWNlLCBSYW5kb20gdmFyaWFibGUKKiBQcm9iYWJpbGl0eSBtYXNzL2RlbnNpdHkgZnVuY3Rpb24KKiBDdW11bGF0aXZlIGRpc3RyaWJ1dGlvbiBmdW5jdGlvbgoqIERpc2NyZXRlIGRpc3RyaWJ1dGlvbnMKICAgICogVW5pZm9ybSBkaXN0cmlidXRpb24KICAgICogQmVybm91bGxpIGRpc3RyaWJ1dGlvbgogICAgKiBCaW5vbWlhbCBkaXN0cmlidXRpb24KICAgICogUG9pc3NvbiBkaXN0cmlidXRpb24KICAgICogTXVsdGlub21pYWwgZGlzdHJpYnV0aW9uCiogQ29udGludW91cyBkaXN0cmlidXRpb25zCiAgICAqIFVuaWZvcm0gZGlzdHJpYnV0aW9uCiAgICAqIEV4cG9uZW50aWFsIGRpc3RyaWJ1dGlvbgogICAgKiBHYW1tYSBkaXN0cmlidXRpb24KICAgICogTm9ybWFsIChHYXVzc2lhbikgZGlzdHJpYnV0aW9uCiogRXhwZWN0YXRpb24KKiBWYXJpYW5jZQoqIExhdyBvZiBsYXJnZSBudW1iZXJzCiogQ2VudHJhbCBsaW1pdCB0aGVvcmVtCgojIyMjIFJlZmVyZW5jZQoKKiBXYXNzZXJtYW4gKDIwMDQpLCBDaGFwdGVycyAyLCAzLCBhbmQgNQoKIyMgU2FtcGxlIFNwYWNlCgpTYW1wbGUgc3BhY2UgJFxPbWVnYSQgaXMgdGhlIHNldCBvZiBwb3NzaWJsZSBvdXRjb21lcy4KCiogZXhhbXBsZXM6IFwoXE9tZWdhID0gXHtILCBUXH0gXCkgZm9yIGEgY29pbiB0b3NzCiAgICAKKiBcKFxPbWVnYSA9IFx7SEgsIEhULCBUSCwgVFRcfVwpIGZvciB0d28gY29pbiB0b3NzZXMKCk91dGNvbWUgJFxvbWVnYSQ6IGFuIGVsZW1lbnQgb2Ygc2FtcGxlIHNwYWNlICRcT21lZ2EkCgoqIGV4YW1wbGU6ICRcb21lZ2E9SCQgZm9yIGEgY29pbiB0b3NzICAKCkV2ZW50ICRBJDogc3Vic2V0IG9mIHNhbXBsZSBzcGFjZSAkXE9tZWdhJAoKKiBleGFtcGxlOiAkXE9tZWdhID0gXHtIVCwgVEhcfSQgZm9yIHRvdyBjb2luIHRvc3NlcyAgCgpQcm9iYWJpbGl0eSAkUChBKSQgb2YgYW4gZXZlbnQgJEEkIHJlcHJlc2VudHMgdGhlIGZyZXF1ZW5jeSBvZiBvYnNlcnZpbmcgJEEkCgoqIFByb2JhYmlsaXR5IGRpc3RyaWJ1dGlvbiAkUCQgaXMgYSBmdW5jdGlvbiB0aGF0IHNhdGlzZmllczoKCiAgICArICRQKEEpIFxnZSAwJCBmb3IgZXZlcnkgZXZlbnQgJEEkICAKICAgICsgJFAoXE9tZWdhKSA9IDEkICAKICAgICsgSWYgJEEkIGFuZCAkQiQgYXJlIGRpc2pvaW50LCAkUChBXGN1cCBCKSA9IFAoQSkgKyBQKEIpJAoKIyMgUmFuZG9tIFZhcmlhYmxlCgpSYW5kb20gdmFyaWFibGUgJFgkIGlzIGEgbWFwcGluZyBmcm9tIGVhY2ggb3V0Y29tZSAkXG9tZWdhXGluXE9tZWdhJCB0byBhIHJlYWwgbnVtYmVyCgoqIGV4YW1wbGU6ICRYJCBpcyB0aGUgbnVtYmVyIG9mIGhlYWRzIGluIHR3byBjb2luIHRvc3NlcwoKICAgIC0gJFgoXG9tZWdhKT0xJCBmb3IgYm90aCAkXG9tZWdhPUhUJCBhbmQgJFxvbWVnYT1USCQuCgpQcm9iYWJpbGl0eSBmb3IgYSByYW5kb20gdmFyaWFibGUgZm9yIHRoZSBldmVudHMgdGhhdCBnaXZlIHRoZSB2YWx1ZTogIAoKICAgIC0gJFAoWD0xKSA9IFAoe0hULFRIfSkgPSAxLzIkICAKICAgIC0gJFAoWFxsZSAxKSA9IFAoe1RULEhULFRIfSkgPSAzLzQkICAKCiogSW4gZ2VuZXJhbDoKCiAgICAtICRQKFg9eCkgPSBQKFxvbWVnYVxpblxPbWVnYTsgWChcb21lZ2EpPXgpJCAgCiAgICAtICRQKFhcaW4gQSkgPSBQKFxvbWVnYVxpblxPbWVnYTsgWChcb21lZ2EpPUEpJCAgCgojIyBQcm9iYWJpbGl0eSBmdW5jdGlvbiAob3IgcHJvYmFiaWxpdHkgbWFzcyBmdW5jdGlvbikKCiogRm9yIGRpc2NyZXRlIHJhZG9tIHZhcmlhYmxlOiAkZl9YKHgpPVAoWD14KSQKCiogRXhhbXBsZTogIyBvZiBoZWFkcyBpbiB0d28gY29pbiB0b3NzZXMKCmBgYHtyfQpwID0gMC4zCnggPSAwOjIKZiA9IGMoKDEtcCleMiwgMipwKigxLXApLCBwXjIpCnBsb3QoeCwgZiwgdHlwZT0iaCIsIGx3ZD0zLCB5bGltPWMoMCwgMSkpICAjICJoIiBmb3IgaGlzdG9ncmFtLWxpa2UKYGBgCgojIyBQcm9iYWJpbGl0eSBkZW5zaXR5IGZ1bmN0aW9uIChQREYpCgoqIEZvciBjb250aW51b3VzIHJhbmRvbSB2YXJpYWJsZSAkWCQuCgogICAgLSAkZl9YKHgpIFxnZSAwJCBmb3IgYWxsICR4JCAgCiAgICAtICRcaW50X3stXGluZnR5fV57XGluZnR5fSBmX1goeClkeCA9IDEkICAKICAgIAogICAgLSAkUChhPFg8YikgPSBcaW50X3thfV57Yn0gZl9YKHgpZHgkICAKCiogRXhhbXBsZTogIFVuaWZvcm0gZGlzdHJpYnV0aW9uIGluICRbMCwxXSQKClByb2JhYmlsaXR5IGRlbnNpdHkgZnVuY3Rpb246CmBgYHtyfQp4ID0gc2VxKC0wLjUsIDEuNSwgMC4wMSkKZiA9IGR1bmlmKHgsIDAsIDEpCnBsb3QoeCwgZiwgdHlwZT0ibCIpCmBgYAoKIyMgQ3VtdWxhdGl2ZSBkaXN0cmlidXRpb24gZnVuY3Rpb24gKENERikKCiogJEZfWCh4KT1QKFhcbGUgeCkkICAKCiogQ0RGIGlzIHJlbGF0ZWQgd2l0aCBQREYgYXM6CgogICAgLSAkRl9YKHgpID0gXGludF97LVxpbmZ0eX1ee3h9IGZfWCh4KWR4JCAgCiAgICAtICRmX1goeCkgPSBGJ19YKHgpJCB3aGVyZSAkRl9YJCBpcyBkaWZmZXJlbnRpYWJsZQoKKiBDREYgYWxsb3dzIGRlYWxpbmcgd2l0aCBkaXNjcmV0ZSBhbmQgY29udGludW91cyByYW5kb20gdmFyaWFibGVzIGluIGEgdW5pZmllZCB3YXkuCgojIyBJbnZlcnNlIENERiAob3IgcXVhbnRpbGUgZnVuY3Rpb24pCgoqICRGXnstMX0ocSkgPSBcaW5mXHt4OiBGKHgpPnFcfSQgCgoqIEV4YW1wbGU6ICMgb2YgaGVhZHMgaW4gdHdvIGNvaW4gdG9zc2VzCgpgYGB7cn0KcCA9IDAuNQpmID0gYygoMS1wKV4yLCAyKnAqKDEtcCksIHBeMikKIyBDREYKRiA9IHJlcCggYygwLCBjdW1zdW0oZikpLCBlYWNoPTIpCnggPSBjKC0xLCByZXAoMDoyLCBlYWNoPTIpLCAzKQpwYXIobWZyb3c9YygxLCAyKSkgICMgc2lkZSBieSBzaWRlIApwbG90KHgsIEYsIHR5cGU9ImwiKQojIEludmVyc2UgQ0RGCnBsb3QoRiwgeCwgdHlwZT0ibCIsIHhsYWI9InEiLCB5bGFiPSJ4PUZeLTEocSkiKQpgYGAKCiogRXhhbXBsZTogVW5pZm9ybSBkaXN0cmlidXRpb24gaW4gJFswLDFdJAoKYGBge3J9CnggPSBzZXEoLTAuNSwgMS41LCAwLjAxKQojIENERgpGID0gcHVuaWYoeCwgMCwgMSkKcGFyKG1mcm93PWMoMSwgMikpICAjIHNpZGUgYnkgc2lkZSAKcGxvdCh4LCBGLCB0eXBlPSJsIikKIyBJbnZlcnNlIENERgpwbG90KEYsIHgsIHR5cGU9ImwiLCB4bGFiPSJxIiwgeWxhYj0ieD1GXi0xKHEpIikKYGBgCgojIERpc2NyZXRlIFJhbmRvbSBWYXJpYWJsZXMKCiRYIFxzaW0gRiQgbWVhbnMgJFgkIGhhcyBkaXN0cmlidXRpb24gJEYkCgojIyBVbmlmb3JtIGRpc3RyaWJ1dGlvbiBvbiBpbnRlZ2VycyAkezEsLi4uLGt9JDoKCiQkZih4KSA9IFxmcmFjezF9e2t9JCQKCmBgYHtyfQprID0gNQp4ID0gMTprCmYgPSBtYXRyaXgoMS9rLCAxLCBrKQpwbG90KHgsIGYsIHR5cGU9ImgiLCBsd2Q9MywgeWxpbT1jKDAsMSkpCmBgYAoKIyMgQmVybm91bGxpIERpc3RyaWJ1dGlvbgoKJCRYIFxzaW0gXG1ib3h7QmVybm91bGxpfShwKSQkCgoqIGNvaW4gdG9zcyB3aXRoIHRoZSBwcm9iYWJpbGl0eSBvZiBoZWFkICRwJAoKJCRQKFg9MSkgPSBwJCQKJCRQKFg9MCkgPSAxLXAkJAoKVGhlIHByb2JhYmlsaXR5IChtYXNzKSBmdW5jdGlvbiBjYW4gYmUgcmVwcmVzZW50ZWQgYXM6CiQkZih4KSA9IHBeeCgxLXApXnsxLXh9JCQKYGBge3J9CnAgPSAwLjMKeCA9IDA6MQpmID0gcF54ICogKDEtcCleKDEteCkgICMgPSBjKDEtcCwgcCkKcGxvdCh4LCBmLCB0eXBlPSJoIiwgbHdkPTMsIHlsaW09YygwLDEpKQpgYGAKCiMjIEJpbm9taWFsIERpc3RyaWJ1dGlvbgoKJCRYIFxzaW0gXG1ib3h7Qmlub21pYWx9KG4sIHApJCQKCiogbnVtYmVyIG9mIGhlYWRzIGluICRuJCBjb2luIHRvc3NlcyB0aGUgcHJvYmFiaWxpdHkgb2YgaGVhZCAkcCQKCiQkZih4KSA9IHtuIFxjaG9vc2UgeH0gcF54KDEtcClee24teH0kJAoke24gXGNob29zZSB4fT1cZnJhY3tuIX17eCEobi14KSF9JDogdGhlIG51bWJlciBvZiB3YXlzIGNob29zaW5nICR4JCBpdGVtcyBvdXQgb2YgJG4kLgoKYGBge3J9Cm4gPSA1CnAgPSAwLjYKeCA9IDA6bgpmID0gY2hvb3NlKG4seCkgKiBwXnggKiAoMS1wKV4obi14KQojZiA9IGRiaW5vbSh4LCBuLCBwKQpwbG90KHgsIGYsIHR5cGU9ImgiLCBsd2Q9MywgeWxpbT1jKDAsMSkpCmBgYAoKIyMjIFByb2JhYmlsaXR5IGRpc3RyaWJ1dGlvbnMgaW4gUgoKTW9zdCBwb3B1bGFyIGRpc3RyaWJ1dGlvbnMgYXJlIGF2YWlsYWJsZSB3aXRoIHRoZSBjb252ZW50aW9uOgoKKiBgZC4uLigpYDogcHJvYmFiaWxpdHkgZGVuc2l0eSBvciBtYXNzIGZ1bmN0aW9uCiogYHAuLi4oKWA6IENERgoqIGBxLi4uKClgOiBRdWFudGlsZSBmdW5jdGlvbiAoaW52ZXJzZSBDREYpCiogYHIuLi4oKWA6IGRyYXcgc2FtcGxlcwoKYGBge3J9CiMgYmlub21pYWwgZGlzdHJpYnV0aW9uCm4gPSA1CnAgPSAwLjMKcGFyKG1mY29sPWMoMiwyKSkgICMgaW4gMngyIGdyaWQKIyBtYXNzIGZ1bmN0aW9uCnggPSAwOm4KcGxvdCh4LCBkYmlub20oeCwgbiwgcCksIHR5cGU9ImgiLCBsd2Q9MywgeWxpbT1jKDAsMSkpCiMgQ0RGCnggPSBzZXEoMCwgbiwgMC4wNSkKcGxvdCh4LCBwYmlub20oeCwgbiwgcCksIHR5cGU9ImwiKQojIFF1YW50aWxlIGZ1bmN0aW9uCnEgPSBzZXEoMCwgMSwgMC4wMSkKcGxvdChxLCBxYmlub20ocSwgbiwgcCksIHR5cGU9ImwiKQojIGRyYXcgc2FtcGxlcwpwbG90KHJiaW5vbSgxMDAsIG4sIHApKQpgYGAKCiMjIFBvaXNzb24gRGlzYnJpYnV0aW9uCgokJFggXHNpbSBcbWJveHtQb2lzc29ufShcbGFtYmRhKSQkCgoqIGNvdW50IG9mIGV2ZW50cyB0aGF0IG9jY3VyIGF0IGF2ZXJhZ2UgcmF0ZSAkXGxhbWJkYSQgCgokJGYoeCkgPSBlXnstXGxhbWJkYX0gXGZyYWN7XGxhbWJkYV54fXt4IX0kJAoKYGBge3J9CmxhbWJkYSA9IDIKeCA9IDA6MTAKZiA9IGRwb2lzKHgsIGxhbWJkYSkKcGxvdCh4LCBmLCB0eXBlPSJoIiwgbHdkPTMsIHlsaW09YygwLDEpKQpgYGAKCiMjIE11bHRpbm9taWFsIGRpc3RyaWJ1dGlvbgoKJCRYIFxzaW0gXG1ib3h7TXVsdGlub21pYWx9KG4scCkkJAoKKiBGb3IgJGskIHBvc3NpYmxlIG91dGNvbWVzIHdpdGggcHJvYmFiaWxpaWVzICRwPShwXzEsLi4scF9rKSQsCm51bWJlciBvZiBlYWNoIG91dGNvbWUgYWZ0ZXIgJG4kIGRyYXdzICRYPShYXzEsLi4uLFhfaykkCgokJGYoeCkgPSB7biBcY2hvb3NlIHhfMS4uLnhfa30gcF8xXnt4XzF9Li4ucF9rXnt4X2t9JCQKJHtuIFxjaG9vc2UgeF8xLi4ueF9rfSA9IFxmcmFje24hfXt4XzEhLi4ueF9rIX0kCgpgYGB7cn0KcCA9IGMoMC40LCAwLjUsIDAuMSkgICMgaz0zCm4gPSAxMApkbW4gPC1mdW5jdGlvbih4MSwgeDIpewogIGlmKHgxK3gyID4gbil7CiAgICByZXR1cm4oMCkgICMgY2Fubm90IGhhcHBlbgogIH1lbHNlewogICAgeCA9IGMoeDEsIHgyLCBuLXgxLXgyKSAgIyBzdW0gdXAgdG8gbgogICAgcmV0dXJuKGRtdWx0aW5vbSh4LCBwcm9iPXApKQogIH0KfQp4MSA9IHgyID0gMDpuCmYgPSBvdXRlcih4MSwgeDIsIFZlY3Rvcml6ZShkbW4pKQpwZXJzcCh4MSwgeDIsIGYsIHRoZXRhPTYwKQpgYGAKCiMgQ29udGludW91cyBSYW5kb20gVmFyaWFibGVzCgojIyBVbmlmb3JtIERpc3RyaWJ1dGlvbgoKJCRYIFxzaW0gXG1ib3h7VW5pZm9ybX0oYSxiKSQkCgokJGYoeCkgPSBcbGVmdFx7XGJlZ2lue2FycmF5fXtjbH0gXGZyYWN7MX17Yi1hfSAmIFxtYm94e2ZvciB9IHggXGluIFthLGJdXFwKMCAmIFxtYm94e290aGVyd2lzZX1cZW5ke2FycmF5fVxyaWdodC4kJAoKYGBge3J9CnggPSBzZXEoLTIsIDIsIDAuMDEpCmYgPSBkdW5pZih4LCAtMSwgMSkKcGxvdCh4LCBmLCB0eXBlPSJsIikKYGBgCgojIyBFeHBvbmVudGlhbCBEaXN0cmlidXRpb24KCiQkWCBcc2ltIFxtYm94e0V4cH0oXGxhbWJkYSkkJAoKKiBJbnRlcnZhbCBvZiBldmVudHMgaGFwcGVuaW5nIGF0IHJhdGUgJFxsYW1iZGEkCgokJGYoeCkgPSBcbGFtYmRhIGVeey1cbGFtYmRhIHh9JCQKCkRlZmluZWQgZm9yICR4IFxnZSAwJCBhbmQgJFxsYW1iZGEgPiAwJC4KCmBgYHtyfQpsYW1iZGEgPSAuNQp4ID0gc2VxKC01LCAxMCwgMC4xKQpmID0gZGV4cCh4LCBsYW1iZGEpCnBsb3QoeCwgZiwgdHlwZT0ibCIpCmBgYAoKSXQgaXMgc29tZXRpbWVzIHBhcmFtZXRlcml6ZWQgYnkgJFxiZXRhID0gXGZyYWN7MX17XGxhbWJkYX0kLgoKIyMgR2FtbWEgRGlzdHJpYnV0aW9uCgokJFggXHNpbSBcbWJveHtHYW1tYX0oYSxiKSQkCgpTdW0gb2YgJGEkIGluZGVwZW5kZW50IHNhbXBsZXMgZnJvbSBFeHAoJGIkKQoKJCRmKHgpID0gXGZyYWN7Yl5hfXtcR2FtbWEoYSl9IHhee2EtMX0gZV57LWJ4fSQkCndoZXJlIHRoZSAiR2FtbWEgZnVuY3Rpb24iIGlzIGRlZmluZWQgYXMKJCRcR2FtbWEoYSkgPVxpbnRfMF5caW5mdHkgdF57YS0xfWVeey10fWR0JCQKRm9yIGludGVnZXIgdmFsdWVzIG9mICRhJCwgJFxHYW1tYShhKT1hISQuCgpgYGB7cn0KYSA9IDEgICMgc2FtZSBhcyBleHAKYiA9IDEKeCA9IHNlcSgtMiwgMTAsIDAuMDEpCmYgPSBkZ2FtbWEoeCwgYSwgYikKcGxvdCh4LCBmLCB0eXBlPSJsIikKZm9yIChhIGluIDI6Nil7ICAjIHNlZSB0aGUgY2hhbmdlIHdpdGggYQogIGxpbmVzKHgsIGRnYW1tYSh4LCBhLCBiKSwgY29sPWEpCn0KYGBgCgpGb3IgaW5kZXBlbmRlbnQgcmFuZG9tIHZhcmlhYmxlcyAkWF9pIFxzaW0gXG1ib3h7R2FtbWF9KGFfaSxiKSQsIAokJFxzdW1fe2k9MX1ebiBYX2kgXHNpbSBcbWJveHtHYW1tYX0oXHN1bV97aT0xfV5uIGFfaSwgYikkJAoKIyMgTm9ybWFsIChHYXVzc2lhbikgRGlzdHJpYnV0aW9uCgokJFggXHNpbSBcbWF0aGNhbHtOfShcbXUsXHNpZ21hKSQkCm1lYW4gJFxtdSQgYW5kIHN0YW5kYXJkIGRldmlhdGlvbiAkXHNpZ21hJAoKJCRmKHgpID0gXGZyYWN7MX17XHNpZ21hXHNxcnR7MlxwaX19IGVeey1cZnJhY3soeC1cbXUpXjJ9ezJcc2lnbWFeMn19JCQKCgpgYGB7cn0KeCA9IHNlcSgtNSwgNSwgMC4xKQpmID0gZG5vcm0oeCkgICMgZGVmYXVsdDogbXU9MCwgc2lnbWE9MQpwbG90KHgsIGYsIHR5cGU9ImwiKQpgYGAKCiMgRXhwZWN0YXRpb24gCgpFeHBlY3RhdGlvbiAob3IgbWVhbiwgb3IgZmlyc3QgbW9tZW50KSBvZiByYW5kb20gdmFyaWFibGUgJFgkOgoKJCRFKFgpID0gXGludCB4IGRGKHgpJCQKCiogZm9yIGRpc2NyZXRlICRYJDogCgokJEUoWCkgPSBcc3VtX3ggeCBmKHgpJCQgCgoqIGZvciBjb250aW51b3VzICRYJDogCgokJEUoWCkgPSBcaW50X3stXGluZnR5fV57XGluZnR5fSB4IGYoeCkgZHgkJAoKRXhwZWN0YXRpb24gaXMgb2Z0ZW4gZGVub3RlZCBhcyAkRShYKT1cbXVfWD1cbXUkLgoKIyMgUHJvcGVydGllcyBvZiBFeHBlY3RhdGlvbnMKCiogRXhwZWN0YXRpb24gb2YgYSBmdW5jdGlvbiAkWT1yKFgpJDoKCiQkRShZKSA9IEUocihYKSkgPSBcaW50IHIoeClkRl9YKHgpJCQKCiogTGluZWFyIHN1bTogCgokJEUoXHN1bV9pIGFfaSBYX2kpID1cc3VtX2kgYV9pIEUoWF9pKSQkCgoqIFByb2R1Y3Qgb2YgaW5kZXBlbmRlbnQgcmFuZG9tIHZhcmlhYmxlczoKCiQkRShccHJvZF9pIFhfaSkgPVxwcm9kX2kgRShYX2kpJCQKCiMgVmFyaWFuY2UKClZhcmlhbmNlIGlzIGEgbWVhc3VyZSBvZiB0aGUgc3ByZWFkIG9mIGEgZGlzdHJpYnV0aW9uLgoKKiBWYXJpYW5jZSAkVihYKT1cc2lnbWFfWF4yPVxzaWdtYV4yJCBmb3IgYSByYW5kb20gdmFyaWFibGUgJFgkIHdpdGggdGhlIG1lYW4gJFxtdSQ6CgokJFYoWCkgPSBFKChYLVxtdSleMikgPSBcaW50KHgtXG11KV4yIGRGKHgpJCQKCiogJFYoWCkgPSBFKFheMiktXG11XjIkCgoqICRWKGFYK2IpID0gYV4yIFYoWCkkCgoqIGZvciBpbmRlcGVuZGVudCByYW5kb20gdmFyaWFibGVzOgoKJCRWKFxzdW1faSBhX2kgWF9pKSA9XHN1bV9pIGFfaV4yIFYoWF9pKSQkCgojIExpbWl0IFRoZW9yeQoKKiBQcm9iYWJpbGl0eSB0aGVvcnkgYWxsb3dzIHVzIHRvIHByZWRpY3Qgd2hhdCBoYXBwZW5zIHdoZW4gd2UgZ2F0aGVyIGEgbGFyZ2Ugc2FtcGxlLgoKIyMgVGhlIExhdyBvZiBMYXJnZSBOdW1iZXJzCgpUaGUgc2FtcGxlIGF2ZXJhZ2UgJFxiYXJ7WH1fbj1cZnJhY3sxfXtufVxzdW1fe2k9MX1ebiBYX2kkIGNvbnZlcmdlcyBpbiBwcm9iYWJpbGl0eSB0byB0aGUgZXhwZWN0YXRpb24gJFxtdT1FRShYX2kpJC4KCiogJFhfbiQgY29udmVyZ2VzIHRvICRYJCAqaW4gcHJvYmFiaWxpdHkqCgokJFhfblxzdGFja3JlbHtQfXtccmlnaHRhcnJvd31YJCQKCkZvciBldmVyeSAkXGVwc2lsb24+MCQsIGFzICRuXHJpZ2h0YXJyb3dcaW5mdHkkLAokJFAofFhfbi1YfD5cZXBzaWxvbilccmlnaHRhcnJvdyAwJCQKCiMjIFRoZSBDZW50cmFsIExpbWl0IFRoZW9yZW0KCkZvciBhbnkgZGlzdHJpYnV0aW9uIG9mICRYJCB3aXRoIG1lYW4gJFxtdSQgYW5kIHZhcmlhbmNlICRcc2lnbWFeMiQsIHRoZSBkaXN0cmlidXRpb24gb2Ygc2FtcGxlIGF2ZXJhZ2VzICRYX24kIGZvbGxvd3MgYSBOb3JtYWwgZGlzdHJpYnV0aW9uICRcbWF0aGNhbHtOfShcbXUsXGZyYWN7XHNpZ21hXjJ9e259KSQKCiogRGV2aWF0aW9uIG9mIHRoZSBzYW1wbGUgYXZlcmFnZSBmcm9tIHRoZSB0cnVlIG1lYW4sIHNjYWxlZCBieSAkbiQgYXMgJFxzcXJ0e259KFxiYXJ7WH1fbi1cbXUpJCwgY29udmVyZ2VzIGluIGRpc3RyaWJ1dGlvbiB0byBhIE5vcm1hbCBkaXN0cmlidXRpb24gJFxtYXRoY2Fse059KDAsXHNpZ21hXjIpJC4KCiogJFhfbiQgY29udmVyZ2VzIHRvICRYJCAqaW4gZGlzdHJpYnV0aW9uKgoKJCRYX25cbGVhZHN0byBYJCQKClRoZSBjdW11bGF0aXZlIGRpc3RyaWJ1dGlvbiBmdW5jdGlvbiAkRl9uKFhfbikkIGNvbnZlcmdlcyB0byAkRihYKSQgYXQgZXZlcnkgcG9pbnQgJHgkIHdoZXJlICRGJCBpcyBjb250aW51b3VzLgokJFxsaW1fe25ccmlnaHRhcnJvd1xpbmZ0eX1GX24oeCk9Rih4KSQkCgojIEV4ZXJjaXNlCgojIyAxLiBQREYgYW5kIENERgoKMSkgRm9yIGFuIGV4cG9uZW50aWFsIGRpc3RyaWJ1dGlvbiwgcGxvdCB0aGUgUERGLCBDREYgYW5kIGludmVyc2UgQ0RGIChxdWFudGlsZSBmdW5jdGlvbikgYnkgYGRleHBgLCBgcGV4cGAgYW5kIGBxZXhwYC4KCmBgYHtyfQoKYGBgCgoyKSBEZXJpdmUgdGhlIG1hdGhlbWF0aWNhbCBmb3JtIG9mIHRoZSBDREYgb2YgdGhlIGV4cG9uZW50aWFsIGRpc3RyaWJ1dGlvbiBmcm9tIGl0cyBQREYgCiQkZih4KSA9IFxsYW1iZGEgZV57LVxsYW1iZGEgeH0kJAoKCgphbmQgY29tcGFyZSB3aXRoIHRoZSBwbG90IGFib3ZlLgoKYGBge3J9CgpgYGAKCjMpIERlcml2ZSB0aGUgbWF0aGVtYXRpY2FsIGZvcm0gb2YgdGhlIGludmVyc2UgQ0RGIChxdWFudGlsZSBmdW5jdGlvbikgb2YgdGhlIGV4cG9uZW50aWFsIGRpc3RyaWJ1dGlvbgoKCgphbmQgY29tcGFyZSB3aXRoIHRoZSBwbG90IGFib3ZlLgoKCmBgYHtyfQoKYGBgCgojIyAyLiBSZWxhdGlvbnNoaXBzIGJldHdlZW4gZGlzdHJpYnV0aW9ucwoKMSkgTWFrZSBhIHNhbXBsZSBieSBzdW1taW5nIHNhbXBsZXMgZnJvbSBCZXJub3VsbGkgZGlzdHJpYnV0aW9uLiBQbG90IGl0cyBoaXN0Z3JhbSBhbmQgY2hlayBpZiB0aGF0IGZpdHMgd2l0aCB0aGUgQmlub21pYWwgZGlzdHJpYnV0aW9uIGdpdmUgYnkgYGRiaW5vbSgpYC4KCmBgYHtyfQoKYGBgCgoyKSBCeSB0YWtpbmcgJG4kIGxhcmdlIGFuZCBzY2FsaW5nICRwJCBieSAkXGZyYWN7MX17bn0kIGluIEJpbm9taWFsIGRpc3RyaWJ1dGlvbiwgc2VlIGlmIHRoZSBkaXN0cmlidXRpb24gY29tZXMgY2xvc2UgdG8gUG9pc3NvbiBkaXN0cmlidXRpb24KCmBgYHtyfQoKYGBgCgozKSBEcmF3IGEgc2VxdWVuY2Ugb2Ygc2FtcGxlcyBmcm9tIGEgQmVybm91bGxpIGRpc3RyaWJ1dGlvbiB3aXRoIHNtYWxsICRwJC4gTWFrZSBhIGhpc3RvZ3JhbSBvZiB0aGUgdGltZSBpbnRlcnZhbHMgYmV0d2VlbiAxcyBhbmQgc2VlIHdoYXQgZGlzdHJpYnV0aW9uIGl0IGZvbGxvd3MuCgpgYGB7cn0KCmBgYAoKNCkgRGl2aWRlIHRoZSBhYm92ZSBzZXF1ZW5jZSBpbnRvIHRpbWUgYmlucyBvZiBsZW5ndGggJFQkIGFuZCBjb3VudCAxcyBpbiBlYWNoIGJpbi4gV2hhdCBkaXN0cmlidXRpb24gZG9lcyBpdCBmb2xsb3c/CgpgYGB7cn0KCmBgYAoKNSkgQnkgc3VtbWluZyB1cCBtdWx0aXBsZSBzYW1wbGVzIGZyb20gZXhwb25lbnRpYWwgZGlzdHJpYnV0aW9uLCBjaGVjayB3aGV0aGVyIHRoYXQgZm9sbG93cyBHYW1tYSBkaXN0cmlidXRpb24uCgpgYGB7cn0KCmBgYAoKNikgU2VlIGluIHdoYXQgY2FzZSBHYW1tYSBkaXN0cmlidXRpb24gYmVjb21lIGNsb3NlIHRvIHRoZSBub3JtYWwgZGlzdHJpYnV0aW9uLgoKIyMgMy4gRXhwZWN0YXRpb24gYW5kIFZhcmlhbmNlCgoqaXMgb3B0aW9uYWwgZm9yIHRob3NlIHdpdGggbWF0aGVtYXRpY2FsIGJhY2tncm91bmQKCjEpIERlcml2ZSB0aGUgbWVhbiBhbmQgdGhlIHZhcmlhbmNlIG9mIEJlcm5vdWxsaSBkaXN0cmlidXRpb24uCgoKCjIpIERlcml2ZSB0aGUgbWVhbiBhbmQgdGhlIHZhcmlhbmNlIG9mIEJpbm9taWFsIGRpc3RyaWJ1dGlvbi4KCgoKMykgRHJpdmUgdGhlIG1lYW4gYW5kIHRoZSB2YXJpYW5jZSBvZiB1bmlmb3JtIGRpc3RyaWJ1dGlvbi4KCgoKNCopIENvbXB1dGUgdGhlIG1lYW4gb2YgdGhlIGV4cG9uZW50aWFsIGRpc3RyaWJ1dGlvbiBmcm9tIFBERjoKJCRFKFgpID0gXGludF8wXlxpbmZ0eSB4IGYoeCkgZHgkJAoKCgo1KikgQ29tcHV0ZSB0aGUgbWVhbiBvZiB0aGUgZXhwb25lbnRpYWwgZGlzdHJpYnV0aW9uIGZyb20gQ0RGOgokJEUoWCkgPSBcaW50IHggZEYoeCkgPSBcaW50XzBeMSBGXnstMX0ocSkgZHEkJAoKCgo2KikgRGVyaXZlIHRoZSB2YXJpYW5jZSBvZiB0aGUgZXhwb25lbnRpYWwgZGlzdHJpYnV0aW9uLgoKCgo3KSBEZXJpdmUgdGhlIG1lYW4gYW5kIHRoZSB2YXJpYW5jZSBvZiBHYW1tYSBkaXN0cmlidXRpb24gYXMgYSBzdW0gb2YgdGhlIHNhbXBsZXMgZnJvbSBleHBvbmVudGlhbCBkaXN0cmlidXRpb24uIAoKCg==