Prove that a good configuration exists by randomising it. A four-vertex cut separates an expectation bound, an actual construction and the true optimum.
Probabilistic method
The probabilistic method proves that an object with a desired property exists by placing a probability distribution over candidate objects and showing that success has positive probability. For a quant developer studying a partitioning or allocation problem, this can establish a feasible performance benchmark before a search algorithm finds a particular solution. The randomness belongs to the proof; the object it proves exists can be entirely deterministic. Carnegie Mellon’s introduction gives this general construction.
A random partition certifies a bound
Take a fixed, finite, undirected graph with no self-loops and m edges. A cut divides its vertices into two groups and counts edges whose endpoints lie in different groups. Assign each vertex independently to group A or B, with equal probability.
For edge e, let Ie be the indicator that it crosses the partition. Its endpoints have different assignments with probability 1/2. If C counts crossing edges, linearity of expected value gives
C=e∑Ie,E[C]=e∑E[Ie]=2m.
Some cut must therefore have at least m/2 crossing edges: on this finite sample space, the largest value cannot be below the average. For odd m, the integer cut size is at least ⌈m/2⌉. This is the standard random-cut existence proof, applied to a graph fixed in advance.
Vertex assignments are independent in this construction. The edge indicators need not be mutually independent, and linearity does not require them to be. Do not replace the distribution of C with a binomial distribution merely because every edge has crossing probability 1/2.
Six edges: the guarantee is three, the optimum is four
In the complete graph on four labelled vertices, K4, every pair shares an edge, giving six edges. There are 24=16 equally likely assignments to labelled groups A and B. Exact enumeration gives:
Crossing edges C
Assignments
Probability
0
2
2/16
3
8
8/16
4
6
6/16
The average is (0⋅2+3⋅8+4⋅6)/16=3. Thus some partition cuts at least three edges. A two-versus-two split cuts four: each of the two vertices on one side connects to both on the other. More generally, a split of sizes k and 4−k cuts k(4−k) edges, whose maximum is four.
For 16 equally likely labelled assignments of four vertices, cut sizes 0, 3 and 4 occur 2, 8 and 6 times. The mean is 3, but a two-versus-two partition attains the maximum of 4 crossing edges out of 6.
Exact enumeration, not simulation. Swapping the names of the two groups counts as a different labelled assignment but leaves the cut unchanged.
Three claims are distinct: the averaging argument proves a cut of size at least three exists; displaying a two-versus-two split constructs a cut of size four; checking all possible split sizes proves four is optimal. The first claim alone establishes neither of the other two.
Turning the proof into a construction
Here, conditional expectation removes the need to keep flipping coins. After fixing some vertices, imagine the remaining assignments are still independent fair choices. The current expected cut size is the average of the two conditional means obtained by assigning the next vertex to A or B. At least one choice preserves or increases that mean. Choose it and continue. Once every vertex is fixed, the conditional mean is the actual cut size. This is the method of conditional expectations.
For K4, process vertices 1 through 4 and choose A on a tie. The groups become A, B, A, B; the conditional means, including the initial mean, are
3⟶3⟶3.5⟶3.5⟶4.
Each conditional mean is easy to compute: count already fixed crossing edges, then add half the number of edges with at least one unassigned endpoint. Already fixed within-group edges contribute zero. This construction preserves the half-the-edges guarantee on any such graph; attaining the optimum on K4 does not make it an exact maximum-cut algorithm in general.
The broader probabilistic method need not yield an efficient construction: a successful event may be very rare, or the conditional quantities may be hard to compute. Nor does a random partition of a toy graph establish independent asset returns or portfolio diversification. Those require a financial model connecting the graph and its objective to the actual decision.
