3
$\begingroup$

Is there a way to sample from a finite set $\{A,B,C,D\}$ such that the limiting empirical proportions converges to the maximum entropy solution of their probabilities consistent with known constraints?

(Example shown for illustration on small scale for understanding of question. Actual problem has around 10^8 probabilities. See comments for earlier discussion)

Example:

Maximize $$H=-\sum_i^n p_i \log(p_i)$$

such that

$$ \begin{bmatrix} 1 & 1 & 1 & 1 \\ 3 & 5 & 6 & 2 \\ 4 & 3 & 2 & 1 \end{bmatrix} \begin{bmatrix} p_A \\ p_B \\p_C \\ p_D \end{bmatrix} = \begin{bmatrix} 1 \\ 4 \\ 3 \end{bmatrix} $$

The exact Maximum Entropy solution is this case is $p^{(*)}=\{0.4182, 0.2800, 0.1855, 0.1164\}$ so would expect about 42% of the simulated values to be A.

The goal is not to solve for $p^{(*)}$ directly and take random samples from those, but to sample from $\{A,B,C,D\}$ in such a way that $p_n^{(\text{Sim})} \rightarrow p^{(*)}$ and $C p_n^{(\text{Sim})} \rightarrow D$ as $n \rightarrow \infty$. (Where $C$ and $D$ are the linear constraint matrix and values). The solution $p^{(*)}$ is taken as unknown, but the constraints they should follow are known.

$\endgroup$
  • $\begingroup$ Could you elaborate on what you mean by "sample from a discrete set"? And what are these "simulated values" you mention? Because you have phrased your problem so abstractly, we have to rely on the mathematical meanings of your words, but those meanings do not seem to permit any reasonable interpretation of what you are describing or asking. $\endgroup$ – whuber May 13 '16 at 20:38
  • $\begingroup$ I rephrased as 'finite' set, the letters could represent anything. The sample could be AABBABABCD... (ad infinitum) where as the proportions of A converge to the maximum entropy solution (in this case about 42%), and we would also expect a certain linear combination of the proportions to converge to [1 4 3]. $\endgroup$ – sheppa28 May 13 '16 at 20:44
  • $\begingroup$ It isn't in the least clear what kind of "sampling" you are proposing, nor by what mechanism you would hope to control the proportions you obtain. Providing some real context and a purpose to this exercise could also help us figure out what you're trying to ask. $\endgroup$ – whuber May 13 '16 at 20:45
  • $\begingroup$ The method on how to sample is the actual question - what algorithm can be used? Is it an application / special case / generalization of MCMC, Gibbs, etc. This I do not know. I haven't seen a way to sample from a distribution where the distribution itself is unknown, but it is known it is the maximum entropy distribution consistent with known constraints. $\endgroup$ – sheppa28 May 13 '16 at 20:52
  • $\begingroup$ Is there a reason you don't wish to solve the optimization problem: maximize H with respect to $p$, subject to $C p = D$? This is a very easy to solve well-behaved convex optimization problem. You could add any other linear or convex conic constraints and it would still be easy to solve. $\endgroup$ – Mark L. Stone May 13 '16 at 21:13

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.