How to generate values with the given property?

Question

I have to generate $N$ values, each of them is between 10000000 and 99999999 where $N<=90000000$. Let's denote the generated values by $(x_i)_{1 \leq i \leq N}$.

Consider the following pseudo-code:

var values = []
for (var i =0, i<N, i++)
    var generatedValue = 100000000 + i mod (N/10) 
    values.append(generatedValue)

Here, if $N=100$, in the list I will get a list of 100 values [100000000, 100000001, 100000002, 100000003, 100000004, 100000005, 100000006, 100000007, 100000008, 100000009, 100000000, 100000001, ....]. There are exactly 10 distinct values and there are exactly 10 terms of the sequence that have some given value $v$.

I want to change the pseudocode in a way that the values generated are random. Moreover, it's okay to have 8 generated values to be equal to $v_1$, 12 generated values to be equal to $v_2$, etc. Basically, if we denote by $X$ the set of distinct values, each set $\{x_i, x_i=v\}$ for each $v \in X$ contains on average 10 values but with a tolerance deviation of +-2.

How to do that?

Answer 1

TL;DR version: use your language's random number generator to select the correct number of distinct values you want, then sprinkle repetitions of them in some way.

---

At present, I don't think your problem is fully specified. I'll explain with some possible implementation strategies as examples; hopefully it will help you clarify what you really want.

Your language certainly has some method of generating random integers, so I'll use rand(n, a, b, replace) as shorthand for generating n integers uniformly distributed between a and b (inclusively) with a Boolean option for whether the numbers should be drawn with replacement.

Option 1: naïvely generate $N$ integers with replacement

By simply doing rand(N, 100000000, 999999999, replace = T), you'll get $N$ numbers in your desired range, but you probably won't have the overlap condition if you want. For instance, if $N = 100$, then you will very likely have $100$ distinct integers. On the other hand, if you draw lots of numbers, you'll start getting the overlap you want, but it will be very hard to control the amount of overlap; for instance, if you set $N = 89,999,999 \times 10 = 899,999,990$, then you will draw each number in the range an average of 10 times -- but some numbers will be drawn 15 times, some just 4 times, etc. Plus, this trick only works if you want an enormous list of numbers that is much bigger than the original range. This probably isn't what you want.

Option 2: pick your distinct values first, then resample from them

Let's use an example where you want just 20 distinct values, and each one should appear an average of 10 times (implying $N = 200$). You could choose to do something like this:

distinct_values := rand(20, 10000000, 99999999, replace = F)
my_values := distinct_values[rand(10*20, 0, 19, replace = T)]

The idea here is to make a vector of your distinct numbers first, then construct a subset of them by randomly choosing indices (with repetition). This gives you something closer to what you want: the number of repetitions of each number will be 10 on average. However, as before: sometimes it will be more than 12 or less than 8, which you've said was undesirable. Importantly, it's very possible (and not particularly challenging) to put probabilities on this; you can compute the exact probability of drawing each number between 8 and 12 times. This probability will change with $N$; the smaller $N$ is, the higher the probability of the repetitions being confined within $[8, 12]$ -- but it is never possible to guarantee that this will occur for any size $N$. However, it may be for your application that knowing something about the probabilities of this occurring will be sufficient.

Option 3: pick your distinct values first, then simply repeat each one ten times

You lose some of the randomness with this approach, but you get precisely what you want: a list of random numbers, each one appearing between 8 and 12 times (specifically, 10 times). You could randomize the overall order of the vector if that's important to do, of course.

Option 4: pick your distinct values first, then repeat each one a random number of times

Pseudocode:

distinct_values := rand(20, 100000000, 99999999, replace = F)
for(i = 0, i < 20, i++)
    my_values := append(my_values, repeat(distinct_values[i], rand(1, 8, 12, replace = *))
# note that replace is irrelevant when drawing 1 integer

The idea is: take your unique values, and glue them onto the end of a list a random number of times between 8 and 12. The catch is that you have now made the total number of items of your list a random variable. On average, it will be 20*10 = 200 (in this example), but it will usually not be exactly that and will typically bit a bit more or a bit less.

Option 5a: pick your distinct values first, then fill buckets randomly until full

Maybe it's important to have an exact number of values generated (again, $N = 200$ for the sake of illustration). Each one needs to be repeated at least 8 times, which specifies 80 of the numbers and leaves 120 of them to be determined (subject to the constraint that none should be repeated more than 12 times).

distinct_values := rand(20, 100000000, 99999999, replace = F)
reps := repeat(8, 20)    # vector indexed on 0:19 counting number of appearances
                         # each one starts with 8, and we'll draw the extras randomly

while(sum(reps) < 200)
    while(reps[i] < 12)
        i := random(1, 0, 19, replace = *)
    reps[i]++
    clear i

for(i = 0, i < 20, i++)
    my_values := append(my_values, repeat(distinct_values[i], reps[i]))

This is the closest solution yet to the problem you have described -- but it imposes certain statistical properties on which numbers will be repeated just 8 times and which will be repeated 12, for instance.

Option 5b: pick your distinct values first, then fill buckets proportionally to the number of possible remaining draws for each distinct value

This is a variation on the above theme; each of the 20 drawn numbers is repeated 8 times, and then it can be drawn up to an additional 4 times maximum. You could imagine the number of "extras" by starting with a $4 \times 20$ matrix of all zeroes, then populate 40 of the 80 entries (randomly) with ones and sum down along the columns. This will result in a row vector of length 20 with entries between 0 and 4 that you could use in place of reps above.

---

So, what's the difference between 5a and 5b? They both do basically what you want, but they very in the probabilities of seeing different things in reps. I'd have to think more about it, but I believe it to be the case that option 5b will produce more "extras" of 2 than option 5a will (meaning, numbers repeated an overall 10 times). There are many other ways you could fill the "extras" buckets while satisfying the constraints you laid out, and the main differences between them will be how many extras of each type show up. Since you haven't stated how you want those extras to show up, I think the problem isn't quite specified as stated. However, I think something like option 5b is probably pretty close to what you asked for.