Consider an $m \times L$ matrix. Each row $i$ contains $n_i \ge 0$ elements in the first $n_i$ cells (the following $L - n_i$ cells are empty) such that $\sum_{i} n_i = n.$
Here is a procedure that selects an element from among all $n$ elements:
- Choose an integer $i$ uniformly at random from $[1,m]$.
- Choose another integer $k$ uniformly at random from $[1,L]$.
- If $k > n_i$, we reject $i$ and $k$ and repeat this procedure; otherwise we return the $k$-th elment in the $i$-th row.
My question is:
Does this procedure select an element uniformly at random from among all $n$ elements?
It does. Every element has the same chance of being selected. The fact that empty cells are sometimes selected in between doesn't create any asymmetry among the occupied cells.
It can be rather inefficient though (depending on the occupancy) if you need to do this many times. If you have enough memory, you could write the coordinates of the occupied cells into an $n$-element array, choose a single uniformly random integer from $[1,n]$ and perform a single table lookup.
Alternatively, if you don't have that much memory, you can compute and store the partial sums $\sum_{i=1}^kn_i$, choose a single uniformly random integer from $[1,n]$ and perform a binary search in the partial sums to find the corresponding element.