2
$\begingroup$

This question is inspired by two seemingly equivalent attempts to solve a question asked yesterday: In R, how to sample from the output of combn(a,b) if the "a choose b" is too large?

Essentially the problem is to choose $10$ integers that sum to $100$, where each number must be $\ge 0$.

The approach suggested in the original question is to sample $9$ numbers in the range $1$ to $109$, without replacement, and treat these as cut points cutting the range $0$ to $110$. The differences between cutpoints (including $0$ and $110$) give 10 numbers each of which is $\ge 1$. Finally, we subtract $1$ from each number to get $10$ numbers that are $\ge 0$ and add up to $100$.

An equivalent -- and simpler -- approach, I thought, would be to sample $9$ numbers in the range $0$ to $100$, with replacement. The differences between cutpoints (including $0$ and $100$) directly give 10 numbers that are $\ge 0$ and add up to $100$.

Implementing these approaches in R shows, however, that the approaches are not equivalent.

  • y is the first approach, sampling $9$ numbers from $1\ldots109$ without replacement and adjusting.
  • x is the second approach, sampling $9$ numbers from $0\ldots100$ with replacement.

From the histograms below, it is apparent that $0$ is sampled a lot more often in the first compared to the second approach.

enter image description here

Assuming there isn't simply a bug in my second approach, my questions are:

  • Why the difference when it seems like intuitively the two approaches should be equivalent?
  • Which approach is correct?

R code below for reference

set.seed(99)

N=1e5
y <- sapply( 1:N, function(i) {
    diff( c(0, 
            sort(sample(1:109, 9)),
            110) ) - 1
} )

x <- sapply( 1:N, function(i) {
    diff( c(0,
            sort(sample(0:100, 9, replace=TRUE)),
            100) )
} )

p1 <- hist(y, breaks=-0.5:100.5)
p2 <- hist(x, breaks=-0.5:100.5)
par(mfrow=c(3,1))
plot(p1, col=rgb(0,0,1))
plot(p2, col=rgb(1,1,0, 0.75))
# http://stackoverflow.com/questions/3541713/how-to-plot-two-histograms-together-in-r
plot(p1, col=rgb(0,0,1), main="x superimposed on y")
plot(p2, col=rgb(1,1,0, 0.75), add=T)
$\endgroup$
  • 1
    $\begingroup$ Why don't you work out the exact solution for the simplest case where the two algorithms differ--finding three nonnegative integers summing to $2$? You can easily enumerate all possibilities (six with the first algorithm and nine with the second). The correct result, given by the first algorithm, is that the expected numbers of $0$, $1$, and $2$'s are $9/18$, $6/18$, and $3/18$ respectively, whereas the second algorithm gives $13/27$, $10/27$, and $4/27$ respectively. $\endgroup$ – whuber Aug 15 '13 at 22:31
  • $\begingroup$ @whuber's point there is so often the right approach - find the simplest possible case where the problem occurs, whereupon both the differences and the problems in reasoning are usually more obvious. $\endgroup$ – Glen_b -Reinstate Monica Aug 16 '13 at 0:59
-1
$\begingroup$

Let's say you have 3 numbers. Without corner cases probability, that you have 0 in the sum is 1/100 in 2nd approach and 2/109 in the 1st approach (numbers are wrong, but I think idea is ok). 1st sounds more reasonable.

$\endgroup$
  • 2
    $\begingroup$ If the numbers are wrong, how can the idea be correct? $\endgroup$ – whuber Aug 15 '13 at 22:31

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.