# AIC/BIC: how many parameters does a permutation count for?

Let's say I have a model selection problem and I am trying to use AIC or BIC to evaluate the models. This is straightforward for models that have some number $k$ of real-valued parameters.

However, what if one of our models (for example, the Mallows model) has a permutation, plus some real-valued parameters instead of just real-valued parameters? I can still maximize the likelihood over the model parameters, for example obtaining a permutation $\pi$ and a parameter $p$. However, how many parameters does $\pi$ count toward for computing AIC/BIC?

• Is this AIC on AIC? Mallows Cp model has been shown to be equivalent to AIC. en.wikipedia.org/wiki/Mallows's_Cp – EngrStudent Mar 28 '14 at 21:56
• Mallows Cp is a model selection technique for regression. I'm asking about model selection for a different statistical model that also has its name, but which has a permutation as one of its parameters. – Andrew Mao Mar 31 '14 at 0:05
• Andrew, I had hoped to get a good answer for this. Sorry that it did not work out so well. -mike – EngrStudent Apr 8 '14 at 21:09
• Perhaps there is a simulation approach - something where you can find the answer and publish it. It might be novel material. – EngrStudent Jan 25 '15 at 18:33

Intuitively, I suspect that the set of all permutations on $p$ elements is equivalent to $p^2-2p+1$ parameters.
This is because the permutation matrices are the extremal points of the convex space of doubly-stochastic real matrices of rank $p$, and in general the doubly-stochastic matrices have $p^2-2p+1$ parameters (you get $2p$ constraints because all row sums have to all be 1 and column sums have to all be 1, but one of these is redundant, so you have $2p-1$ constraints on $p^2$ entries).
• Great explanation, but what do you mean by "trying it numerically"? Something also feels wrong about this because giving each element a parameter will induce any permutation, and that is only a total of $p$ parameters. – Andrew Mao Feb 25 '15 at 15:50
• Parameters (at least in the context of AIC, and arguably in general) are continuous. Thinking of an index as a parameter is a common trap, since although the "parameters" (2, 3, 1) specify the permutation (123), there is no obvious way to interpret (2.1, 3, 1). If you think instead of parameters moving mass, you get the doubly-stochastic matrices as I described. By numerically, I mean: simulate data from a known model and then estimate using AIC with the three penalizations $p$ (yours), $p^2-2p+1$ (mine), and $p!$ (naive enumeration) and see which one recovers the known model "best". – Timothy Teräväinen Mar 1 '15 at 3:32