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?

$\endgroup$
  • $\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 Jul 9 '15 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 Jul 9 '15 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 Jul 9 '15 at 21:32
  • $\begingroup$ @Silverfish you are correct. I think the question was not posed appropriately. $\endgroup$ – AdamO Jul 9 '15 at 21:37
  • $\begingroup$ The code for integer works differently. The aroma would be 0,1,2 $\endgroup$ – Aksakal Jul 9 '15 at 22:04
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^*)$.

$\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).

$\endgroup$
  • $\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 Jul 10 '15 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 Jul 10 '15 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 Jul 10 '15 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 Jul 10 '15 at 14:59
  • $\begingroup$ Except in pathological cases where B=INT_MAX and A=INT_MIN, because N can't be calculated. $\endgroup$ – bishop Jul 10 '15 at 15:04

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.