I am trying to estimate the following expectation value $$\mu_f = \sum_x f(x) \Pr(x)$$ for a function $f(x)$ defined for every point $x=(x_1,...,x_p)$ in ordinal state space $\Omega$ (i.e. a discrete phase space). The problem is that the effective amount of dofs $p$ is typically huge: $p$ ~ 9000, but 16,000 in the worst case.

Every dof $x_i \in \Omega$ is completely independent and has 2 to 6 outcomes ('branches') with a known probability determined by a previous algorithm. Here's a plot of the distribution of branch counts and the typical distribution of $\Pr(x_i)$ for each set of possible outcomes.

bc Pr

I can easily generate configurations according to $\Pr(x)$, but not many: $n \approx p$ samples is already a very heavy task for my laptop. In general each configuration $x$ represents a network and $f$ can be a complex network statistic.

To make each sample count, I tried sequential importance sampling as a variance reducing technique. Although my algorithm for $\Pr(x)$ enabled me to produce a very neat biased approximating distribution $q$, the weights $w = p/q$ for a sample simply explode (~3.4$^{1700}$) because of the size of $p$.

As a final very important remark, most (about 3 times $p$) links have a known outcome and are fixed in the simulation of the network. So only 25% actually vary in the computation of $f$ for a configuration (these are the 'effective dofs').

I scanned the literature and Cross Validated (including Using MCMC to evaluate the expected value of a high-dimensional function) but it seems that the amount of dofs is just too big, and the distribution too ... specific. Aggregating similar links can bring the effective amount of dofs to a minimum of $p \approx$ 4000.

So my question is: how can I calculate expected values for an arbitrary function $f$ of a huge collection of independent discrete variables, preferably with an variance/error estimate?

I spent many days trying to solve this problem, but I realize I need help. I would appreciate any clue and thank you all for your time!


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.