Finite Probability and the Probabilistic Method

Assume $A$ is empty.

Then $\mathbb{P}(A)=0$ by [L1], so $\mathbb{P}(A)$ is not positive.

The contrapositive proves that positive probability implies nonemptiness. It asserts existence of an outcome, not a canonical choice of one.

If $\mathbb{E}[X]<1$, [L2] gives $\mathbb{P}(X\ge 1)<1$, so [L4] gives $\mathbb{P}(X=0)>0$ because a nonnegative integer is either zero or at least one.

If $\mathbb{E}[X]>0$, an outcome with $X\ge \mathbb{E}[X]>0$ exists by [L1].

By [L3], the event $\{X=0\}$ is nonempty.

The two averaging assertions are exactly [L1]; steps 1.1 and 2.1 prove avoidance, and step 1.2 proves forcing.

On every outcome, deleting at most one unit per listed defect leaves an admissible object of size at least $Y-X$.

By [L2], there is an outcome with $Y-X\ge \mathbb{E}[Y-X]$.

Repair that outcome. Its size is at least $\mathbb{E}[Y-X]=\mathbb{E}[Y]-\mathbb{E}[X]$ by [L1]. Overlisting defects increases $X$ and therefore cannot invalidate the lower bound.

If $x=0$, then $1+x=1=\exp (x)$.

If $x>0$, [L5] and [L2] give $\exp (x)-1=\exp (c)x$ for some $0<c<x$; [L3] gives $\exp (c)>1$, hence $\exp (x)>1+x$.

If $x<0$, apply [L5] on $[x,0]$: $1-\exp (x)=\exp (c)(-x)$ for some $x<c<0$. Now $0<\exp (c)<1$ by [L3] and [L4], so $1-\exp (x)<-x$ and $1+x<\exp (x)$.

The three cases prove $1+x\le \exp (x)$ for every real $x$.

Apply step 2.1 to $x=-p$ to get $0\le 1-p\le \exp (-p)$, then raise both sides to the natural power $m$ and use [L7] repeatedly to obtain $(1-p{)}^m\le \exp (-mp)$. The case $m=0$ is equality, including $p=1$.

Each required-present coordinate has probability $p$ and each required-absent coordinate has probability $1-p$.

Mutual independence factors the joint probability as $p^r(1-p{)}^s$. This remains valid for empty prescriptions and for $p=0,1$.

For a fixed graph, take its $m$ edges as $R$ and the remaining $\left(\genfrac{}{}{0px}{}{n}{2}\right)-m$ possible edges as $F$.

Iterating [L3] gives $\exp (t{\sum }_i{X}_i)={\prod }_i\exp (t{X}_i)$ pointwise. For any joint values of the transformed variables, each corresponding event is a disjoint union of joint-value events of the $X_i$; summing the products supplied by [L4] and factoring the finite sums with [L5] proves that the transformed variables remain mutually independent.

Apply [L2] to step 1.1 and use [L1] in each factor to obtain the formula.

For $I=\mathrm{\varnothing }$, the sum is zero, $M_0(t)=\exp (0)=1$, and the product is empty and equals $1$.

Direct averaging gives $\mathbb{E}[\exp (t\epsilon )]=(\exp (t)+\exp (-t))\mathrm{/}2$.

For every $j\ge 0$, $(2j)!={\prod }_{r=1}^j(2r-1)(2r)\ge {\prod }_{r=1}^{j}2r=2^{j}j!$, including $j=0$.

Expanding both exponentials by [L2] and using [L4], the odd powers cancel and the result is ${\sum }_{j\ge 0}{t}^{2j}\mathrm{/}(2j)!$.

Hence $t^{2j}\mathrm{/}(2j)!\le (t^2\mathrm{/}2{)}^j\mathrm{/}j!$ term by term, and [L4] gives $\mathbb{E}[\exp (t\epsilon )]\le {\sum }_{j\ge 0}(t^2\mathrm{/}2{)}^j\mathrm{/}j!=\exp (t^2\mathrm{/}2)$.

For $u>0$, strict monotonicity gives $\{S\ge t\}=\{\exp (uS)\ge \exp (ut)\}$, so [L1] gives $\mathbb{P}(S\ge t)\le \exp (-ut)\mathbb{E}[\exp (uS)]$.

By [L2] and [L3], $\mathbb{E}[\exp (uS)]\le \exp (n{u}^2\mathrm{/}2)$.

Choose $u=t\mathrm{/}n>0$. Substitution in steps 1.1 and 1.2 gives $\mathbb{P}(S\ge t)\le \exp (-t^2\mathrm{/}(2n))$.

Negation merely relabels the two attained values of each sign, so the joint-value factorization in [L6] shows that the variables $-{\epsilon }_i$ are again mutually independent uniform signs. Step 2.1 applied to $-S$ gives the same bound for $\mathbb{P}(S\le -t)$.

Since $\{\mathrm{\mid }S\mathrm{\mid }\ge t\}=\{S\ge t\}\cup \{S\le -t\}$, [L5] and steps 2.1 and 3.1 give the result. The excluded boundary $t=0$ would only give the valid but uninformative bound $1\le 2$.

For $S=\mathrm{\varnothing }$, the conditional probability is $\mathbb{P}(A_i)\le x_i{\prod }_{j\in N_D^{+}(i)}(1-x_j)\le x_i$.

Assume the assertion holds whenever the conditioning set has fewer than $m$ elements, and let $\mathrm{\mid }S\mathrm{\mid }=m>0$. Put $S_1=S\cap N_D^{+}(i)$ and $S_2=S\setminus S_1$.

If $S_1=\mathrm{\varnothing }$, [L3] gives $\mathbb{P}(A_i\mid {\bigcap }_{j\in S}{A}_j^c)=\mathbb{P}(A_i)\le x_i$.

Suppose $S_1\mathrm{\ne }\mathrm{\varnothing }$, order it as $j_1,\dots ,j_r$, and write $C_t={\bigcap }_{j\in S_t}{A}_j^c$. Since $\mathbb{P}(C_1\cap C_2)>0$, also $\mathbb{P}(C_2)>0$. Conditional multiplication gives $\mathbb{P}(A_i\mid C_1\cap C_2)=\mathbb{P}(A_i\cap C_1\mid C_2)\mathrm{/}\mathbb{P}(C_1\mid C_2)\le \mathbb{P}(A_i\mid C_2)\mathrm{/}\mathbb{P}(C_1\mid C_2)=\mathbb{P}(A_i)\mathrm{/}\mathbb{P}(C_1\mid C_2)$, where the equality uses [L3] because $S_2$ consists of non-out-neighbours of $i$.

The chain rule writes $\mathbb{P}(C_1\mid C_2)={\prod }_{q=1}^r(1-\mathbb{P}(A_{j_q}\mid {\bigcap }_{h\in S_2\cup \{j_1,\dots ,j_{q-1}\}}{A}_h^c))$. Every displayed conditioning set has fewer than $m$ elements and positive probability, because its complement intersection contains the positive event $C_1\cap C_2$. The induction hypothesis therefore bounds the conditional probability by $x_{j_q}$, so this denominator is at least ${\prod }_{j\in S_1}(1-x_j)$.

Consequently $\mathbb{P}(A_i\mid {\bigcap }_{j\in S}{A}_j^c)\le \mathbb{P}(A_i)\mathrm{/}{\prod }_{j\in S_1}(1-x_j)\le x_i{\prod }_{j\in N_D^{+}(i)\setminus S_1}(1-x_j)\le x_i$.

Steps 2.1 and 4.1 cover the two possibilities for $S_1$, completing the induction. No conditional probability with zero denominator was formed.

For an empty event family, the intersection is the whole space and both empty products equal $1$.

Order a nonempty family as $i_1,\dots ,i_m$ and assume the first $r-1$ complements have intersection probability at least ${\prod }_{q<r}(1-x_{i_q})>0$.

By [L1], the conditional probability of $A_{i_r}$ given those complements is at most $x_{i_r}$, so the conditional probability of $A_{i_r}^c$ is at least $1-x_{i_r}>0$.

Multiplying by the positive prefix probability gives $\mathbb{P}({\bigcap }_{q\le r}{A}_{i_q}^c)\ge {\prod }_{q\le r}(1-x_{i_q})>0$.

Induction through $r=m$ proves both the lower bound and positivity.

Suppose $d=0$ and set every $x_i=1\mathrm{/}e$. Applying [L2] at $y=1$ gives $2\le e$, so $0<x_i<1$. The hypothesis gives $p\le 1\mathrm{/}e=x_i$, and the empty neighbour product is $1$, so [L1] applies.

Suppose $d\ge 1$ and set every $x_i=1\mathrm{/}(d+1)$. From [L2] at $y=1\mathrm{/}d$ and [L3], $(1+1\mathrm{/}d{)}^d\le e$, hence $(1-1\mathrm{/}(d+1){)}^d=(d\mathrm{/}(d+1){)}^d\ge 1\mathrm{/}e$.

Each vertex has at most $d$ out-neighbours, so $x_i{\prod }_{i\to j}(1-x_j)\ge 1\mathrm{/}(e(d+1))\ge p$ by the hypothesis. Thus [L1] applies.

The cases $d=0$ and $d\ge 1$ are exhaustive and both give positive probability that no bad event occurs.

Colour every vertex independently and uniformly red or blue. For a fixed edge, its $k$ colours are all red or all blue with probability $2\cdot 2^{-k}=2^{1-k}$.

Let $X$ count monochromatic edges. Then $\mathbb{E}[X]=\mathrm{\mid }E\mathrm{\mid }{2}^{1-k}<1$.

By [L4], some colouring has $X=0$ and is proper. If $k=1$, the edge hypothesis forces $E=\mathrm{\varnothing }$, and the same proof applies.

Colour vertices independently and fairly. For each edge $F$, let $A_F$ be the event that $F$ is monochromatic. The two monochromatic assignments are disjoint and each has product weight $2^{-k}$, so $\mathbb{P}(A_F)=2^{1-k}$.

Join two bad events when their edges meet. If all edges indexing a complement conjunction are disjoint from $F$, that conjunction depends only on coordinates outside $F$; finite Fubini in [L2] factors its intersection probability with $A_F$. Thus [L3] makes the edge-intersection graph a dependency graph, and its degree is at most $d$.

The numerical hypothesis is $e{2}^{1-k}(d+1)\le 1$, so [L4] gives positive probability that no edge is monochromatic.

By [L5], the positive-probability event in step 2.1 contains a colouring, and that colouring is proper. For $k=1$, [L6] gives $e(d+1)\ge 2>1=2^{k-1}$, so the numerical hypothesis cannot hold; the empty-edge case for admissible parameters is immediate.

Place every vertex independently and fairly into one of two parts. A fixed edge crosses with probability $1\mathrm{/}2$.

If $X$ is the number of crossing edges, [L3] gives $\mathbb{E}[X]=m\mathrm{/}2$.

By [L4], some bipartition has $X\ge m\mathrm{/}2$. When $m=0$, every bipartition attains equality.

Orient every possible edge independently and fairly. A fixed ordering of the vertices is a directed Hamilton path exactly when its $n-1$ consecutive edges receive prescribed orientations, an event of probability $2^{-(n-1)}$.

Sum an indicator over the $n!$ orderings. Its expectation is $n!\mathrm{/}{2}^{n-1}$.

Some tournament has at least this many directed Hamilton paths. For $n=1$, the unique ordering is a Hamilton path and the bound is $1$.

Orient every edge independently and fairly. For a fixed $k$-set $S$, each outside vertex dominates all of $S$ with probability $2^{-k}$, independently across outside vertices; hence the failure probability is $(1-2^{-k}{)}^{n-k}$.

The union bound gives total failure probability at most $F_k(n):=\left(\genfrac{}{}{0px}{}{n}{k}\right)(1-2^{-k}{)}^{n-k}$.

The ratio $F_k(n+1)\mathrm{/}{F}_k(n)=\frac{n+1}{n+1-k}(1-2^{-k})$ is at most $1$ whenever $n+1\ge k{2}^k$. Thus $F_k(n)$ is nonincreasing throughout the stated range.

Suppose $k=1$. At $n=6$, $F_1(6)=6\mathrm{/}{2}^5<1$.

Suppose $k=2$. At $n=48$, $F_2(48)=1128(3\mathrm{/}4{)}^{46}$. Since $(3\mathrm{/}4{)}^8=6561\mathrm{/}65536<1\mathrm{/}9$, one has $(3\mathrm{/}4{)}^{46}<(3\mathrm{/}4{)}^{40}<1\mathrm{/}{9}^5$, and $1128<9^5$; hence $F_2(48)<1$.

Suppose $k\ge 3$ and put $N=3k^2{2}^k$. The $k$th nonnegative term of the exponential series gives $k!\ge (k\mathrm{/}e{)}^k$, so $\left(\genfrac{}{}{0px}{}{N}{k}\right)\le (eN\mathrm{/}k{)}^k$. With [L4], $F_k(N)\le \exp (k(1+\log (N\mathrm{/}k))-(N-k)\mathrm{/}{2}^k)$.

Since $N\mathrm{/}k=3k{2}^k$, [L4] applied at $\log x$ gives $\log x\le x-1$ for $x>0$. Hence the exponent in step 3.4 is at most $k(1+2+(k-1)+k-3k)+k\mathrm{/}{2}^k=k(2-k)+k\mathrm{/}{2}^k<0$, using $\log 3\le 2$, $\log k\le k-1$, and $\log 2\le 1$. Thus $F_k(N)<1$.

Monotonicity from step 3.1, together with the initial bounds in steps 3.2, 3.3, and 4.1, shows $F_k(n)<1$ in every case. Since step 2.1 bounds the failure union by $F_k(n)$, [L3] makes its complement positive; that event is nonempty by [L7].

In the resulting tournament every set of size exactly $k$ has a dominator. Any smaller set extends to a $k$-set because $n\ge k$, and the same dominator works; hence [L1] gives property $S_k$.