# Using order statistics and recovering unordered variable

I have a serious model fitting issue, and wanted to pick the brains of the forum members here.

My model involves multivariate (d \ge 3) latent variables which contribute to the likelihood. Each of the components have identical marginal distributions, but have a very complicated dependence structure. I have figured the proper multivariate *_lpdf functions for d=3, but higher values are intractable.

However, it turns out I can easily (d \le\ \sim 20) find the expressions for the telescoping product of conditional densities, but of the order statistics of my original variables. That is, these functions:

f(x_{(1)})\_\mathrm{lpdf},
f(x_{(2)}|x_{(1)})\_\mathrm{lpdf},
f(x_{(3)}|x_{(1)},x_{(2)})\_\mathrm{lpdf},

and so on. I then wrote these into the likelihood, then performed a random permutation of the resulting order statistics to propagate the latent variable into my model calculations. Here however, the convergence of my model failed dramatically (n_{\mathit{eff}} < 10) and I could not improve it.

I suppose this is due to the discontinuity of the gradient of the permuting process, though am not sure. Is there any workaround available for multivariate situations like this, where the raw unordered variables are not tractable but the order statistics are, and which can successfully exploit them?

JZ

1 Like

Hi,
I am not sure I understand your problem well, but couldnâ€™t you treat the order statistics as the latent variables, i.e. have: ordered[d] x_order; as the parameter? If you need to handle both the actual x in some other than ascending/descending order AND the order statistics of x then this is likely intractable in Stan.

Best of luck with your model!

Thank you Martin. I could use an ordered type for storage to start generating the latent variables although itâ€™s not strictly necessary. I can generate the [vector/row_vector/ordered/array] of order statistics just fine. The problem Iâ€™m having is that I then need to randomly permute these order statistics, as the marginals for the components of the actual latent variable are identical.

I do now suspect this permuting approach is not feasible.
Thanks again.

I donâ€™t really understand what this means. Could you be more specific? Why do you need to randomly permute the order statistics? What kind of object are you trying to emulate - wouldnâ€™t randomly permuting order statistics be either undefined or represent some sort of uniform-ish distribution?

It is well possible that what you want to do is not possible, but I currently donâ€™t understand it enough to be able to form an informed opinionâ€¦

I appreciate the time and your concern. Let me try an example.

Letâ€™s say the problem involves a 4D latent variable X= [x1, x2, x3, x4]. Each of these x_i are identically distributed, but they have a very complicated dependence structure so that expressing the (log) density f(x1, x2, x3, x4)\_lpdf is not reasonably possible.

But it turns out the density of the minimum of the x_i is straightforward. And then, conditional on the minimum, the density of the second order statistic x_(2) is tractable. Same with each order statistic, conditional on all the smaller ones. Therefore it is easy to express f(x_{(1)}, x_{(2)}, x_{(3)}, x_{(4)} )\_lpdf as a telescoping product of x_{(1)}'s density and the subsequent three conditional densities. These densities are defined in the functions block, and the x_{(i)} are then parameters which are then concatenated into X* in the transformed variables block. But X* is [x_{(1)}, x_{(2)}, x_{(3)}, x_{(4)} ], a sorted row vector (it could be another type, not the issue).

To get X I need to randomly generate one of the 24 permutations of these, to undo the ordering process. This can be done in the transformed parameters block, say by using another parameter U which is a 4D iid uniform RV, computing its ranks, and indexing X* with the ranks. Recall each component of X need to be identically distributed, certainly not the case if the components are sorted!

Using the order statistics is merely meant to be a computational trick to get at X. But this last step, the â€śunsortingâ€ť process, seems to break the sampler. What Iâ€™d like to know is, is this random unsorting hopeless (presumably because of the discontinuous gradients of the random permuting), or is there a workaround that will sample well?

Hereâ€™s what I donâ€™t understand - are the order statistics sufficient statistics for your sample or not? I.e. could you - at least in theory - learn more than the order statistics from the observed data? If order statistics are not sufficient, how do the x1, x2, x3, x4 enter the likelihood beyond f(x_{(1)}, x_{(2)}, x_{(3)}, x_{(4)} )\_lpdf ? If you can share the Stan code, it might also help a bit to clarify.

Yeah, that sounds quite hopeless if you need to use X in a general way. If you have a specific way you need to use X, there might IMHO be workarounds - what do you need the X for?

Does that make sense?

No the order statistics are just a trick to get at the unordered variable. Neither ordered nor unordered variables are sufficient at all; the closest analog would be the measurement error discussion in the Userâ€™s Guide, section 6.1, where a set of uniform RVs are simulated, to be added into rounded data to simulate the unrounded data. But they carry no information about the data themselves - they are around merely to improve the accuracy of the posterior inference. And my unordered variable is just a trick to improve my inference as well.

Let me put together a couple of Stan programs to demonstrate this. One thing I should try is to verify that I get convergence when I do not unsort the X*, even if the underlying model is now completely wrong.

2 Likes

This only holds (without further assumptions) in the i.i.d. case. Since the x_i are correlated, all bets are off.