User bobby kleinberg - MathOverflow

Tail bound for Poisson random variable

2012-08-10T14:13:30Z

Is the following fact about Poisson random variables true?

For any $\lambda \in (0,1)$ and integer $k > 0$, if $X$ is a Poisson random variable with mean $k \lambda$, then $\Pr(X < k) \geq e^{-\lambda}$.

It clearly holds for $k=1$, and for any fixed $\lambda$ it's easy to see that it holds for all sufficiently large $k$, but for intermediate values of $k$ it's not obvious to me.

Answer by Bobby Kleinberg for Is there some generalization of the "Maximum Coverage Problem" for information in random variables ?

2011-05-17T11:53:31Z

The prototypical way of measuring the "information content" of a set of random variables is by evaluating the Shannon entropy of their joint distribution. It is known that entropy is a submodular set function and that it is monotone: the joint distribution of a subset of the random variables cannot have more entropy than that of the set itself. Your question therefore becomes a special case of the following broader question: given the ability to evaluate a monotone, non-negative, submodular set function, how can I compute the $k$-element subset that maximizes this function? There is a greedy algorithm that generalizes the greedy algorithm for the maximum coverage problem: starting from the empty set, repeatedly enlarge your set by adding a single element that yields the greatest increase in the function value, until the number of elements chosen equals $k$. This algorithm, like the greedy algorithm for maximum coverage, achieves an approximation ratio of $e/(e-1)$. (Nemhauser, Wolsey, and Fisher, An analysis of approximations for maximizing submodular set functions, Math. Programming 14 (1978), 265-294.)

There are at least two senses in which this approximation ratio is the best possible under polynomial resource constraints. First, if the algorithm is only allowed to access the function by querying its value at specified sets, then any algorithm achieving an approximation ratio strictly less than $e/(e-1)$ must use an exponential (in $k$) number of queries. (Nemhauser and Wolsey, Best algorithms for approximating the maximum of a submodular set function, Math. Oper. Res. 3:3 (1978), 177-188.) Second, assuming the $P \neq NP$ conjecture, no polynomial-time algorithm can achieve a better approximation ratio, even for the special case of maximum coverage problems.

Compactness theorem with preserved substructure

2010-12-22T15:30:24Z

Suppose $T$ is a first-order theory whose signature contains $(+,\cdot,0,1,<)$ as well as a unary predicate $R(x)$. Suppose every finite subset $S \subseteq T$ has a model in which the set of elements satisfying $R(x)$ forms a substructure isomorphic to the field of real numbers. Does it follow that $T$ itself has a model in which the set of elements satisfying $R(x)$ forms a substructure isomorphic to the field of real numbers?

Answer by Bobby Kleinberg for How many pairs of edges can disconnect a biconnected graph?

2010-08-17T12:54:47Z

The statement is true. In fact, much more general statements are true. If $G$ is a graph with $n$ vertices and $c$ is the cardinality of a minimum edge cut of $G$, then the number of edge cuts of cardinality $c$ is at most $\binom{n}{2}$, and for every half-integer $k \geq 1$, the number of edge cuts containing at most $kc$ edges is bounded above by $2^{2k-1} \binom{n}{2k}.$

The upper bound of $\binom{n}{2}$ on the number of minimum cuts is attributed to Bixby and Dinitz-Karzanov-Lomonosov. The more general bound on the number of approximate minimum cuts is due to Karger (Global min-cuts in RNC, and other ramifications of a simple min-cut algorithm), who also re-proved the $\binom{n}{2}$ bound on minimum cuts. His appealingly simple proof rests on the analysis of a simple "randomized contraction" algorithm. Here we present the proof that the number of minimum cuts is at most $\binom{n}{2}$.

Suppose that $G$ is a multigraph with $n$ vertices, $c>0$ is the number of edges in a minimum cut of $G$, and $A$ is a specific set of $c$ edges whose removal disconnects $G$. Repeatedly perform the following process to obtain a sequence of multigraphs $G = G_0, G_1, \ldots, G_{n-2}$: choose a uniformly random edge of $G_t$ and contract it to obtain $G_{t+1}$. In other words, if $(u,v)$ is the edge chosen in step $t$, then we replace $u$ and $v$ with a single vertex $z$ in $G_{t+1}$, and we replace every edge of $G_t$ having exactly one endpoint in ${u,v}$ with a corresponding edge of $G_{t+1}$ with endpoint $z$. (Edges from $u$ to $v$ in $G_t$ are deleted during this step.) Note that $G_{n-2}$ has exactly two vertices $a,b$, these vertices correspond to a partition of $V(G)$ into two nonempty sets $A,B$ (those vertices that were merged together to form $a \in V(G_2)$, and those that were merged together to form $b$), and that the edges of $G_{n-2}$ are in one-to-one correspondence with the edges of the cut separating $A$ from $B$ in $G$. Denote this random cut by $R$.

Now consider a specific cut $C$ of cardinality $c$. We claim that the probability of the event $R=C$ is at least $1 \left/ \binom{n}{2} \right.$, from which it follows immediately that the number of distinct cuts of cardinality $c$ is at most $\binom{n}{2}$. To prove the upper bound on the probability that $R=C$, observe that for all $t = 0,\ldots,n-2$, every vertex of $G_t$ has degree at least $c$. (Otherwise, that vertex of $G_t$ corresponds to a set of vertices in $G$ having fewer than $c$ edges leaving it, contradicting our assumption about the edge connectivity of $G$.) Consequently, the number of edges of $G_t$ is at least $(n-t)c/2$, and the probability that an edge of $C$ is contracted in step $t$, given that no edge of $C$ was previously contracted, is at most $c/|E(G_t)| \leq 2/(n-t)$. Combining these bounds, we find that the probability that no edge of $C$ is ever contracted is bounded below by $\prod_{t=0}^{n-3} \left(1 - \frac{2}{n-t}\right) = \frac{n-2}{n} \cdot \frac{n-3}{n-1} \cdots \frac{1}{3} = \frac{2}{n(n-1)}.$

Answer by Bobby Kleinberg for Lower bounds for chromatic number of a graph

2010-07-30T11:09:03Z

Hoffman's bound states that $\chi(G) \geq 1 - \frac{\lambda_1(G)}{\lambda_n(G)}$ where $\lambda_1(G), \lambda_n(G)$ denote the largest and smallest eigenvalues of the adjacency matrix of $G$. (Note that $\lambda_n(G)$ is negative.)

Comment by Bobby Kleinberg

2012-08-10T16:18:36Z

Maybe "tail bound" was a poor choice of words. I'm thinking of $\lambda$ as a fixed constant in (0,1), and I think the difficult case is actually when $\lambda$ is very close to 1, so $e^{-\lambda}$ should not be interpreted as inverse-exponential. The probability a Poisson equals its mode is inverse-square-root, this would enable a lower bound of $\Theta(1/\sqrt{k})$, but that doesn't exceed $e^{-\lambda}$ when $k$ is larger than $e^{c \lambda}$ for some $c$.