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 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.