1
$\begingroup$

I have a probability space $\mathcal{X} \times \mathcal{Y}$. $\mathcal{X}$ and $\mathcal{Y}$ could be infinite, but they are at worst case countable.

There is a matrix $A_{xy}$ ranging over $\mathcal{X}$ for rows $\mathcal{Y}$ for columns, which is either 0 or 1 for each $x,y$.

We have the information that

$P(${$ (x,y) \mid A_{xy} = 1$}$) \le \epsilon$.

Is it possible to upper bound the probability $P(${$x \mid \exists y A_{xy} = 1$}$)$, where the bound depends on $\epsilon$ and other parameters given in the question? (say, structure of $A$ perhaps... but I'd rather it be $A$-independent.)

The problem is that we can always create an $A$ such that it has $1$ in row (for each $x$ somewhere, therefore the probability that I want to bound would be 1), but still the probability of total 1s would be $\epsilon$. So I am pretty sure I am not approaching the whole problem formulation the right way.

So maybe you have an idea what assumptions I can make to get a better bound.

One idea that I had is doing the following: assume that we have $\alpha = \sup_{x,y} \frac{P(x)}{P(x,y)}$. Then, we know that:

$P(${$x \mid \exists y A_{xy} = 1$}$) = \sum_x P(x) I(\exists y A_{xy} = 1)\le \sum_{x,y \mathrm{s.t.}\, A_{xy}=1} \alpha P(x,y) \le \alpha \epsilon $ (where $I$ is a 0 1 indicator.)

The thing is that in my case, $\alpha$ could get pretty big if I really define it that way.

  • 1
    What is P(x) and what is P(x, y)? It sounds like you are trying to approach some other problem using a mathematical framework but are not sure how to do it; you should describe that other problem instead.2010-10-21
  • 0
    $P(x)$ is the probability of a collection of labeled graph nodes, could be infinite, and $P(y | x)$ is a probability of edges for this node, so $P(x,y)$ is a joint distribution over labeled graphs.2010-10-21
  • 0
    What? I'm afraid I don't follow. I also don't really see what the question is here, since the only thing with a question mark next to it is a question you've already answered.2010-10-21
  • 0
    Sorry. You can think of $\mathcal{X}$ as a set of labeled nodes for a graph. $\mathcal{Y}$ is a set of edges given a set of labeled nodes. So that $P(x,y)$ is a joint distribution over graphs with edges $y$ and labeled nodes $x$. The question I am asking is what kind of assumptions could I make which are similar to $\alpha = \sup_{x,y} P(x)/P(x,y)$ that I made, but not as less harsh. I want this assumption to enable setting a bound for $P(${$x \mid \exists y A_{xy}=1$}$)$, the first term in the last set of inequalities in the question.2010-10-21
  • 1
    What would you use such a bound for? You should use whatever assumptions are appropriate to your problem. I think it's too general a question to ask for some arbitrary set of assumptions that will work.2010-10-21

1 Answers 1