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


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.

  • $\begingroup$ Thank you for your answer. I see what you mean (kind of). Maybe you can comment on this: I did not mean that the "ordering" of the list changes -- of course it does. Imagine that you sort the list anyway after you did all changes. But would the sorted list then look (kind of) the same , i.e. have the same distribution of values, in the second scheme compared to the first one? $\endgroup$ – Felix Dombek Jan 31 '11 at 3:31
  • 1
    $\begingroup$ @Felix Dombek, the answer is "yes". In each of the three schemes, if you sorted each of the three vectors at the end, into ascending or descending order, then the resulting three vectors would all have the same joint distribution. These would be the order statistics of a multinomial random vector. But, the ordering at the end is important. Otherwise, each of the vectors have different distributions (though I think first and last would still be the same). $\endgroup$ – cardinal Jan 31 '11 at 3:57

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.