Creative Commons License

1 Introduction

Inference was only correct if distributional assumptions were satisfied

  • e.g Normal distribution

  • equal variance

  • The \(p\)-value: \(\text{P}_0\left[ \vert T\vert \geq \vert t \vert \right]\).

    • Calculated using the null distribution of \(T\) that we derived under the assumptions
    • In correct if assumptions are violated
  • \(95\%\) CI also builds upon these assumptions. If they are invalid then the intervals will not contain the population parameter with 95% probability.

  • Asymptotic theory is more difficult to place: the \(t\)-test is asymptotically non-parametric because for very large samples the distributional assumptions of normality are no longer important.

  • If assumptions hold the parametric approach

    • more efficient: larger power with same sample size + smaller CI.
    • more flexible: easier to analyse data with complex designs

1.1 Cholesterol example

  • Cholesterol concentration in blood measured for
    • 5 patients (group=1) two days upon a stroke
    • 5 healthy subject (groep=2).
  • Is cholesterol concentration of hart patients and healthy subjects on average different?
chol <- read_tsv("https://raw.githubusercontent.com/GTPB/PSLS20/master/data/chol.txt")
chol$group <- as.factor(chol$group)
nGroups <- table(chol$group)
n <- sum(nGroups)
chol

  • Possibly outliers
  • Difficult to assess distributional assumptions when only 5 observations are available.

2 Rank Tests

  • Important group of non-parametric test
    • Non-parametric,
    • Exact \(p\)-values using a permutation null distribution.
    • No need for separate permutation distribution for each new dataset.
    • Permutation null distribution of rank tests only depends on sample size
    • Robust to outliers

3 Ranks

Rank tests start from rank-transformed data.

  • Let \(Y_1, \ldots, Y_n\).
  • In the absence of ties \[R_i=R(Y_i) = \#\{Y_j: Y_j\leq Y_i; j=1,\ldots, n\}\]
  • Smallest observation has rank 1, second smallest rank 2, … , largest observation gets rank \(n\)
chol$cholest
 [1] 244 206 242 278 236 188 212 186 198 160
rank(chol$cholest)
 [1]  9  5  8 10  7  3  6  2  4  1

3.1 Ties

Sometimes ties occur: two observations with identical values

withTies <- c(403, 507, 507, 610, 651, 651, 651, 830, 900)
rank(withTies)
[1] 1.0 2.5 2.5 4.0 6.0 6.0 6.0 8.0 9.0
  • Ties: 507 occurs twice, 651 occurs 3 times

  • If ties occur midranks are used.

  • midrank of observation \(Y_i\) becomes \[\begin{eqnarray*} R_i &=& \frac{ \#\{Y_j: Y_j\leq Y_i\} + ( \#\{Y_j: Y_j < Y_i\} +1)}{2}. \end{eqnarray*}\]


3.2 Ranks of pooled sample

  • Let \(Y_{ij}\), \(i=1,\ldots, n_j\) be observations from two treatment groups \(j=1,2\).
  • They can also be represented by \(Z_1,\ldots, Z_n\) (\(n=n_1+n_2\)), the outcomes of the pooled sample
t(chol)
        [,1]  [,2]  [,3]  [,4]  [,5]  [,6]  [,7]  [,8]  [,9]  [,10]
group   "1"   "1"   "1"   "1"   "1"   "2"   "2"   "2"   "2"   "2"  
cholest "244" "206" "242" "278" "236" "188" "212" "186" "198" "160"
z <- chol$cholest
z
 [1] 244 206 242 278 236 188 212 186 198 160
rank(z)
 [1]  9  5  8 10  7  3  6  2  4  1

4 Wilcoxon-Mann-Whitney Test

Simultaneously developed by Wilcoxon, and, Mann and Whitney: Wilcoxon-Mann-Whitney, Wilcoxon rank sum test or Mann-Whitney U test

4.1 Hypotheses

Under \(H_0\) the distributions of the two groups are equal \[H_0: f_1=f_2\]

Under the alternative \(H_1\) the distributions differ in location \[H_1: \mu_1\neq \mu_2\]

\(H_1\) assumes location-shift, we will relax this assumption later on.

4.2 Test statistic

Classic T-test: difference in sample means \(\bar{Y}_1-\bar{Y}_2\).

Here: Difference in sample means based on rank transformed data

Ranks based on the pooled sample (upon joining the observations from the two groups): \(R_{ij}=R(Y_{ij})\) is de rank of observation \(Y_{ij}\) in the pooled sample.

\[ T = \frac{1}{n_1}\sum_{i=1}^{n_1} R(Y_{i1}) - \frac{1}{n_2}\sum_{i=1}^{n_2} R(Y_{i2}) . \]

  • Under \(H_0\) we expect the average rank of the first group to be close to that of the second group so \(T\) is close to zero.

  • Under \(H_1\) we expect the mean ranks to differ so that \(T\) deviates from zero.

  • It is sufficient to only calculate \[S_1=\sum_{i=1}^{n_1} R(Y_{i1})\].

  • \(S_1\) is the sum of the ranks of the first group: rank sum test.

  • This holds because \[ S_1+S_2 = \text{sum of all ranks} = 1+2+\cdots + n=\frac{1}{2}n(n+1). \]

  • \(S_1\) (or \(S_2\)) is a good test statistic

  • Use permutations to determine the exact permutation distribution. (Permute the ranks between the groups)

  • For a given \(n\) and no ties the rank transformed data is always \[1, 2, \ldots, n\]

  • For given \(n_1\) en \(n_2\) the permutation distribution is always the same!

  • With current computing power this is not so important any more.


4.3 Standardized statistic

Often the standardized test statistic is used \[ T = \frac{S_1-\text{E}_{0}\left[S_1\right]}{\sqrt{\text{Var}_{0}\left[S_1\right]}}, \]

  • with \(\text{E}_{0}\left[S_1\right]\) and \(\text{Var}_{0}\left[S_1\right]\) the expect mean and variance of S1 under \(H_0\).

  • Under \(H_0\) \[ \text{E}_{0}\left[S_1\right]= \frac{1}{2}n_1(n+1) \;\;\;\;\text{ en }\;\;\;\; \text{Var}_{0}\left[S_1\right]=\frac{1}{12}n_1n_2(n+1). \]

  • Under \(H_0\) and when \(\min(n_1,n_2)\rightarrow \infty\) \[ T = \frac{S_1-\text{E}_{0}\left[S_1\right]}{\sqrt{\text{Var}_{0}\left[S_1\right]}} \rightarrow N(0,1). \]

Asymptotically the standardised statistic follows a standard normal distribution!


4.4 Cholesterol example

We illustrate the result for the cholesterol example using the R function wilcox.test.

wilcox.test(cholest ~ group, data = chol)

    Wilcoxon rank sum exact test

data:  cholest by group
W = 24, p-value = 0.01587
alternative hypothesis: true location shift is not equal to 0
  • We reject \(H_0\) (\(p=\) 0.016 \(<0.05\))

  • The output shows \(W=\) 24?

  • Lets calculate

S1 <- sum(rank(chol$cholest)[chol$group == 1])
S1
[1] 39
S2 <- sum(rank(chol$cholest)[chol$group == 2])
S2
[1] 16
  • Where does \(W=\) 24 comes from?

4.5 Mann and Whitney test

Mann and Whitney test in absence of ties: \[ U_1 = \sum_{i=1}^{n_1}\sum_{k=1}^{n_2} \text{I}\left\{Y_{i1}\geq Y_{k2}\right\}. \]

  • with \(\text{I}\left\{.\right\}\) an indicator that equals 1 if the expression is true and is zero otherwise.

  • U counts how many times an observation of the first group is larger or equal to an observation from the second group.

y1 <- subset(chol, group == 1)$cholest
y2 <- subset(chol, group == 2)$cholest
u1Hlp <- sapply(y1, function(y1i, y2) {
  y1i >= y2
}, y2 = y2)
colnames(u1Hlp) <- y1
rownames(u1Hlp) <- y2
u1Hlp
     244   206  242  278  236
188 TRUE  TRUE TRUE TRUE TRUE
212 TRUE FALSE TRUE TRUE TRUE
186 TRUE  TRUE TRUE TRUE TRUE
198 TRUE  TRUE TRUE TRUE TRUE
160 TRUE  TRUE TRUE TRUE TRUE
U1 <- sum(u1Hlp)
U1
[1] 24

It can be shown that \(U_1 = S_1 - \frac{1}{2}n_1(n_1+1).\)

S1 - nGroups[1] * (nGroups[1] + 1) / 2
 1 
24 
  1. \(U_1\) en \(S_1\) contain the same information
  2. \(U_1\) is also a rank statistic, and
  3. Exact test based on \(U_1\) and \(S_1\) are equivalent.

4.6 Probabilistic index

  • \(U_1\) has a better interpretation feature
  • Let \(Y_j\) a random observation from group \(j\) (\(j=1,2\)). Then \[\begin{eqnarray*} \frac{1}{n_1n_2}\text{E}\left[U_1\right] &=& \text{P}\left[Y_1 \geq Y_2\right]. \end{eqnarray*}\]

So we can estimate the probability by calculating the mean of all indicator variable values \(\text{I}\left\{Y_{i1}\geq Y_{k2}\right\}\). Note, that we did \(n_1 \times n_2\) comparisons

mean(u1Hlp)
[1] 0.96
U1 / (nGroups[1] * nGroups[2])
   1 
0.96 
  • Probability \(\text{P}\left[Y_1 \geq Y_2\right]\) is referred to as the probabilistic index.

  • It is the probability that a random observation of the first group is larger or equal than a random observation of the second group

  • If \(H_0\) holds \(\text{P}\left[Y_1 \geq Y_2\right]=\frac{1}{2}\).

  • R function wilcox.test does not return the Wilcoxon rank sum statistic. It returns the Mann-Whitney statistic \(U_1\).

  • Lets revisit the result

wTest <- wilcox.test(cholest ~ group, data = chol)
wTest

    Wilcoxon rank sum exact test

data:  cholest by group
W = 24, p-value = 0.01587
alternative hypothesis: true location shift is not equal to 0
U1
[1] 24
probInd <- wTest$statistic / prod(nGroups)
probInd
   W 
0.96 

Because \(p=\) 0.0159 \(<0.05\) we conclude at the \(5\%\) significance level that the mean cholesterol level of hart patients is larger then that of healthy subjects.

  • Note that we have assumed that the location-shift model is valid in this conclusion.
  • We also know that higher cholesterol level are more likely for hart patients then for healthy subjects and this probability is \(U1/(n_1\times n_2)=\) 96%.
  • We should assess the location shift assumption. But this is not possible with only 5 observations.

Without the location-shift assumption the conclusion in terms of the probabilistic index remains valid!

  • So when we do not assume location shift we test for

\[H_0: F_1=F_2 \text{ vs } H_1: P[Y_1 \geq Y_2] \neq 0.5.\]

4.7 Conclusion

There is a significant difference in the distribution of the cholesterol concentration of hart patients two days upon a stroke and that of healthy subject (\(p=\) 0.0159). It is more likely to observe higher cholesterol levels for hart patients then for healthy subjects. The point estimator for this probability is 96%.

LS0tCnRpdGxlOiAiOS4gTm9ucGFyYW1ldHJpYyBTdGF0aXN0aWNzIC0gV2lsY294b24tTWFubi1XaXRobmV5IHRlc3QiCmF1dGhvcjogIkxpZXZlbiBDbGVtZW50IgpkYXRlOiAic3RhdE9taWNzLCBHaGVudCBVbml2ZXJzaXR5IChodHRwczovL3N0YXRvbWljcy5naXRodWIuaW8pIgotLS0KCjxhIHJlbD0ibGljZW5zZSIgaHJlZj0iaHR0cHM6Ly9jcmVhdGl2ZWNvbW1vbnMub3JnL2xpY2Vuc2VzL2J5LW5jLXNhLzQuMCI+PGltZyBhbHQ9IkNyZWF0aXZlIENvbW1vbnMgTGljZW5zZSIgc3R5bGU9ImJvcmRlci13aWR0aDowIiBzcmM9Imh0dHBzOi8vaS5jcmVhdGl2ZWNvbW1vbnMub3JnL2wvYnktbmMtc2EvNC4wLzg4eDMxLnBuZyIgLz48L2E+CgpgYGB7ciBzZXR1cCwgaW5jbHVkZT1GQUxTRSwgY2FjaGU9RkFMU0V9CmtuaXRyOjpvcHRzX2NodW5rJHNldCgKICBpbmNsdWRlID0gVFJVRSwgY29tbWVudCA9IE5BLCBlY2hvID0gVFJVRSwKICBtZXNzYWdlID0gRkFMU0UsIHdhcm5pbmcgPSBGQUxTRSwgY2FjaGUgPSBUUlVFCikKbGlicmFyeSh0aWR5dmVyc2UpCmxpYnJhcnkoUm1pc2MpCnNldC5zZWVkKDE0MCkKYGBgCgoKIyBJbnRyb2R1Y3Rpb24KCkluZmVyZW5jZSB3YXMgb25seSBjb3JyZWN0IGlmIGRpc3RyaWJ1dGlvbmFsIGFzc3VtcHRpb25zIHdlcmUgc2F0aXNmaWVkCgotIGUuZyBOb3JtYWwgZGlzdHJpYnV0aW9uCi0gZXF1YWwgdmFyaWFuY2UKCi0gIFRoZSAkcCQtdmFsdWU6ICRcdGV4dHtQfV8wXGxlZnRbIFx2ZXJ0IFRcdmVydCBcZ2VxIFx2ZXJ0IHQgXHZlcnQgXHJpZ2h0XSQuCgoJLSBDYWxjdWxhdGVkIHVzaW5nIHRoZSBudWxsIGRpc3RyaWJ1dGlvbiBvZiAkVCQgdGhhdCB3ZSBkZXJpdmVkIHVuZGVyIHRoZSBhc3N1bXB0aW9ucwoJLSBJbiBjb3JyZWN0IGlmIGFzc3VtcHRpb25zIGFyZSB2aW9sYXRlZAoKLSAgJDk1XCUkIENJIGFsc28gYnVpbGRzIHVwb24gdGhlc2UgYXNzdW1wdGlvbnMuIElmIHRoZXkgYXJlIGludmFsaWQgdGhlbiB0aGUgaW50ZXJ2YWxzIHdpbGwgbm90IGNvbnRhaW4gdGhlIHBvcHVsYXRpb24gcGFyYW1ldGVyIHdpdGggOTUlIHByb2JhYmlsaXR5LgoKLSBBc3ltcHRvdGljIHRoZW9yeSBpcyBtb3JlIGRpZmZpY3VsdCB0byBwbGFjZTogdGhlICR0JC10ZXN0IGlzIGFzeW1wdG90aWNhbGx5IG5vbi1wYXJhbWV0cmljIGJlY2F1c2UgZm9yIHZlcnkgbGFyZ2Ugc2FtcGxlcyB0aGUgZGlzdHJpYnV0aW9uYWwgYXNzdW1wdGlvbnMgb2Ygbm9ybWFsaXR5IGFyZSBubyBsb25nZXIgaW1wb3J0YW50LgoKLSBJZiBhc3N1bXB0aW9ucyBob2xkIHRoZSBwYXJhbWV0cmljIGFwcHJvYWNoCgoJLSBtb3JlIGVmZmljaWVudDogbGFyZ2VyIHBvd2VyIHdpdGggc2FtZSBzYW1wbGUgc2l6ZSArIHNtYWxsZXIgQ0kuCgktIG1vcmUgZmxleGlibGU6IGVhc2llciB0byBhbmFseXNlIGRhdGEgd2l0aCBjb21wbGV4IGRlc2lnbnMKCi0tLQoKIyMgQ2hvbGVzdGVyb2wgZXhhbXBsZQoKLSBDaG9sZXN0ZXJvbCBjb25jZW50cmF0aW9uIGluIGJsb29kIG1lYXN1cmVkIGZvcgogIC0gNSBwYXRpZW50cyAoZ3JvdXA9MSkgdHdvIGRheXMgdXBvbiBhIHN0cm9rZQogIC0gNSBoZWFsdGh5IHN1YmplY3QgKGdyb2VwPTIpLgoKLSBJcyBjaG9sZXN0ZXJvbCBjb25jZW50cmF0aW9uIG9mIGhhcnQgcGF0aWVudHMgYW5kIGhlYWx0aHkgc3ViamVjdHMgb24gYXZlcmFnZSBkaWZmZXJlbnQ/CgpgYGB7cn0KY2hvbCA8LSByZWFkX3RzdigiaHR0cHM6Ly9yYXcuZ2l0aHVidXNlcmNvbnRlbnQuY29tL0dUUEIvUFNMUzIwL21hc3Rlci9kYXRhL2Nob2wudHh0IikKY2hvbCRncm91cCA8LSBhcy5mYWN0b3IoY2hvbCRncm91cCkKbkdyb3VwcyA8LSB0YWJsZShjaG9sJGdyb3VwKQpuIDwtIHN1bShuR3JvdXBzKQpjaG9sCmBgYAoKLS0tCgoKYGBge3IsIGVjaG89RkFMU0UsIGZpZy5hbGlnbj0nY2VudGVyJ30KY2hvbCAlPiUgZ2dwbG90KGFlcyh4ID0gZ3JvdXAsIHkgPSBjaG9sZXN0KSkgKwogIGdlb21fYm94cGxvdChvdXRsaWVyLnNoYXBlID0gTkEpICsKICBnZW9tX3BvaW50KHBvc2l0aW9uID0gImppdHRlciIpCgpjaG9sICU+JSBnZ3Bsb3QoYWVzKHNhbXBsZSA9IGNob2xlc3QpKSArCiAgZ2VvbV9xcSgpICsKICBnZW9tX3FxX2xpbmUoKSArCiAgZmFjZXRfd3JhcCh+Z3JvdXApCmBgYAoKLSBQb3NzaWJseSBvdXRsaWVycwotIERpZmZpY3VsdCB0byBhc3Nlc3MgZGlzdHJpYnV0aW9uYWwgYXNzdW1wdGlvbnMgd2hlbiBvbmx5IDUgb2JzZXJ2YXRpb25zIGFyZSBhdmFpbGFibGUuCgoKIyBSYW5rIFRlc3RzCgotIEltcG9ydGFudCBncm91cCBvZiBub24tcGFyYW1ldHJpYyB0ZXN0CiAgLSBOb24tcGFyYW1ldHJpYywKICAtIEV4YWN0ICRwJC12YWx1ZXMgdXNpbmcgYSBwZXJtdXRhdGlvbiBudWxsIGRpc3RyaWJ1dGlvbi4KICAtIE5vIG5lZWQgZm9yIHNlcGFyYXRlIHBlcm11dGF0aW9uIGRpc3RyaWJ1dGlvbiBmb3IgZWFjaCBuZXcgZGF0YXNldC4KICAtIFBlcm11dGF0aW9uIG51bGwgZGlzdHJpYnV0aW9uIG9mIHJhbmsgdGVzdHMgb25seSBkZXBlbmRzIG9uIHNhbXBsZSBzaXplCiAgLSBSb2J1c3QgdG8gb3V0bGllcnMKCi0tLQoKIyBSYW5rcwoKUmFuayB0ZXN0cyBzdGFydCBmcm9tIHJhbmstdHJhbnNmb3JtZWQgZGF0YS4KCi0gTGV0ICRZXzEsIFxsZG90cywgWV9uJC4KLSBJbiB0aGUgYWJzZW5jZSBvZiAqdGllcyoKICAkJFJfaT1SKFlfaSkgPSBcI1x7WV9qOiBZX2pcbGVxIFlfaTsgaj0xLFxsZG90cywgblx9JCQKLSBTbWFsbGVzdCBvYnNlcnZhdGlvbiBoYXMgcmFuayAxLCBzZWNvbmQgc21hbGxlc3QgcmFuayAyLCAuLi4gLCBsYXJnZXN0IG9ic2VydmF0aW9uIGdldHMgcmFuayAkbiQKCmBgYHtyfQpjaG9sJGNob2xlc3QKcmFuayhjaG9sJGNob2xlc3QpCmBgYAoKLS0tCgojIyBUaWVzCgpTb21ldGltZXMgKnRpZXMqIG9jY3VyOiB0d28gb2JzZXJ2YXRpb25zIHdpdGggaWRlbnRpY2FsIHZhbHVlcwoKYGBge3J9CndpdGhUaWVzIDwtIGMoNDAzLCA1MDcsIDUwNywgNjEwLCA2NTEsIDY1MSwgNjUxLCA4MzAsIDkwMCkKcmFuayh3aXRoVGllcykKYGBgCgotIFRpZXM6IDUwNyBvY2N1cnMgdHdpY2UsIDY1MSBvY2N1cnMgMyB0aW1lcwotIElmIHRpZXMgb2NjdXIgKm1pZHJhbmtzKiBhcmUgdXNlZC4KCi0gKiptaWRyYW5rKiogb2Ygb2JzZXJ2YXRpb24gJFlfaSQgYmVjb21lcwogIFxiZWdpbntlcW5hcnJheSp9CiAgIFJfaSAmPSYgXGZyYWN7IFwjXHtZX2o6IFlfalxsZXEgWV9pXH0gKyAoIFwjXHtZX2o6IFlfaiA8IFlfaVx9ICsxKX17Mn0uCiAgIFxlbmR7ZXFuYXJyYXkqfQoKLS0tCgojIyBSYW5rcyBvZiBwb29sZWQgc2FtcGxlCgotIExldCAkWV97aWp9JCwgJGk9MSxcbGRvdHMsIG5faiQgYmUgb2JzZXJ2YXRpb25zIGZyb20gdHdvIHRyZWF0bWVudCBncm91cHMgJGo9MSwyJC4KLSBUaGV5IGNhbiBhbHNvIGJlIHJlcHJlc2VudGVkIGJ5ICRaXzEsXGxkb3RzLCBaX24kICgkbj1uXzErbl8yJCksIHRoZSBvdXRjb21lcyBvZiB0aGUgcG9vbGVkIHNhbXBsZQoKYGBge3J9CnQoY2hvbCkKeiA8LSBjaG9sJGNob2xlc3QKegpyYW5rKHopCmBgYAotLS0KCiMgV2lsY294b24tTWFubi1XaGl0bmV5IFRlc3QKCiBTaW11bHRhbmVvdXNseSBkZXZlbG9wZWQgYnkgV2lsY294b24sIGFuZCwgIE1hbm4gYW5kIFdoaXRuZXk6ICAqKldpbGNveG9uLU1hbm4tV2hpdG5leSoqLCAqKldpbGNveG9uIHJhbmsgc3VtIHRlc3QqKiAgb3IgKipNYW5uLVdoaXRuZXkgVSB0ZXN0KioKCiMjIEh5cG90aGVzZXMKClVuZGVyICRIXzAkIHRoZSBkaXN0cmlidXRpb25zIG9mIHRoZSB0d28gZ3JvdXBzIGFyZSBlcXVhbAokJEhfMDogZl8xPWZfMiQkCgoKVW5kZXIgdGhlIGFsdGVybmF0aXZlICRIXzEkIHRoZSBkaXN0cmlidXRpb25zIGRpZmZlciBpbiBsb2NhdGlvbiAkJEhfMTogXG11XzFcbmVxIFxtdV8yJCQKCiRIXzEkIGFzc3VtZXMgKipsb2NhdGlvbi1zaGlmdCoqLCB3ZSB3aWxsIHJlbGF4IHRoaXMgYXNzdW1wdGlvbiBsYXRlciBvbi4KCiMjIFRlc3Qgc3RhdGlzdGljCgpDbGFzc2ljIFQtdGVzdDogZGlmZmVyZW5jZSBpbiBzYW1wbGUgbWVhbnMgJFxiYXJ7WX1fMS1cYmFye1l9XzIkLgoKSGVyZTogRGlmZmVyZW5jZSBpbiBzYW1wbGUgbWVhbnMgYmFzZWQgb24gcmFuayB0cmFuc2Zvcm1lZCBkYXRhCgpSYW5rcyBiYXNlZCBvbiB0aGUgcG9vbGVkIHNhbXBsZSAodXBvbiBqb2luaW5nIHRoZSBvYnNlcnZhdGlvbnMgZnJvbSB0aGUgdHdvIGdyb3Vwcyk6ICRSX3tpan09UihZX3tpan0pJCBpcyBkZSByYW5rIG9mIG9ic2VydmF0aW9uICRZX3tpan0kIGluIHRoZSBwb29sZWQgc2FtcGxlLgoKXFsKICBUID0gXGZyYWN7MX17bl8xfVxzdW1fe2k9MX1ee25fMX0gUihZX3tpMX0pIC0gXGZyYWN7MX17bl8yfVxzdW1fe2k9MX1ee25fMn0gUihZX3tpMn0pIC4KXF0KCi0gVW5kZXIgJEhfMCQgd2UgZXhwZWN0IHRoZSBhdmVyYWdlIHJhbmsgb2YgdGhlIGZpcnN0IGdyb3VwIHRvIGJlIGNsb3NlIHRvIHRoYXQgb2YgdGhlIHNlY29uZCBncm91cCBzbyAkVCQgaXMgY2xvc2UgdG8gemVyby4KCi0gVW5kZXIgJEhfMSQgd2UgZXhwZWN0IHRoZSBtZWFuIHJhbmtzIHRvIGRpZmZlciBzbyB0aGF0ICRUJCBkZXZpYXRlcyBmcm9tIHplcm8uCgotIEl0IGlzIHN1ZmZpY2llbnQgdG8gb25seSBjYWxjdWxhdGUKICAkJFNfMT1cc3VtX3tpPTF9XntuXzF9IFIoWV97aTF9KSQkLgoKLSAkU18xJCBpcyB0aGUgc3VtIG9mIHRoZSByYW5rcyBvZiB0aGUgZmlyc3QgZ3JvdXA6ICpyYW5rIHN1bSB0ZXN0Ki4KCi0gVGhpcyBob2xkcyBiZWNhdXNlClxbCiAgU18xK1NfMiA9IFx0ZXh0e3N1bSBvZiBhbGwgcmFua3N9ID0gMSsyK1xjZG90cyArIG49XGZyYWN7MX17Mn1uKG4rMSkuClxdCgoKLSAkU18xJCAob3IgJFNfMiQpIGlzIGEgZ29vZCB0ZXN0IHN0YXRpc3RpYwoKLSBVc2UgcGVybXV0YXRpb25zIHRvIGRldGVybWluZSB0aGUgZXhhY3QgcGVybXV0YXRpb24gZGlzdHJpYnV0aW9uLiAoUGVybXV0ZSB0aGUgcmFua3MgYmV0d2VlbiB0aGUgZ3JvdXBzKQoKLSBGb3IgYSBnaXZlbiAkbiQgYW5kIG5vICp0aWVzKiB0aGUgcmFuayB0cmFuc2Zvcm1lZCBkYXRhIGlzIGFsd2F5cwogICQkMSwgMiwgXGxkb3RzLCBuJCQKLSBGb3IgZ2l2ZW4gJG5fMSQgZW4gJG5fMiQgdGhlIHBlcm11dGF0aW9uIGRpc3RyaWJ1dGlvbiBpcyBhbHdheXMgdGhlIHNhbWUhCi0gV2l0aCBjdXJyZW50IGNvbXB1dGluZyBwb3dlciB0aGlzIGlzIG5vdCBzbyBpbXBvcnRhbnQgYW55IG1vcmUuCgotLS0KCiMjIFN0YW5kYXJkaXplZCBzdGF0aXN0aWMKCk9mdGVuIHRoZSBzdGFuZGFyZGl6ZWQgdGVzdCBzdGF0aXN0aWMgaXMgdXNlZApcWwogIFQgPSBcZnJhY3tTXzEtXHRleHR7RX1fezB9XGxlZnRbU18xXHJpZ2h0XX17XHNxcnR7XHRleHR7VmFyfV97MH1cbGVmdFtTXzFccmlnaHRdfX0sClxdCgotIHdpdGggJFx0ZXh0e0V9X3swfVxsZWZ0W1NfMVxyaWdodF0kIGFuZCAkXHRleHR7VmFyfV97MH1cbGVmdFtTXzFccmlnaHRdJCB0aGUgZXhwZWN0IG1lYW4gYW5kIHZhcmlhbmNlIG9mIFMxIHVuZGVyICRIXzAkLgoKLSBVbmRlciAkSF8wJAogXFsKICAgXHRleHR7RX1fezB9XGxlZnRbU18xXHJpZ2h0XT0gXGZyYWN7MX17Mn1uXzEobisxKSBcO1w7XDtcO1x0ZXh0eyBlbiB9XDtcO1w7XDsgXHRleHR7VmFyfV97MH1cbGVmdFtTXzFccmlnaHRdPVxmcmFjezF9ezEyfW5fMW5fMihuKzEpLgogXF0KCi0gVW5kZXIgJEhfMCQgYW5kIHdoZW4gJFxtaW4obl8xLG5fMilccmlnaHRhcnJvdyBcaW5mdHkkCiBcWwogICAgVCA9IFxmcmFje1NfMS1cdGV4dHtFfV97MH1cbGVmdFtTXzFccmlnaHRdfXtcc3FydHtcdGV4dHtWYXJ9X3swfVxsZWZ0W1NfMVxyaWdodF19fSBccmlnaHRhcnJvdyBOKDAsMSkuCiBcXQoKQXN5bXB0b3RpY2FsbHkgdGhlIHN0YW5kYXJkaXNlZCBzdGF0aXN0aWMgZm9sbG93cyBhIHN0YW5kYXJkIG5vcm1hbCBkaXN0cmlidXRpb24hCgotLS0KCiMjIENob2xlc3Rlcm9sIGV4YW1wbGUKCldlIGlsbHVzdHJhdGUgdGhlIHJlc3VsdCBmb3IgdGhlIGNob2xlc3Rlcm9sIGV4YW1wbGUgdXNpbmcgdGhlIFIgZnVuY3Rpb24gYHdpbGNveC50ZXN0YC4KYGBge3J9CndpbGNveC50ZXN0KGNob2xlc3QgfiBncm91cCwgZGF0YSA9IGNob2wpCmBgYAoKLSBXZSByZWplY3QgJEhfMCQgKCRwPSQgYHIgZm9ybWF0KHdpbGNveC50ZXN0KGNob2xlc3R+Z3JvdXAsZGF0YT1jaG9sKSRwLnZhbHVlLGRpZ2l0cz0yKWAgJDwwLjA1JCkKCi0gVGhlIG91dHB1dCBzaG93cyAkVz0kIGByIHdpbGNveC50ZXN0KGNob2xlc3R+Z3JvdXAsZGF0YT1jaG9sKSRzdGF0aXN0aWNgPwoKLSBMZXRzIGNhbGN1bGF0ZQpgYGB7cn0KUzEgPC0gc3VtKHJhbmsoY2hvbCRjaG9sZXN0KVtjaG9sJGdyb3VwID09IDFdKQpTMQpTMiA8LSBzdW0ocmFuayhjaG9sJGNob2xlc3QpW2Nob2wkZ3JvdXAgPT0gMl0pClMyCmBgYAoKLSBXaGVyZSBkb2VzICRXPSQgYHIgd2lsY294LnRlc3QoY2hvbGVzdH5ncm91cCxkYXRhPWNob2wpJHN0YXRpc3RpY2AgY29tZXMgZnJvbT8KCi0tLQoKIyMgTWFubiBhbmQgV2hpdG5leSB0ZXN0CgpNYW5uIGFuZCBXaGl0bmV5IHRlc3QgaW4gYWJzZW5jZSBvZiB0aWVzOgpcWwogVV8xID0gXHN1bV97aT0xfV57bl8xfVxzdW1fe2s9MX1ee25fMn0gXHRleHR7SX1cbGVmdFx7WV97aTF9XGdlcSBZX3trMn1ccmlnaHRcfS4KXF0KCi0gd2l0aCAkXHRleHR7SX1cbGVmdFx7LlxyaWdodFx9JCBhbiBpbmRpY2F0b3IgdGhhdCBlcXVhbHMgMSAgaWYgdGhlIGV4cHJlc3Npb24gaXMgdHJ1ZSBhbmQgaXMgemVybyBvdGhlcndpc2UuCgotIFUgY291bnRzIGhvdyBtYW55IHRpbWVzIGFuIG9ic2VydmF0aW9uIG9mIHRoZSBmaXJzdCBncm91cCBpcyBsYXJnZXIgb3IgZXF1YWwgdG8gYW4gb2JzZXJ2YXRpb24gZnJvbSB0aGUgc2Vjb25kIGdyb3VwLgoKYGBge3J9CnkxIDwtIHN1YnNldChjaG9sLCBncm91cCA9PSAxKSRjaG9sZXN0CnkyIDwtIHN1YnNldChjaG9sLCBncm91cCA9PSAyKSRjaG9sZXN0CnUxSGxwIDwtIHNhcHBseSh5MSwgZnVuY3Rpb24oeTFpLCB5MikgewogIHkxaSA+PSB5Mgp9LCB5MiA9IHkyKQpjb2xuYW1lcyh1MUhscCkgPC0geTEKcm93bmFtZXModTFIbHApIDwtIHkyCmBgYAoKYGBge3J9CnUxSGxwClUxIDwtIHN1bSh1MUhscCkKVTEKYGBgCgpJdCBjYW4gYmUgc2hvd24gdGhhdCAkVV8xID0gU18xIC0gXGZyYWN7MX17Mn1uXzEobl8xKzEpLiQKCmBgYHtyfQpTMSAtIG5Hcm91cHNbMV0gKiAobkdyb3Vwc1sxXSArIDEpIC8gMgpgYGAKCjEuICRVXzEkIGVuICRTXzEkIGNvbnRhaW4gdGhlIHNhbWUgaW5mb3JtYXRpb24KMi4gJFVfMSQgaXMgYWxzbyBhIHJhbmsgc3RhdGlzdGljLCBhbmQKMy4gRXhhY3QgdGVzdCBiYXNlZCBvbiAkVV8xJCBhbmQgJFNfMSQgYXJlIGVxdWl2YWxlbnQuCgotLS0KCiMjIFByb2JhYmlsaXN0aWMgaW5kZXgKCi0gJFVfMSQgaGFzIGEgYmV0dGVyIGludGVycHJldGF0aW9uIGZlYXR1cmUKLSBMZXQgJFlfaiQgYSByYW5kb20gb2JzZXJ2YXRpb24gZnJvbSBncm91cCAkaiQgKCRqPTEsMiQpLiBUaGVuClxiZWdpbntlcW5hcnJheSp9CiAgXGZyYWN7MX17bl8xbl8yfVx0ZXh0e0V9XGxlZnRbVV8xXHJpZ2h0XQogICAgICY9JiBcdGV4dHtQfVxsZWZ0W1lfMSBcZ2VxIFlfMlxyaWdodF0uClxlbmR7ZXFuYXJyYXkqfQoKU28gd2UgY2FuIGVzdGltYXRlIHRoZSBwcm9iYWJpbGl0eSBieSBjYWxjdWxhdGluZyB0aGUgbWVhbiBvZiBhbGwgaW5kaWNhdG9yIHZhcmlhYmxlIHZhbHVlcyAkXHRleHR7SX1cbGVmdFx7WV97aTF9XGdlcSBZX3trMn1ccmlnaHRcfSQuIE5vdGUsIHRoYXQgd2UgZGlkICRuXzEgXHRpbWVzIG5fMiQgY29tcGFyaXNvbnMKCmBgYHtyfQptZWFuKHUxSGxwKQpVMSAvIChuR3JvdXBzWzFdICogbkdyb3Vwc1syXSkKYGBgCgotIFByb2JhYmlsaXR5ICRcdGV4dHtQfVxsZWZ0W1lfMSBcZ2VxIFlfMlxyaWdodF0kIGlzIHJlZmVycmVkIHRvIGFzIHRoZSAqcHJvYmFiaWxpc3RpYyBpbmRleCouCi0gSXQgaXMgdGhlIHByb2JhYmlsaXR5IHRoYXQgYSByYW5kb20gb2JzZXJ2YXRpb24gb2YgdGhlIGZpcnN0IGdyb3VwIGlzIGxhcmdlciBvciBlcXVhbCB0aGFuIGEgcmFuZG9tIG9ic2VydmF0aW9uIG9mIHRoZSBzZWNvbmQgZ3JvdXAKLSBJZiAkSF8wJCBob2xkcyAkXHRleHR7UH1cbGVmdFtZXzEgXGdlcSBZXzJccmlnaHRdPVxmcmFjezF9ezJ9JC4KCi0gUiBmdW5jdGlvbiBgd2lsY294LnRlc3RgIGRvZXMgbm90IHJldHVybiB0aGUgV2lsY294b24gcmFuayBzdW0gc3RhdGlzdGljLiBJdCByZXR1cm5zIHRoZSBNYW5uLVdoaXRuZXkgc3RhdGlzdGljICRVXzEkLgotIExldHMgcmV2aXNpdCB0aGUgcmVzdWx0CmBgYHtyfQp3VGVzdCA8LSB3aWxjb3gudGVzdChjaG9sZXN0IH4gZ3JvdXAsIGRhdGEgPSBjaG9sKQp3VGVzdApVMQpwcm9iSW5kIDwtIHdUZXN0JHN0YXRpc3RpYyAvIHByb2Qobkdyb3VwcykKcHJvYkluZApgYGAKCkJlY2F1c2UgJHA9JCBgciBmb3JtYXQod1Rlc3QkcC52YWx1ZSxkaWdpdHM9MylgICQ8MC4wNSQgd2UgY29uY2x1ZGUgYXQgdGhlICQ1XCUkIHNpZ25pZmljYW5jZSBsZXZlbCB0aGF0IHRoZSBtZWFuIGNob2xlc3Rlcm9sIGxldmVsIG9mIGhhcnQgcGF0aWVudHMgaXMgbGFyZ2VyIHRoZW4gdGhhdCBvZiBoZWFsdGh5IHN1YmplY3RzLgoKICAtIE5vdGUgdGhhdCB3ZSBoYXZlIGFzc3VtZWQgdGhhdCB0aGUgbG9jYXRpb24tc2hpZnQgbW9kZWwgaXMgdmFsaWQgaW4gdGhpcyBjb25jbHVzaW9uLgogIC0gV2UgYWxzbyBrbm93IHRoYXQgaGlnaGVyIGNob2xlc3Rlcm9sIGxldmVsIGFyZSBtb3JlIGxpa2VseSBmb3IgaGFydCBwYXRpZW50cyB0aGVuIGZvciBoZWFsdGh5IHN1YmplY3RzIGFuZCB0aGlzIHByb2JhYmlsaXR5IGlzCiRVMS8obl8xXHRpbWVzIG5fMik9JCBgciBwcm9iSW5kKjEwMGAlLgogIC0gV2Ugc2hvdWxkIGFzc2VzcyB0aGUgbG9jYXRpb24gc2hpZnQgYXNzdW1wdGlvbi4gQnV0IHRoaXMgaXMgbm90IHBvc3NpYmxlIHdpdGggb25seSA1IG9ic2VydmF0aW9ucy4KCldpdGhvdXQgdGhlIGxvY2F0aW9uLXNoaWZ0IGFzc3VtcHRpb24gdGhlIGNvbmNsdXNpb24gaW4gdGVybXMgb2YgdGhlIHByb2JhYmlsaXN0aWMgaW5kZXggcmVtYWlucyB2YWxpZCEKCiAgLSBTbyB3aGVuIHdlIGRvIG5vdCBhc3N1bWUgbG9jYXRpb24gc2hpZnQgd2UgdGVzdCBmb3IKClxbSF8wOiBGXzE9Rl8yIFx0ZXh0eyB2cyB9IEhfMTogUFtZXzEgXGdlcSBZXzJdIFxuZXEgMC41LlxdCgoKIyMgQ29uY2x1c2lvbgoKVGhlcmUgaXMgYSBzaWduaWZpY2FudCBkaWZmZXJlbmNlIGluIHRoZSBkaXN0cmlidXRpb24gb2YgdGhlIGNob2xlc3Rlcm9sIGNvbmNlbnRyYXRpb24gb2YgaGFydCBwYXRpZW50cyB0d28gZGF5cyB1cG9uIGEgc3Ryb2tlIGFuZCB0aGF0IG9mIGhlYWx0aHkgc3ViamVjdCAoJHA9JCBgciBmb3JtYXQod1Rlc3QkcC52YWx1ZSxkaWdpdHM9MylgKS4gSXQgaXMgbW9yZSBsaWtlbHkgdG8gb2JzZXJ2ZSBoaWdoZXIgY2hvbGVzdGVyb2wgbGV2ZWxzIGZvciBoYXJ0IHBhdGllbnRzIHRoZW4gZm9yIGhlYWx0aHkgc3ViamVjdHMuIFRoZSBwb2ludCBlc3RpbWF0b3IgZm9yIHRoaXMgcHJvYmFiaWxpdHkgaXMgYHIgcHJvYkluZCoxMDBgJS4K