21
$\begingroup$

Does this discrete distribution have a name? For $i \in 1...N$

$f(i) = \frac{1}{N} \sum_{j = i}^N \frac{1}{j}$

I came across this distribution from the following: I have a list of $N$ items ranked by some utility function. I want to randomly select one of the items, biasing toward the start of the list. So, I first choose an index $j$ between 1 and $N$ uniformly. I then select an item between indices 1 and $j$. I believe this process results in the above distribution.

$\endgroup$
  • 2
    $\begingroup$ This is not a distribution: it is not normalized. $\endgroup$ – whuber May 18 '15 at 2:31
  • $\begingroup$ @whuber I thought so at first (and commented before I realized that I had misunderstood and removed the comment), but it turned out I misunderstood the definition. Unless I have a further misunderstanding, it is a normalized probability mass function. $\endgroup$ – Glen_b May 18 '15 at 2:52
  • 4
    $\begingroup$ It is normalized. 1/1 will appear in the sum exactly once (it will be in f(1)). 1/2 will appear exactly twice (it will be in f(1) and f(2)). etc. So the sum of all those sums will be N and the normalizing constant is shown as 1/N. checks out. $\endgroup$ – rcorty May 18 '15 at 3:03
  • 1
    $\begingroup$ More to the point, though, I don't know what this distro is called. I also don't know how the process you described leads to this distro. One thought I had is that it sounds like a discrete version of a stick-breaking process, which is very googlable. $\endgroup$ – rcorty May 18 '15 at 3:04
  • $\begingroup$ @Glen_b Thanks. I was reading this on my phone, which did not render $f$ clearly enough. $\endgroup$ – whuber May 18 '15 at 13:33
30
$\begingroup$

You have a discretized version of the negative log distribution, that is, the distribution whose support is $[0, 1]$ and whose pdf is $f(t) = - \log t$.

To see this, I'm going to redefine your random variable to take values in the set $\{ 0, 1/N, 2/N, \ldots, 1 \}$ instead of $\{0, 1, 2, \ldots, N \}$ and call the resulting distribution $T$. Then, my claim is that

$$ Pr\left( T = \frac{t}{N} \right) \rightarrow - \frac{1}{N} \log \left( \frac{t}{N} \right) $$

as $N, t \rightarrow \infty$ while $\frac{t}{N}$ is held (approximately) constant.

First, a little simulation experiment demonstrating this convergence. Here's a small implementation of a sampler from your distribution:

t_sample <- function(N, size) {
  bounds <- sample(1:N, size=size, replace=TRUE)
  samples <- sapply(bounds, function(t) {sample(1:t, size=1)})
  samples / N
}

Here's a histogram of a large sample taken from your distribution:

ss <- t_sample(100, 200000)
hist(ss, freq=FALSE, breaks=50)

enter image description here

and here's the logarithmic pdf overlaid:

linsp <- 1:100 / 100
lines(linsp, -log(linsp))

enter image description here

To see why this convergence occurs, start with your expression

$$ Pr \left( T = \frac{t}{N} \right) = \frac{1}{N} \sum_{j=t}^N \frac{1}{j} $$

and multiply and divide by $N$

$$ Pr \left( T = \frac{t}{N} \right) = \frac{1}{N} \sum_{j=t}^N \frac{N}{j} \frac{1}{N} $$

The summation is now a Riemann sum for the function $g(x) = \frac{1}{x}$, integrated from $\frac{t}{N}$ to $1$. That is, for large $N$,

$$ Pr \left( T = \frac{t}{N} \right) \approx \frac{1}{N} \int_{\frac{t}{N}}^1 \frac{1}{x} dx = - \frac{1}{N} \log \left( \frac{t}{N} \right)$$

which is the expression I wanted to arrive at.

$\endgroup$
  • $\begingroup$ You're extremely welcome. This was a great question and I had a lot of fun working it out. $\endgroup$ – Matthew Drury May 19 '15 at 17:30
6
$\begingroup$

This appears to be related to the Whitworth distribution. (I don't believe it is the Whitworth distribution, since if I remember right, that's the distribution of a set of ordered values, but it seems to be connected to it, and relies on the same summation-scheme.)

There's some discussion of the Whitworth (and numerous references) in

Anthony Lawrance and Robert Marks, (2008)
"Firm size distributions in an industry with constrained resources,"
Applied Economics, vol. 40, issue 12, pages 1595-1607

(There looks to be a working paper version here)

Also see

Nancy L Geller, (1979)
A test of significance for the Whitworth distribution,
Journal of the American Society for Information Science, Vol.30(4), pp.229-231

$\endgroup$
  • 2
    $\begingroup$ To make this answer self-contained, could you provide a definition of the Whitworth distribution and perhaps supply a few words of explanation concerning the connection you see? $\endgroup$ – whuber May 18 '15 at 13:35
  • $\begingroup$ @whuber Yes, it should be a comment as it stands. I'll edit some details in but it's going to end up a good deal longer. $\endgroup$ – Glen_b May 19 '15 at 0:31
  • $\begingroup$ Just some kind of definition would be fine. $\endgroup$ – whuber May 19 '15 at 0:44
  • $\begingroup$ Thanks, that was understood, but nevertheless that will be the outcome. $\endgroup$ – Glen_b May 19 '15 at 1:14

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.