Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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. – Qiaochu Yuan Oct 21 '10 at 17:42
$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. – normvector Oct 21 '10 at 17:44
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. – Qiaochu Yuan Oct 21 '10 at 17:46
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. – normvector Oct 21 '10 at 17:56
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. – Qiaochu Yuan Oct 21 '10 at 17:58

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.