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

1

You have a two sets of nodes, $X$ and $Y$, with $A_{i,j}=1$ when there is an edge from $i\in X$ to $j \in Y$. You are given that only a fraction $\epsilon$ of the possible edges are occupied and want the chance that a given $i\in X$ has at least one edge occupied. If $|Y|$ is large the chance can be quite high. Your bound would be to recognize that the worst case is if each node in $X$ has only one edge occupied. Then the bound is $\epsilon * |Y|$ (or 1 if smaller). The size of $X$ doesn't matter. Essentially the elements of $X$ are all independent. If the sets are infinite you need to worry about how you take limits.