2
$\begingroup$

I am reading about a method called consistent hash designed to distribute load among servers. The best case scenario would be a discrete uniform distribution where each server would get the same amount of requests.

In a specific implementation I am considering using there is a table of describing the chi squared and p-values test results:

enter image description here

I am having difficulties understanding how to interpret the results: From what I understand a Chi square test tests a null hypothesis and that the p value is the probability that we would accept the null hypothesis even if it is wrong.

What I don't understand is how to interpret a row in the results table. How do I associate the chi-squared test results and the value in the p-value[0.05/0.01] values to the probability that the distribution is not uniform ?

| cite | improve this question | |
$\endgroup$
1
$\begingroup$

They're showing that the distribution of load is statistically indistinguishable from the uniform distribution, by (I'm guessing) partitioning the servers into 2 through 18 sets and conducting a chi-squared goodness of fit test, comparing the observed requests for each bucket with expected requests.

$\chi^2$ goodness of fit test

A $ \chi^2$ test comes up anytime you have a test-statistic that follows the $\chi^2$ distribution, i.e. the statistic is the sum of squared standard normal random variables.

One classic such situation is the chi-squared goodness of fit test of whether an observed sample came from a particular distribution.

  • Let $X$ be some random variable.
  • Let's partition the range of $X$ into $r$ buckets. (This partition is arguably somewhat arbitrary.)

If we assume that $X$ follows some distribution for our null hypothesis, we can calculate the probability $p_i$ that $X$ falls into bucket $i$ for each bucket. If we have $n$ observations, we'll expect $np_i$ entries in bucket $i$ under the null hypothesis. Let $v_i$ be the actual number of observations in bucket $i$.

As Dmitry Panchenko's lecture notes show here, the following test statistic converges to the chi-squared distribution with $r-1$ degrees of freedom.

$$ \sum_{i=1}^r \frac{\left(v_i - np_i \right)^2}{np_i} \rightarrow \chi^2_{r-1} $$

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

The table reports the chi-square statistic from the test. The values under "p-value = 0.05" are the chi-square value you would need to get to get a p-value of 0.05. So, for two buckets you would need a chi-square value of at least 3.84 to get a significant result, and they got a chi-square value of only 0.5. So obviously, the p-value is quite greater than 0.05 for this test.

We used to use tables of p-value thresholds like this before we all had computers that could tell us the precise p-value.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you. From your answer it seems that the test results show that even for 20 buckets it doesn't seem that the distribution is uniform, right? $\endgroup$ – Belgi Nov 2 '18 at 16:37
  • 1
    $\begingroup$ I assume that the null hypothesis of the test is that the distribution is uniform. If so, the table would suggest that there is no good evidence that the distribution is not uniform. $\endgroup$ – Sal Mangiafico Nov 2 '18 at 16:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.