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's gravatar image

accept rate: 0%

edited 13 Oct '14, 14:19

fbahr's gravatar image

fbahr ♦

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

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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



Asked: 13 Oct '14, 12:01

Seen: 549 times

Last updated: 13 Oct '14, 14:26

OR-Exchange! Your site for questions, answers, and announcements about operations research.