StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
primarykey
Id
12020883
data
AcceptedAnswerId
0
AnswerCount
0
ClosedDate
CommentCount
4
CommunityOwnedDate
CreationDate
2012-08-18T17:49:54
FavoriteCount
0
LastActivityDate
2012-08-18T17:49:54
LastEditDate
LastEditorUserId
0
OwnerUserId
764214
ParentId
11872190
PostTypeId
2
Score
8
ViewCount
0
LastEditorDisplayName
text
Body
The behaviour of the algorithm can be modelled as a <a href="http://en.wikipedia.org/wiki/Markov_chain" rel="noreferrer">Markov chain</a> over the <a href="http://en.wikipedia.org/wiki/Symmetric_group" rel="noreferrer">symmetric group</a> SN. <h1>Basics</h1> The N elements of the array <code>A</code> can be arranged in N! different permutations. Let us number these permutations from 1 to N!, e.g. by lexicographic ordering. So the state of the array <code>A</code> at any time in the algorithm can be fully characterized by the permutation number. For example, for N = 3, one possible numbering of all 3! = 6 permutations might be: <ol> <li>a b c</li> <li>a c b</li> <li>b a c</li> <li>b c a</li> <li>c a b</li> <li>c b a</li> </ol> <h1>State transition probabilities</h1> In each step of the algorithm, the state of <code>A</code> either stays the same or transitions from one of these permutations to another. We are now interested in the probabilities of these state changes. Let us call Pr(i → j) the probability that the state changes from permutation i to permutation j in a single loop iteration. As we pick m and n uniformly and independently from the range [0, N-1], there are N² possible outcomes, each of which is equally likely. <h2>Identity</h2> For N of these outcomes m = n holds, so there is no change in the permutation. Therefore, <blockquote> <img src="https://i.stack.imgur.com/4sFaR.png" alt="Pr(i→i)">. </blockquote> <h2>Transpositions</h2> The remaining N² - N cases are transpositions, i.e. two elements exchange their positions and therefore the permutation changes. Suppose one of these transpositions exchanges the elements at positions x and y. There are two cases how this transposition can be generated by the algorithm: either m = x, n = y or m = y, n = x. Thus, the probability for each transposition is 2 / N². How does this relate to our permutations? Let us call two permutations i and j neighbors if and only if there is a transposition which transforms i into j (and vice versa). We then can conclude: <blockquote> <img src="https://i.stack.imgur.com/3tdqo.png" alt="Pr(i→j)"> </blockquote> <h1>Transition matrix</h1> We can arrange the probabilities Pr(i → j) in a transition matrix P ∈ [0,1]N!×N!. We define <blockquote> pij = Pr(i → j), </blockquote> where pij is the entry in the i-th row and j-th column of P. Note that <blockquote> Pr(i → j) = Pr(j → i), </blockquote> which means P is symmetric. The key point now is the observation of what happens when we multiply P by itself. Take any element p(2)ij of P²: <blockquote> <img src="https://i.stack.imgur.com/sYmCX.png" alt="p(2)ij"> </blockquote> The product Pr(i → k) · Pr(k → j) is the probability that starting at permutation i we transition into permutation k in one step, and transition into permutation j after another subsequent step. Summing over all in-between permutations k therefore gives us the total probability of transitioning from i to j in 2 steps. This argument can be extended to higher powers of P. A special consequence is the following: <blockquote> p(N)ii is the probability of returning back to permutation i after N steps, assuming we started at permutation i. </blockquote> <h1>Example</h1> Let's play this through with N = 3. We already have a numbering for the permutations. The corresponding transition matrix is as follows: <blockquote> <img src="https://i.stack.imgur.com/HFj0A.png" alt="P"> </blockquote> Multiplying P with itself gives: <blockquote> <img src="https://i.stack.imgur.com/nnRAh.png" alt="P²"> </blockquote> Another multiplication yields: <blockquote> <img src="https://i.stack.imgur.com/ZSdTO.png" alt="P³"> </blockquote> Any element of the main diagonal gives us the wanted probability, which is 15/81 or 5/27. <h1>Discussion</h1> While this approach is mathematically sound and can be applied to any value of N, it is not very practical in this form. The transition matrix P has N!² entries, which becomes huge very fast. Even for N = 10 the size of the matrix already exceeds 13 trillion entries. A naive implementation of this algorithm therefore appears to be infeasible. However, in comparison to other proposals, this approach is very structured and doesn't require complex derivations beyond figuring out which permutations are neighbors. My hope is that this structuredness can be exploited to find a much simpler computation. For example, one could exploit the fact that all diagonal elements of any power of P are equal. Assuming we can easily calculate the trace of PN, the solution is then simply tr(PN) / N!. The trace of PN is equal to the sum of the N-th powers of its eigenvalues. So if we had an efficient algorithm to compute the eigenvalues of P, we would be set. I haven't explored this further than calculating the eigenvalues up to N = 5, however.
Tags
Title
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. POWhat is the probability that the array will remain the same?
 singulars
 PostTypePostTypeId
 PTQuestion
PostTypePostTypeId
1. PTAnswer
UserLastEditorUserId
1. This table or related slice is empty.
UserOwnerUserId
1. USreima
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. This table or related slice is empty.
PostsParentIdCreationDate
1. This table or related slice is empty.
VotesPostIdCreationDate
1. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
2. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
3. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
CommentsPostId

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.