Let $X$ be a sequence of items, and let $Y$ be a permutation of $X$ (a sequence with the same items, but possibly rearranged).

Let $S_{ij}$ be a random variable that equals $1$ if items $i$ and $j$ are swapped between $X$ and $Y$. For instance, if $X=\langle A,B,C\rangle$ and $Y=\langle B,C,A\rangle$, we have that $S_{AB}=S_{AC}=1$ and $S_{BC}=0$. In the general case, the space of $(S_{AB},S_{AC},S_{BC})$ would have $8$ outcomes, but because of the order restrictions we have only $6$. For instance, $S_{BC}=0$ and $S_{AC}=1$ imply $S_{AB}=1$.

Assume I can estimate each $S_{ij}$ independent of the others, that is, I can calculate $p_{ij}=E[S_{ij}]$. The problem comes when I want to compute the probability of a particular permutation, knowing each of these $p_{ij}$ estimates.

For example, take all possible outcomes with a sequence of three elements:

$\begin{matrix} outcome & S_{AB} & S_{AC} & S_{BC}\\\hline ABC & 0 & 0 & 0\\ BAC & 1 & 0 & 0\\ BCA & 1 & 1 & 0\\ ACB & 0 & 0 & 1\\ CAB & 0 & 1 & 1\\ CBA & 1 & 1 & 1 \end{matrix}$

If I draw the probability tree from left to right:

enter image description here

According to this tree, $P(ACB)=(1-p_{AB})(1-p_{AC})p_{BC}$. However, if I draw the probability tree from right to left:

enter image description here

we get $P(ACB)=p_{BC}(1-p_{AC})$.

So it's obvious I'm doing something wrong, but I can't figure out what it is. The immediate clue is that I can't just plug $p_{ij}$ into the edges of the trees because of dependencies, but I'm not sure what I should do, or even if it can be done just with $p_{ij}$ for that matter.

Edit: I also tried to stick to the actual tree as follows. In the first tree for instance, through the edge from $S_{AB}=0$ to $S_{AC}=0$ we have two leafs, and only one leaf through the edge from $S_{AB}=0$ to $S_{AC}=1$. If we say that in the first edge we have probability $2(1-p_{AC})/k$ and in the second one we have $p_{AC}/k$, where $k=2(1-p_{AC})+p_{AC}$ is used to add up to 1. Still, depending on the tree we'll have different probabilities for some outcomes.

  • $\begingroup$ Maybe I'm misunderstanding the meaning of $S_{ij}$, but it doesn't seem that your $S_{ij}$ are well defined. To get from ABC to BCA you can swap AB, and then swap AC, or you can swap AC, and then BC -- it's unclear what the 'correct' values for $S_{ij}$ are. And for the permutation ACB, why isn't it the case that $S_{AB}=0, S_{BC}=1, S_{AC}=0$? $\endgroup$
    – grand_chat
    Mar 18, 2015 at 17:47
  • $\begingroup$ I'm not sure the order in which we apply the swaps is important here. The permutation from ABC to BCA results in $S_{AB}=1,S_{AC}=1,S_{BC}=0$ regardless of what swap comes first. Do you mean that each $p_{ij}$ depends on the order in which we apply swaps? As to the final question, that is the case in the examples; not sure what you mean. $\endgroup$ Mar 18, 2015 at 17:56
  • $\begingroup$ Starting with ABC, if you swap AB first and then AC, you get BCA. If you swap AC first and then AB, you get CAB. Am I misunderstanding something? $\endgroup$
    – grand_chat
    Mar 18, 2015 at 18:08
  • $\begingroup$ I see what you mean, that's a good point. $S_{ij}$ does not represent a swap operation on the sequence, as if we could define the permutation as a sequence of such operations. Instead, it just partially represents the final state of the permutation, regardless of what operations were performed (I say partially because it only refers to two items). $\endgroup$ Mar 18, 2015 at 18:20
  • $\begingroup$ OK, I think I understand. The $S_{ij}$ taken as a whole are a characterization of the final permutation--each final permutation is assigned a unique collection of $S_{i,j}$. $\endgroup$
    – grand_chat
    Mar 18, 2015 at 19:05

1 Answer 1


I think the problem you are seeing arises because you are not populating your probability trees with conditional probabilities. You can't use the same $1-p_{AC}$ in the first tree as in the second tree; what needs to go in the second leg of the path to ACB is the conditional prob of $S_{AC}=0$ given what is known. For example in the first tree's path to ACB you've got $1-p_{AC}$, which equals $$P(S_{AC}=0),$$ where you really need the conditional probability $$P(S_{AC}=0|S_{AB}=0).$$ The required conditional probs cannot in general be deduced from $p_{AB}$, $p_{BC}$, and $p_{AC}$ alone (unless, for instance, the $S_{ij}$ are independent, which they aren't in your case).

Try building the two trees assuming each of the six outcomes is equally likely, and populating the paths with conditional probabilities; you'll find a prob of 1/6 is correctly calculated for every leaf permutation whether you build the tree left-to-right or right-to-left.

  • $\begingroup$ Well, yes, if I build the tree assuming that each outcome is equally likely, I'll end up with 1/6 in each leaf. But I can't just assume that. In fact, we know they are not equally likely. That'd be like ignoring all $p_{ij}$. $\endgroup$ Mar 18, 2015 at 23:46
  • $\begingroup$ The equally-likely outcomes exercise is intended to demonstrate that you have to populate your tree with conditional probabilities. If you don't do this, you'll find that you get the wrong answer. For your problem, you need more information than just estimates of the $p_{ij}$ in order to properly calculate the probability of each permutation. $\endgroup$
    – grand_chat
    Mar 19, 2015 at 0:17
  • $\begingroup$ This is what I'm fearing; please, take a look at the edit in my question. So the answer then is that there is no way of doing this just with the $p_{ij}$ estimates, right? If you state this in your answer I'll mark it as accepted. $\endgroup$ Mar 19, 2015 at 0:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .