3
$\begingroup$

I'm trying to prove a theorem that seems very intuitive. However, I seem to be missing a piece of the puzzle.

If:

  1. $\pi$ is a random permutation ($S_n$),
  2. $\pi_1, \pi_2$ - random permutations with uniform distributions over $N_1, N_2$ respectively ($N_1,N_2$ are the supports of their distributions),
  3. $N_1\subset N_2\subseteq S_n$,
  4. (*) missing assumption,

then entropies $$H(\pi\circ\pi_1)\leq H(\pi\circ\pi_2).$$ I know that assumptions 1-3 are insufficient, as I've found a counterexample in $S_4$. I'm curious about your suggestions.

[Update] Application of the theorem

Thank you for very interesting contribution. Let me explain the domain of the application. Imagine I have a secret permutation $\Lambda_i\in S_n$, $$\Lambda_i = \lambda_1\circ\lambda_2\circ\dots\circ\lambda_i,$$ of which I have some partial knowledge, namely for each $\lambda_j$ permutation I can limit the set of all possible values to $V_j$ ($|V_j| = (\frac{n}{2})!\,(\frac{n}{2})!$). The possible permutations are equally distributed. Now, I want to replace $\lambda_i$ with $\lambda_i'$ which has a substantially bigger set of possible values $V'_i$. In addition I can prove that $V_i\subset V'_i$. I would like to conclude that (assuming we treat $\lambda_j$ as random variables) $$H(\lambda_1\circ\lambda_2\circ\dots\circ\lambda_i)\leq H(\lambda_1\circ\lambda_2\circ\dots\circ\lambda'_i).$$ To give some more information on the characteristics of $V_j$ sets I have to add that each permutation $\lambda_j$ consists of two permutations $\lambda_j = \rho_j^{(1)}\circ\rho_j^{(2)}$. I know half of the mappings in $\rho_j^{(1)}$ and $\rho_j^{(1)}$. The mappings are complementary, so I never see a complete mapping for $\lambda_j$ (image below). knowledge about $\lambda_j$

The revealed pattern for $\lambda'_i$ is more complex, it consists of 4 permutations. I still know half of the mappings, but I never see a complete path of length 4. However none of the sets of possible permutations seem to be a subgroup.

$\endgroup$
  • $\begingroup$ Please, if you still consider the given answer insufficient, clarify what you expect. Else, consider accepting it. $\endgroup$ – filipos Apr 8 '16 at 18:00
0
$\begingroup$

$N_2$ is a subgroup.

In that case, $\pi \circ \pi_2$ will have uniform distribution on each coset, while the probability of each coset is the same for both $\pi \circ \pi_2$ and $\pi \circ \pi_1$.

Note that $\pi_1$ does not need to be uniform. Also, by translation invariance, the result holds equally well if $N_2$ is a coset.

(The same idea can be applied in the continuous case for compact Lie groups with the Haar measure.)


To understand the difficulties in further generalising the result, we introduce the concept of balance relative to a subgroup.

Definition: Given a subgroup $G \leq S_n$ and a random permutation $\sigma$, the balance of $\sigma$ with respect to $G$ is the entropy of the distribution of the coset of $G$ to which $\sigma$ belongs.

Proposition: Let $\pi$ have uniform distribution in a subgroup $G$ and $\pi_1$, $\pi_2$ be arbitrary random permutations. Then $H(\pi\circ\pi_1) > H(\pi\circ\pi_2)$ if and only if $\pi_1$ is more balanced than $\pi_2$ relative to $G$.

(We prove it by the same reasoning as above. That is, $\pi\circ\pi_i$ is uniform on each coset, so the distribution of the cosets determines the general entropy.)

With this in mind, we can see, for instance, that if $N_2$ has two even permutations and one odd, and $N_1$ has exactly one of each, then $H(\pi\circ\pi_1) > H(\pi\circ\pi_2)$ for $\pi$ uniform in $A_n$. (This gives a minimal counter-example in $S_3$, by the way.)

In general, if $N_2$ has different non-zero numbers of representatives of cosets relative to any subgroup $G$, we can find $\pi$ and $N_1 \subset N_2$ such that $H(\pi\circ\pi_1) > H(\pi\circ\pi_2)$.

$\endgroup$
  • $\begingroup$ Unfortunately, because of the application of the theorem I cannot assume that N_2 (or N_1) is a subgroup. N_1, N_2 are simply sets of possible values for \pi_1, \pi_2. $\endgroup$ – LukN Apr 6 '16 at 14:17
  • $\begingroup$ See the edit. Also, can you explain the application? Then I could have a better idea of what further assumptions to consider (e.g., can we restrict $\pi$? Is there any structure at all in $N_1$ and $N_2$?) $\endgroup$ – filipos Apr 7 '16 at 13:28
  • $\begingroup$ @LukN (forgot to mark you) $\endgroup$ – filipos Apr 7 '16 at 16:43

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.