Past exam of the mathematics course of the University of Cambridge / 2007 / iii / Paper 13 / 1

Write $p_i=\mathbb{P}(A_i)$. A strong independence graph of maximum degree one consists of isolated vertices and disjoint pairs. For a component $C$, let $B$ be the event that all events outside $C$ are avoided. Each $A_i$, $i\in C$, is independent of $B$, since the outside vertices are all nonneighbors. The union bound therefore givesRemove the components successively. If every $p_i<1/2$, all these factors are positive, including singleton components, so simultaneous avoidance has positive probability. Conversely, two complementary events of probability $1/2$, joined by one edge, cover the sample space. Consequently $\gamma (1)=1/2$. The argument does not assume joint independence between entire two-event components.

For higher degrees use a dependency-degree obstruction on a rooted tree. Put $d=\Delta -1$ and chooseOn a finite rooted $d$-ary tree take independent bits $B_v$ and define $A_v$ to mean that $B_v=1$ and every child bit is zero. The underlying tree is a strong independence graph: the variables used by $A_v$ are disjoint from all variables used by its nonneighbors. Its maximum degree is at most $d+1$.

Give the leaves success probability $r_0=p$, and, working upwards, useas long as this is less than one. This recursion must reach or exceed one after finitely many steps. Indeed,so the iterates strictly increase. An infinite sequence staying below one would either converge to a fixed point, contradicting the displayed maximum, or tend to one, in which case its next iterate would exceed one. At the first offending step set the root success probability to one instead of the proposed value. Every nonroot event then has probability exactly $p$; the root event has probability $(1-r_j{)}^d\le p$.

Every configuration contains an occurring event: start at the root, whose bit is one; if its event fails, descend to a child whose bit is one, and repeat. A finite tree forces this descent to end at an occurring event. Thus avoidance is impossible. Given any $c>p_{\ast }$, choose $p\in (p_{\ast },\min (c,1))$; all event probabilities are strictly below $c$. This proves

With a cyclically oriented independence digraph of events, each event is independent of one of the other two. Independence is symmetric, so all three pairs are independent events. This does not imply mutual independence. Put $x=\mathbb{P}(A_1\cap A_2\cap A_3)$. The inclusion-exclusion principle givesbecause $x\le \mathbb{P}(A_1\cap A_2)=a^2$. Thus the oriented case guarantees positive avoidance exactly when $0<a<1/2$.

For sharpness, for any $1/2\le a<1$ prescribe the law of the three event indicators by assigning mass $(1-a{)}^2$ to each of the three singleton success patterns, $(1-a)(2a-1)$ to each doubleton, $1-3a+3a^2$ to the tripleton, and zero to the zero-success pattern. All masses are nonnegative and their sum is one. Each marginal isand each pair intersection has mass $(1-a)(2a-1)+(1-3a+3a^2)=a^2$. These events satisfy the oriented independence conditions and have zero avoidance probability.

The unoriented triangle imposes no independence conditions at all: every vertex is adjacent to every other. The union bound gives positive avoidance if $3a<1$. To see that this is sharp for every $a\ge 1/3$, use uniform measure on the circle of circumference one and take three arcs of length $a$ starting at $0,1/3,2/3$. They cover the circle. Hence the unoriented case guarantees positive avoidance exactly when $0<a<1/3$.