Evenly filling spaces for a specific average value

Question

Imagine I have $N$ spaces. Each space can be empty, or occupied. Given a fixed point value $x$ between zero and one, I would like to evenly populate the $N$ spaces such that $\frac{N_{\text{occupied}}}{N}$ is approximately equal to $x$. The purpose of the even distribution is such that the average rate of encountering occupied spaces when traversing the spaces follows $x$.

I understand that $\left \lfloor{N \cdot x}\right \rfloor$ will give me the number of spots to fill. But how do I algorithmically distribute them most evenly within the $N$ spaces? Is there any way to do this "cleanly"?

I've considered doing this with a boolean pseudorandom number generator with mean $x$, but I'm worried that wouldn't give optimal reliability and precision. Ideally the solution would not be very computationally intensive. Thank you so much.

Answer 1

Let $p$ be the proportion that you want filled, i.e., $p = \frac{N_{occupied}}N$. Leave the first space empty if $p<1$; otherwise, fill it.

Now let $f(k) = \lfloor pk \rfloor - \lfloor p(k-1) \rfloor$ and observe that if $k \in \mathbb Z$, then $f(k) \in \{0,1\}$. Use $f(k)$ as an indicator for filling the spaces for $k>1$; that is, fill the $k$th space if and and only if $f(k)=1$.

---

Example: say $p=0.71$ and $N=10$. Here's a table with columns $\left(k, pk, \lfloor pk \rfloor, f(k)\right)$. As you can see, a total of seven spaces are filled, and $\frac{7}{10} \approx 0.71$.

 1  0.71    0   0  
 2  1.42    1   1  
 3  2.13    2   1  
 4  2.84    2   0  
 5  3.55    3   1  
 6  4.26    4   1  
 7  4.97    4   0  
 8  5.68    5   1  
 9  6.39    6   1  
10  7.10    7   1  

Answer 2

Here is one way to do it. Generate the list of $N$ numbers $$\lfloor 0.5\rfloor, \lfloor x+0.5\rfloor, \lfloor 2x+0.5\rfloor,\dots,\lfloor (N-1)x+0.5\rfloor,$$ where $\lfloor\cdot\rfloor$ is the greatest integer function. Then “fill” box $k$ when $\lfloor kx+0.5\rfloor>\lfloor (k-1)x+0.5\rfloor$.

Note that this is equivalent to drawing the straight line from $(0,-0.5)$ to $(N-1,(N-1)x-0.5)$ on an integer grid and “filling” each column if the line passes through a horizontal grid line in this column. In the picture below, the line and it’s “floor” are drawn. You’d fill the boxes for the leftmost $x$-value of each segment of the floor function (orange), or boxes $2,5,9,12,15,19,22,25,29$, if $x=0.3$ and $N=30$.

This is like the “anti-aliasing” problem in computer graphics, where one needs to draw a slanted line using square pixels.