Let $p$ be a (sub)probability vector, supported on $\mathbb{N}$. Let $\sigma$ be a permutation on $\mathbb{N}$. This permutation is generated by swapping adjacent elements $i$ and $i+1$ of $\mathbb{N}$, we can create a sequence of swaps by first swapping $\sigma^{-1}(1) - 1$ and $\sigma^{-1}(1)$, etc, till we swap $1$ and $\sigma^{-1}(1)$. We can repeat these actions.

Every such a swap costs $\left( \frac{1 + p_i}{1 + p_j}\right)^a$, where $a>0$, if we swap $j$ with $i$. We can use this to assign costs to a permutation $\sigma$, by assigning as a cost, the product of the costs per swap. If we denote $\text{Swaps}(\sigma)$ the collection of swaps needed, i.e. the pair which we need to swap, then the costs for a permutation are given by $$\text{costs}(\sigma) = \prod_{s \in \text{swaps}(\sigma)} \left(\frac{1 + s_1}{1 + s_2} \right)^a.$$

Now $$\sum_{\sigma} \text{costs}(\sigma)$$ wont be finite, because we can have probability vectors like $(1/4,1/4,1/8,1/8,...)$ which have infinitely many pairs. However, if we mod out the set of permutations by the equivalence relation that two permutations, $\sigma, \tau$ are equivalent, $\sigma \sim \tau$, iff $\sigma(i) = \tau(j)$ implies $p_i = p_j$, i.e. $i$ does not need to be equal to $j$, but they have the same probability mass. Note that the costs function descents to costs function on the equivalence classes, because we can first order the (sub)probability vector, then do the necessary permutations at costs 1 to switch the two points, and then undo the ordering of the (sub)probability vector again. Is $$\sum_{\sigma \in S^{\mathbb{N}}/\sim} \text{costs}(\sigma)$$ finite? The case where $p$ is a finite (sub)probability vector is easy because then we have a finite sum, however, I was wondering if this can be extended to the case where we have an infinite number of support points.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.