# Help with importance sampling over HUGE sample space

 0 Apologies for the awful typesetting, but MathJax doesn't appear to be working, as described on the FAQ. [fixed; see comment below -- @fbahr] My underlying problem is fairly simple, but the sheer size is what is causing issues. I would like to use importance sampling, but am unsure about its implementation. Problem statement: We have $$\text{N}$$ vectors $$\mathbf{x_i} \in \mathbb{(R^+)}^{k}$$ an a $$\leq$$ constraint for each dimension of $$\mathbb{(R^+)}^{k}$$. I would like to examine all possible on-trivial subsets $$S$$ of the vectors $$\mathbf{x_i}$$ (there are $2^N-1$ of these) and determine, for each vector $$\mathbf{x_i}:\;\; i \in \{1...N\}$$, the fraction of all subsets that satisfy the following constraints: Let $$T := \{1...N\}$$, $$\Omega := 2^T\setminus \emptyset$$, and $$L_i>0 \;\;i \in \{1...N\}$$ Let $$C_i:= S \subset \Omega$$ such that: $$\mathbf{x_i} \in S$$ $$\exists ~j \in \{1...N\}: {\sum\limits_{\mathbf{x_z} \in S} ( \mathbf{x_z} )_j > L_j} \quad \text{and}~ {\sum \limits_{\mathbf{x_z} \in S \setminus \mathbf{x_i}} (\mathbf{x_z})_{j} \leq {L_j}}$$ My goal is to estimate $$\frac{|C_i|}{2^N-1}$$ for each $$i \in \{i...N\}$$ Basically, sets that meet these conditions are ones whose vector sum falls outside the "box" defined by the $$L_i$$ constraints, yet when the $$i^{th}$$ member is removed, it falls inside the box. I figured that importance sampling will help get an estimate withing a reasonable amount of time, where I preferentially select subset sizes that are more likely to meet the above constraints. I would like input on how to formulate the importance sampling distribution over the subsets. My initial thought is to fit a discrete beta distribution to the vector of "reciprocal maximal exceedance ratios", which is $$\min \{\frac{L_k}{(x_j)_k},1\}$$ calculated for each vector. This will approximate the distribution of required subset sizes to exceed the box constraint. asked 13 Oct '14, 12:01 eupraxis 53●6 accept rate: 0% fbahr ♦ 4.6k●7●16 Inline math requires \$$... \$$ delimiters [not \\( ... )\\]. Sometimes, though, things might get a little "fuzzy" (when using * or _ in math – since these are also operators recognized as MarkDown commands; in this case, "escaping" [i.e., putting a single \ in front of the operator] is supposed to help. (13 Oct '14, 13:41) fbahr ♦
Be the first one to answer this question!
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags: