Hi,in the correctness of Knuth Shuffle, you make use of “coupling” in probability, it’s in this link http://tsourakakis.wordpress.com/2010/04/05/generating-random-permutations/ ,I’m sorry that after searching for coupling in probability, little knowledge is got, I wonder would U please give a more detail explanation?
take two permutations: the first one is the identity, and the other one is a fictional permutation. The fictional permutation is a permutation taken uniformly at random.
what do you mean by that? Take two independent permutations or take them in a sequence? The fictional permutation means do not actually do it?
– in the first permutation, exchange I_k and k
– in the fictional permutation, exchange I_k and the number in position k
In the first one, Do you mean exchange l_k and k or the number in l_k and the number in position k? what’s more, exchange sth will be a contradiction to identity permutation?
Shuai Zhao said,
June 14, 2011 at 2:23 am
Hi,in the correctness of Knuth Shuffle, you make use of “coupling” in probability, it’s in this link
http://tsourakakis.wordpress.com/2010/04/05/generating-random-permutations/ ,I’m sorry that after searching for coupling in probability, little knowledge is got, I wonder would U please give a more detail explanation?
take two permutations: the first one is the identity, and the other one is a fictional permutation. The fictional permutation is a permutation taken uniformly at random.
what do you mean by that? Take two independent permutations or take them in a sequence? The fictional permutation means do not actually do it?
– in the first permutation, exchange I_k and k
– in the fictional permutation, exchange I_k and the number in position k
In the first one, Do you mean exchange l_k and k or the number in l_k and the number in position k? what’s more, exchange sth will be a contradiction to identity permutation?
I’m sorry for my excuse, many many thanks.