Picking random elements from a list – still random if they are reinserted at the end?

Question

Say I have a list with $n$ elements (say number $1$'s) and I want to do 1000 random changes to them, such as a $+1$. If I (1) picked a random element, (2) changed it, and then (3) did these two steps (1)+(2) another 999 times, this would probably be completely random, right?

Now, what if, whenever I change an element, I take it from the list and reinsert the changed element at the end of the list (i.e. this is the new step (2)) – would the changes also be completely random then?

I have the feeling that it might decrease the probability for already changed elements to get changed again, but can't quite put my finger on the cause. Also, consider this variant: instead of inserting them in the end, I insert them in a random new location after the change. How would that influence the probability for picking any element?

(PS. If someone knows good tags for this, please add them and delete this paragraph...)

Answer 1

It's necessary to be a little bit careful about what you mean by "random" and "completely random" here.

What you are describing, at least in your first scheme is a set of random draws such that the resulting vector is multinomially distributed with n = 1000 and probabilities $p_1 = p_2 = \cdots = p_n = 1/n$. Even in your first scheme, the resulting variables are not independent. Marginally, they do all have the same distribution and, intuitively (though I didn't check carefully), it seems that the vector of counts would have a property called exchangeability which, in some sense, is "almost independent and identically distributed".

In the second scheme, where you move each new selection to the end of the list after incrementing it, the reordered variables are not even exchangeable any more, nor do they have the same marginal distribution. Intuitively, this is because the ones being moved to the end of the list will tend to have larger values than ones at the beginning of the list. This is related to, but not quite, what are called order statistics.

I would have to think about the last scheme (i.e., reinserting in a random location) more carefully. On the surface, I believe you would essentially end up with the same distribution as in the first case. But, I've not checked that even remotely formally, so take that with a hefty dose of salt.