Random Sample from Power Law Distribution

Question

I have a huge data set that is probably hundreds of millions of rows. This data follows a very skewed power law distribution. Consider the X-axis to be products and the Y-axis to be revenue from products. Almost 95% of revenue would come from 1% of the products. The distribution looks like this:

I want to generate a random sample from this distribution which approximates the original distribution.

All this data is in a huge oracle DB. I see that Oracle SQL has DBMS_RANDOM.VALUE [link] which generates pseudo-random numbers.

These are my questions:

1. What should my sample size be in order to come close to the original data set. Consider original dataset to be 100million rows.
2. Doesn't pseudo-random number generators follow a gaussian distribution? If so, isn't it wrong use a random-number generator fit for gaussian distribution over a data which follows a power-law distribution?
3. How should I do random sampling over power law distributions? (this can be generalized to random sampling over any custom distribution).

Answer 1

What should my sample size be in order to come close to the original data set. Consider original dataset to be 100million rows.

1. I'm not sure what you're asking. Suppose your data are definitely follow a power-law, and you know its parameters precisely. Then a random sample of any size from a power-law distribution with that parameter is, by definition, a set of random draws from the distribution.

Doesn't pseudo-random number generators follow a gaussian distribution? If so, isn't it wrong use a random-number generator fit for gaussian distribution over a data which follows a power-law distribution?

2. No. You can make a PRNG for arbitrary distributions. Even if you don't have a prefab function for a particular distribution, there are many, many methods for generating exact and approximate deviates from arbitrary distributions.

How should I do random sampling over power law distributions? (this can be generalized to random sampling over any custom distribution).

3. I'd recommend starting with this article, "POWER-LAW DISTRIBUTIONS IN EMPIRICAL DATA," by Aaron Clauset, Cosma Shalizi and MEJ Newman. It describes testing for power law data and generating power law deviates in gruesome detail, including discrete and continuous power laws, and several other variations and alternative models which are power-law like.

Answer 2

This is an answer to the question 3: how to sample from a power-law distribution. The answer is based on the article pointed by @Sycorax: Power-Law Distributions in Empirical Data by Clauset et al. 2009. The article discusses synthetic random samples in Appendix D: Generating power-law distributed random numbers somewhere around page 38. I will write the math in Python-like pseudocode.

The appendix describes the use of the transformation method. The method is commonly used to generate samples from various distributions. Two things needed are a uniformly distributed random source r where 0 <= r < 1 and the functional inverse of the cumulative density function (CDF) of the power-law distribution. The source r is simply given as a parameter to the CDF.

Let us start from the probability density function p(x) of a continuous power-law distribution. Let x_min be the lower bound and alpha be the scaling parameter of the distribution. Syntax a**n denotes exponentiation a^n. The PDF can be given as:

p(x) = ((alpha - 1) / x_min) * (x / x_min) ** -alpha

The cumulative density function, CDF can be given as:

P(x) = (x / x_min) ** (-alpha + 1)

The inverse of CDF:

Pinv(x) = x_min * x ** (-1 / (alpha - 1))

Now, we are able to sample by applying x = 1 - r. Why not x = r? Appendix D shows that x = 1 - r is the correct one and more suitable for Pinv(x) because x cannot be zero: 0 < x <= 1.

Thus, to generate a power-law distributed sample x_smp in Python:

from random import random
x_min = 5
alpha = 2.5
r = random()
x_smp = x_min * (1 - r) ** (-1 / (alpha - 1))

For example, for r = 0.734113 the sampled value is x_smp = 12.092203.

To sample from discrete distribution the article proposes an approximation which uses the continuous method above but rounds the result to the nearest integer:

x_discrete = round(x_smp)

This approximation performs the better the larger is x_min. For distributions where x_min < 5 a more accurate but more complicated method should be used, as recommended in Appendix D.