1
$\begingroup$

Is it possible to map a uniform, discrete distribution over two integers $A$, $B$ (lower and upper bounds respectively) onto $[A^*, B^*]$ while keeping the distribution discrete uniform? We may assume $|A - B| > |A^* - B^*|$.

Based on my research, it seems like location and scale families do preserve the uniformity for continuous uniform distributions, but I can't understand how that would be true if I were to choose transformations with noncommon divisors like a uniform {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} distribution into a uniform {1, 2, 3, 4, 5, 6, 7} distribution. Is there a change of variable formula to obtain such a distribution?

Improve this question
$\endgroup$
10
  • $\begingroup$ Am I missing something? Simply do $z=a*(x-b)$, where $x$ is the original uniform and $z$ is the transformed one. That's exactly how uniform distribution functions work in statistics libraries, e.g. see this in Java docs.oracle.com/javase/7/docs/api/java/util/…. $\endgroup$
    – Aksakal
    Commented Jul 9, 2015 at 21:23
  • $\begingroup$ @Aksakal This is clearly true for the continuous uniform (rectangular) distribution; with a discrete distribution over the integers things are more complicated because e.g. a uniform over the integers {0,1,2} and a uniform over the integers {0,1,2,3,4} have a different number of atoms. I think the point here is that one can scale a distribution over the integers 0 to 4 to a distribution from 0 to 2, but the atoms would be at {0,0.5, 1, 1.5, 2} so no longer would it be uniform "over the integers". I think this is the point the OP is getting at. $\endgroup$
    – Silverfish
    Commented Jul 9, 2015 at 21:31
  • $\begingroup$ I think it would help in the original question if we could get some clarification on what you mean by "while keeping the distribution uniform", and in particular whether you require point probability masses over the integers? $\endgroup$
    – Silverfish
    Commented Jul 9, 2015 at 21:32
  • $\begingroup$ @Silverfish you are correct. I think the question was not posed appropriately. $\endgroup$
    – AdamO
    Commented Jul 9, 2015 at 21:37
  • $\begingroup$ The code for integer works differently. The aroma would be 0,1,2 $\endgroup$
    – Aksakal
    Commented Jul 9, 2015 at 22:04

2 Answers 2

Reset to default
1
$\begingroup$

Let $X_1, X_2, \ldots X_n \sim_{iid} DU(A, B)$ have the desired distribution. Let $Z_1, Z_2, \ldots Z_n \sim_{iid} U(0, 1)$ also independent of the $X$s. Then $\mathbf{L} = \mathbf{X} + \mathbf{Z} \sim_{iid} U(A, B+1)$. Since this is a location scale family, applying a linear transformation, we may obtain $\mathbf{L}^* \sim_{iid} U(A^*, B^*+1)$. Apply the integral binning operator:

$$\mbox{bin}(\cdot) = \cdot - \mbox{mod}(\cdot, 1)$$

to obtain $\mathbf{X}^* = \mbox{bin}(\mathbf{L}^*) \sim_{iid} DU(A^*, B^*)$.

Improve this answer
$\endgroup$
1
$\begingroup$

This code does precisely that.

The psudo random number generator in Java generates sequences of numbers from 0 to $2^{31}$ when you call Random.next(31). When you call Random.getInt(10), it will return uniform numbers between 0 and 10 using the randoms from Random.next(31).

Improve this answer
$\endgroup$
6
  • $\begingroup$ But this code has a further limitation: [0, 2^31) => [A, B), where A == 0 and B <= 2^31. I'm interested in a general method where neither A nor B are restricted. Eg, I also want to map [0, 2^31) => [-2^13, 242). $\endgroup$
    – bishop
    Commented Jul 10, 2015 at 14:16
  • $\begingroup$ There are many implementations of this function, look at `sample' in R, it can do any A and B $\endgroup$
    – Aksakal
    Commented Jul 10, 2015 at 14:25
  • $\begingroup$ But how? The obvious mapping formula is n' = a + n(b-a)/M, but that skews sampling at the upper end such that only n==M leads to b much less frequently than all the others. If we artificially increase the range to give b more of a chance with n' = a + n(b-a+1)/(M+1) we still have a problem: b-a overflows if b == INT_MAX and a == INT_MIN. The Java method is nice in that it doesn't play those games, but I'd like to see an implementation that preserves uniformity while avoiding an operation that could overflow the registers. $\endgroup$
    – bishop
    Commented Jul 10, 2015 at 14:54
  • $\begingroup$ @bishop When I just started programming, my naive implementation was to simply split the [0,1] interval into N=(B-A+1) bins numbered from 0 to N-1, call real uniform random number, then return A+interval#. It's not the most efficient way, but works like a charm. $\endgroup$
    – Aksakal
    Commented Jul 10, 2015 at 14:59
  • 1
    $\begingroup$ @bishop, the method that I described as naive is actually a version of so called "transformation method", see here. It is described in Knuth's TAOCP Vol.2, if I remember correctly. It's theoretically sound, the only thing's that it's not the fastest for the uniform distribution. $\endgroup$
    – Aksakal
    Commented Jul 10, 2015 at 15:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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