Randomization Techniques

Overview

Prerequisites: Random functions and Introduction to probability

This article gives a brief classification of randomization techniques related to OI/ICPC and introduces each category. It also introduces some methods that are rarely used in OI/ICPC but are relatively close to OI/ICPC in style and other respects; these are marked with (*) beforehand.

This classification does not represent a broad consensus and certainly cannot cover every possibility, so it is provided for reference only.

Notation and conventions:

• $\mathrm{Pr}[A]$ denotes the probability that event $A$ occurs.
• $\mathrm{E}[X]$ denotes the expectation of random variable $X$.
• The assignment symbol $:=$ introduces a new quantity; for example, $Y:=1926$ introduces a quantity with value $1926$, namely $Y$.

Covering target elements with random sets

There is one or more solution in a huge solution space that we want. We can try casting a net repeatedly; as long as we catch the target solution once, we succeed.

Example: Testing whether a graph is tripartite

For each vertex $v$, independently choose a color from $\{R,G,B\}$, denoted $C_v$, and stipulate that $v$ is not colored $C_v$. The probability that an optimal solution happens to satisfy these restrictions is clearly $\big(\frac 23\big)^n$.

Under these restrictions, for a pair of adjacent vertices $(u,v)$, the requirement that $u,v$ have different colors is equivalent to the following implication:

• For every color other than $C_u,C_v$, denoted $X$, if $u$ is colored $X$, then $v$ is colored $\{R,G,B\}\setminus\{X,C_v\}$.

Thus, for each $v$ we can set a Boolean variable $B_v$, whose value indicates which of the two remaining colors is assigned to $v$. The problem can then be solved with a 2-SAT model in $O(n+m)$ time.

This gives a success probability of $\big(\frac 23\big)^n$ for one run. Run the algorithm $-\big(\frac 32\big)^n\log \epsilon$ times and output a solution if any run succeeds; this guarantees a success probability of $1-\epsilon$. (See the later section on the analysis of probability bounds for details.)

Review: In this problem, the “solution space” is the set $\{R,G,B\}^n$. Each time, we search for the “target solution”—a valid coloring—within a smaller range by imposing random restrictions.

Example: CodeChef SELEDGE

Observation: if three selected edges form a path, deleting the middle edge is never worse; if several selected edges form a cycle, deleting any one of them is never worse.

Corollary: the edge set selected by an optimal solution must form several vertex-disjoint stars (that is, trees of diameter at most two).

Corollary: the edge set selected by an optimal solution must form a bipartite graph.

Independently color every vertex black or white with equal probability, and require this coloring to be exactly the black-and-white coloring of the bipartite graph corresponding to the optimal solution.

Let us calculate the probability that the optimal solution satisfies this requirement:

• Consider a star with $n$ vertices. It clearly has two coloring schemes, so the probability that it receives the correct colors is $\dfrac 2{2^n}=2^{1-n}$.
• Suppose the numbers of vertices in the stars of the optimal solution are $a_1,\cdots,a_l$. Then $(a_1-1)+\cdots+(a_l-1)\leq K$, where $K$ is the maximum number of edges that can be selected.
• Therefore, the probability that all stars receive the correct colors is $2^{1-a_1}\cdots 2^{1-a_l}\geq 2^{-K}$.

Under these restrictions, try to build a min-cost flow model to calculate the optimal answer:

• Build a bipartite graph, with white vertices on the left connected to $S$ and black vertices on the right connected to $T$.
  • For a white vertex $v$, add an edge from $S$ to it with capacity 1 and cost $-A_v$, and an edge with capacity $\infty$ and cost 0.
  • For a black vertex $v$, add an edge from it to $T$ with capacity 1 and cost $-A_v$, and an edge with capacity $\infty$ and cost 0.
• For an edge $(u,v,B)$ in the original graph with $u$ white and $v$ black, add an edge from $u$ to $v$ with capacity 1 and cost $B$.
• Restrict the flow in this graph to be at most $K$; the opposite of the minimum cost is then the answer.

If we solve this with min-cost flow using SPFA, the complexity is $O\big(K^2(n+m)\big)$. Proof:

• First, the number of SPFA runs is clearly $\leq K$.
• Then, during one SPFA run, any vertex is enqueued at most $O(K)$ times. This is because:
  • At any moment there are at most $3K$ edges carrying flow; otherwise, more than $K$ edges would have been selected in the original graph.
  • For any augmenting path of length $L$, at least $\dfrac L2-2$ edges are reverse edges of some edge carrying flow, because all forward edges point from the left side of the graph to the right side, and only these reverse edges can point from right to left.
  • Combining the two facts, the length of any augmenting path is at most $6K+4$.
• Therefore, the complexity is $O\big(K^2(n+m)\big)$.

As in the previous problem, we need to repeat the entire process $-2^K \log\epsilon$ times to obtain a success probability of $1-\epsilon$. The total complexity is $O\big(2^KK^2(n+m)\cdot -\log\epsilon\big)$.

Hitting a target set with random elements

We need to determine an arbitrary element of a set, so we randomly select elements in the hope of hitting this set exactly.

Example: Gym 101550I

The entire graph can be decomposed into a cycle and four chains extending from the cycle. For any one of these four chains, denoted $C$, a greedy algorithm can easily find a placement of wiretaps on the chain satisfying the following conditions:

• Under the condition that all calls entirely within $C$ are intercepted, use the fewest possible wiretaps.
• Under the previous condition, make the minimum distance from the wiretaps on $C$ to the cycle as small as possible.
  • The purpose of this requirement is to intercept as many calls as possible with exactly one endpoint inside $C$.

Next consider the four edges where the chains meet the cycle. We can brute-force whether to place a wiretap on each of these edges. Clearly, if we want to intercept calls crossing between a chain and the cycle, placing a wiretap on one of these four edges is optimal. We can now divide the call paths into the following types:

1. Call paths entirely on a chain. These paths have already been intercepted, so they can be ignored.
2. Call paths crossing between a chain and the cycle that have already been intercepted. They can be ignored.
3. Call paths crossing between a chain and the cycle that have not been intercepted. We can cut off their chain portions directly (because the wiretap placement on the chains is fixed) and retain only their cycle portions.
4. Call paths entirely on the cycle.

The problem has now been reduced to a problem on the cycle.

Suppose the optimal solution places wiretaps on the edge set $S$. If we have identified any element of $S$, say $e$, we can:

• First break the cycle at $e$ to form a chain.
• Then start at $e$ and proceed greedily, repeatedly finding the next edge on which to place a wiretap. With suitable preprocessing, each greedy step can be performed in $O(1)$ time.
• Thus solve the problem in $O(|S|)$ time.

We randomly choose an edge $e'$ on the cycle, stipulate that $e'\in S$, and then perform the process above, repeating it several times and taking the best result.

Analyze the complexity of one run:

• Observation: let $S'$ denote the optimal solution among all solutions that select $e'$. Then $|S'|\leq |S|+1$.
• Therefore, the complexity of one run is $O(|S'|)=O(|S|)$.

Analyze the success probability:

• Clearly, the success probability of one run is $\dfrac {|S|}n$, where $n$ is the length of the cycle.
• Therefore, we need to repeat the process $-\dfrac n{|S|}\log\epsilon$ times to obtain a success probability of $1-\epsilon$.

In conclusion, the complexity of the algorithm is $O\big(|S|\cdot -\dfrac n{|S|}\log\epsilon\big)=O(-n\log\epsilon)$.

Example: CSES 1685 New Flight Routes

First condense the original graph into strongly connected components. Our goal is clearly to make every sink reachable from every source.

It is not difficult to prove that we only need to add edges from sinks to sources, because any other added edge can be replaced by an edge from a sink to a source that is no worse.

One core operation is to take a sink $t$ and a source $s$ (they need not belong to the same weakly connected component), and add an edge $t\to s$ to make both $s$ and $t$ cease to be sinks or sources (call this Goal I). Ideally, each operation reduces the number of sinks and sources by one. We continue until only one sink or only one source remains, which is a trivial case. Thus we conjecture that the answer is the larger of the number of sources and the number of sinks.

It is not difficult to see that the necessary and sufficient condition for the operation above to achieve Goal I is that $t$ has a predecessor other than $s$, and $s$ has a successor other than $t$. It can be proved (as we will show shortly) that every DAG with at least two sources and at least two sinks contains such an $(s,t)$, but this existence result does not help us construct a solution; further analysis is needed.

• Even with this necessary and sufficient condition, it is difficult to obtain an algorithm directly, mainly because adding the edge $t\to s$ may affect the validity of other pairs $(s',t')$, which is difficult to handle.

We know little about the relationships between sources and sinks (we may not even be able to quickly query whether a pair $s-t$ is reachable without DFS + bitset preprocessing, which the time limit does not allow). This suggests that we need some very general and powerful property.

Observation: pairs $(s,t)$ that do not satisfy Goal I number at most $n+m-1$, where $n$ is the number of sources and $m$ is the number of sinks.

• Reason: if each such $(s,t)$ is viewed as an edge joining $s,t$, all these edges form a graph consisting of several vertex-disjoint paths, so the number of edges is no more than the number of vertices minus one.
• The motivation for this observation is that, to apply an existence result in an algorithm, a qualitative conclusion often first needs to be strengthened into a quantitative one.

Corollary: if $(s,t)$ is chosen uniformly at random, the probability that it satisfies the preceding requirement is at least $\geq \dfrac {(n-1)(m-1)}{nm}$.

• Notice that this conclusion is strictly stronger than the existence result given earlier.

Corollary: choose $\dfrac {\min(n,m)}2$ pairs $(s,t)$ without common elements independently and uniformly at random, and perform the corresponding operations in order (that is, add the edges $t\to s$). Then the probability that all these operations satisfy Goal I is at least $\geq \dfrac 14$.

• Reason:

After selecting $k$ pairs $(s,t)$ consecutively, it is easy to check whether they all satisfy Goal I: run strongly connected component condensation once more and check whether $n,m$ have both decreased by $k$. If each round reduces $k=\dfrac{\min(n,m)}2$, then $\min(n,m)$ must become 1 within $O\big(\log(n+m)\big)$ rounds, reducing the problem to the trivial case.

while(n>1 and m>1):
    randomly choose k=min(n,m)/2 pairs (s,t)
    add edge t->s for all these pairs
    if new_n>n-k or new_m>m-k:
        roll_back()
solve_trivial()

The complexity is $O\big((|V|+|E|) \log |V|\big)$.

Review: We need to determine any pair $(s,t)$ that can achieve Goal I, so we randomly choose $(s,t)$.

Using randomization to obtain properties of random data

If the data of a problem is generated randomly, we may be able to use properties of random data to solve it. In some cases, even if the data is not randomly generated, we can use randomization to give it some characteristics of random data, thereby helping to solve the problem.

Example: Randomized incremental method

A randomly generated sequence of elements may have properties such as a small expected number of changes in the prefix optimum, and the randomized incremental method obtains such properties by randomly shuffling the input sequence.

See randomized incremental method for details.

Example: randomized solution for TopCoder MagicMolecule

A meet-in-the-middle search is natural. Split the vertex set evenly into two halves $V_L,V_R$, both of size $\dfrac n2$. Compute an array $f_{L,k}$ giving the maximum total weight of all cliques in the vertex set $L\subseteq V_L$ having size $\geq k$. Then enumerate every clique $C_R$ in the right half, find the vertices in the left half adjacent to every vertex in $C_R$ (call this vertex set $N_L$), and update the answer with $f_{N_L,\frac 23 n-|C_R|}+\textit{value}(C_R)$.

• Notice that an $O(1)$-time transition is possible for every $f_{L,k}$. Specifically, choose an arbitrary element $d$ of $L$ and consider cases:
  • If $d$ is not in the optimal clique, transition from $f_{L\setminus \{d\},k}$.
  • If $d$ is in the optimal clique, transition from $f_{L\cap N(d),k}+\textit{value}(d)$, where $N(d)$ denotes the set of neighbors of $d$.
  • Do not forget to use $f_{L,k+1}$ to update $f_{L,k}$.

This solution is too slow. Try to optimize it:

• Split the vertex set uniformly at random. Then, with appreciable probability, the vertex set $C_{res}$ of the optimal solution is also split exactly evenly, namely $|C_{res}\cap V_L|=|C_{res}\cap V_R|$.
  • Of course, $|C_{res}|$ may be odd. For simplicity, assume it is even here; the odd case does not fundamentally change the solution.
  • Experiments show that about 20 random trials give a high probability of satisfying this property at least once. In other words, if our algorithm relies on $C_{res}$ being split evenly, repeating the algorithm 20 times and taking the best result likewise gives a high probability of obtaining the correct answer.
• With this property, we can stipulate directly that the left clique $L$ and right clique $C_R$ both have size $\geq \dfrac n3$. This improves the complexity in two ways:
  • $f$ no longer needs to record the size dimension.
  • Since we only need to consider cliques of size $\geq \dfrac n3$, the number of left cliques $L$ and right cliques $C_R$ to consider is greatly reduced, to about $1.8\cdot 10^6$.
• The bottleneck now becomes finding the weight sum of a particular subset on one side, because this requires $O\big(2^{|V_L|}+2^{|V_R|}\big)$ preprocessing.
  • Solution: split $V_L,V_R$ in half again. When querying the weight sum of a subset, split that subset into two halves, query each half, and add the answers.
• This is enough to solve the problem.

Review: A random set has the property that the sizes of the two parts into which it is split do not differ too greatly, and we obtain this property by randomly splitting the set.

Randomization for hashing

Example: UOJ #207 Covalent Grandpa Visits Changsha

For every edge $e$ in the graph, define $S_e$ as the set of important paths passing through that edge (that is, the $(a,b)$ pairs in the problem). Consider dynamically maintaining the hash value of each set $S_e$. Then it is easy to determine whether $S_e$ equals the universal set, that is, whether $e$ is an “unavoidable path”.

To hash the sets, assign each $(a,b)$ a random nonnegative integer less than $2^{64}$, denoted $H_{(a,b)}$. The hash value of a set is the XOR of the $H$ values of its elements.

Then the hash value of any fixed set is uniformly distributed over $R:=\left\{0,1,\cdots,2^{64}-1\right\}$ (in other words, the hash value ranges over $R$ and every value has the same probability). This is because:

1. A single $H_{(a,b)}$ is clearly uniformly distributed.
2. The XOR of two independent random variables that are both uniformly distributed over $R$ is also uniformly distributed over $R$. This is not difficult to prove.

Thus the correctness probability of the algorithm is guaranteed.

As for maintaining this hash value, an LCT suffices.

Example: CodeChef PANIC and analysis of its error rate

The rough solution to this problem is:

1. It can be proved¹ that $S(N)$, with respect to $N$, satisfies an $O(K)$-order linear recurrence.
2. Use the BM algorithm to find this recurrence.
3. Use the recurrence and the Cayley–Hamilton theorem to calculate $S(N)$.

Here we focus only on the second part, namely how to find a recurrence for a sequence of matrices. Thus we only need to consider the following problem:

If a sequence of matrices satisfies a recurrence $F$, then each of its entries also satisfies $F$. However, if we find a shortest recurrence $F'$ for one entry, $F'$ may be shorter than $F$, causing a problem.

Solution: assign each matrix entry $(i,j)$ a $ [!note]+ Brief problem statement

Given two directed graphs $G_0,G_1$ whose edge labels are lowercase letters, compute for each graph the multiset of strings corresponding to all paths (possibly an infinite multiset), and determine whether the two multisets are equal. If they are not equal, output a shortest string whose occurrence counts in the two multisets differ.

Let $f_{K,i,j}$ denote the hash value of the multiset of all strings corresponding to paths in graph $G_K$ that start at vertex $i$ and have length $j$. Consider every state in increasing order of $j$; when transitioning, enumerate the outgoing edges of $i$ and stipulate that the chosen edge is the first edge of the path.

To determine whether a bad string of length $=L$ exists, it suffices to integrate and compare $\{f_{0,*,L}\}$ and $\{f_{1,*,L}\}$ separately (the wildcard * here denotes every vertex; for example, $\{f_{0,*,L}\}$ denotes the set of all $f_{0,i,L}$ as $i$ ranges over every vertex). The official solution² proves that the shortest bad string, if one exists, has length at most $n_1+n_2$, so the complexity of this method is reliable.

Next consider the specific hash method. The usual method—mapping a string $a_1a_2\cdots a_k$ to $\big(a_1+Pa_2+P^2a_3+\cdots+P^{k-1}a_k\big)\bmod Q$, and defining the hash of a multiset as the sum of the hashes of its elements modulo $Q$—does not work here. For example, the sets {"ab","cd"} and {"cb","ad"} have the same hash value regardless of how $P,Q$ are chosen.

The problem with the method above is that the hash value of a string is a sum, so its terms can be separated and rearranged. To avoid this problem, we consider changing the hash value into a product. In addition, the commutativity of multiplication makes different positions indistinguishable, so we assign different weights to different positions to avoid this.

For every pair $(c,j)$, where $c$ is a character and $j$ is an integer indicating the position of $c$ in a string, we pre-generate a random number $x_{c,j}$. We map a string $a_1a_2\cdots a_k$ to $x_{a_1,1}x_{a_2,2}\cdots x_{a_k,k}\bmod Q$, where $Q$ is a randomly chosen prime, and define the hash of a multiset as the sum of the hashes of its elements modulo $Q$. We now analyze the error rate.

Let $F$ be the field corresponding to the residue classes modulo $Q$. For an $L\leq n_1+n_2$, $\sum\limits_i f_{0,i,L}$ and $\sum\limits_i f_{1,i,L}$ correspond respectively to polynomials over $F$ in the variable set $\{x_{*,*}\}$ of degree $L$. Denote these two polynomials by $P_0,P_1$.

If two different string multisets have the same hash value, there are two possibilities:

1. $P_0\equiv P_1\pmod {Q}$; that is, the coefficients of every term of $P_0,P_1$ are equal modulo $Q$.
2. $P_0\not\equiv P_1\pmod {Q}, P_0(x_{*,*})\equiv P_1(x_{*,*})\pmod {Q}$; that is, $P_0,P_1$ are not identically equal, but the selected $\{x_{*,*}\}$ happen to make their values at this point equal.

Analyze the probability of the first case:

• Observation: for any $A\neq B; A,B\leq N$ and a randomly selected prime $Q\leq Q_{\max}$, we have:

• This is because $A\equiv B$ can hold only when $Q$ satisfies $Q\big|(A-B)$, and such $Q$ are counted by $\omega(A-B)\leq \log_2 N$. By the prime number theorem, the number of distinct primes no greater than $Q_{\max}$ is $\Theta\Big(\dfrac {Q_{\max}}{\log Q_{\max}}\Big)$. Dividing the former count by the latter gives the formula above.
• In the observation above, take $A,B$ with $A\neq B$ to be the coefficients of a particular term in $P_0,P_1$ (which are also the occurrence counts of the corresponding string in $G_0,G_1$). Clearly $A,B\leq (m_1+m_2)^{L}$, so we obtain:

• Therefore, taking $Q_{\max}\approx 10^{12}$ is more than sufficient. If the machine cannot support integer operations on numbers this large, double hashing can be used instead.

Analyze the probability of the second case:

• In the Schwartz–Zippel lemma:
  • take the field $F$ corresponding to the residue classes modulo $Q$;
  • take $f(x_{*,*})=P_0(x_{*,*})-P_1(x_{*,*})$ to be a nonzero degree-$L$ polynomial;
  • take $S=F$.
• We obtain that the desired probability is $\leq \dfrac LQ$.

Notice that we need to guarantee correctness for every $L$, so for a rigorous argument we also need to use the Union Bound (see below) to explain this.

In practice, we do not need to choose the modulus randomly because—for example—using our birthday as the modulus is already equivalent to using a random number.

Example: (*) number of distinct elements in a submatrix

Lemma: let $X_{1\cdots k}$ be mutually independent random variables uniformly distributed in $[0,1]$. Then $\mathrm{E}\big[\min\limits_i X_i\big]=\dfrac 1{k+1}$.

• Proof: consider a unit circle with $k+1$ points distributed uniformly at random by relative position, at positions $0,X_1,X_2,\cdots,X_k$. Then $\min\limits_i X_i$ is the length of one particular segment among the $k+1$ gaps. Since these gaps are “symmetric”, the expected length of any particular gap is $\dfrac 1{k+1}$.

Take $k$ to be the number of distinct elements and use the lemma above to infer, from $\min\limits_i X_i$, the number $k$.

Consider a hash function that maps every matrix element independently and uniformly to a real number in $[0,1]$, with equal elements mapped to equal real numbers. Then the real numbers corresponding to all elements of a submatrix, after deduplication, form an instance of the preceding set $\{X_1,\cdots,X_k\}$, where $k$ equals the number of distinct elements in the submatrix.

Thus we obtain the algorithm:

1. Assign a hash value in $[0,1]$ to every matrix element. To ensure randomness, the hash function can be implemented directly with map and a random-number generator: whenever a new value is encountered, assign it a random hash value.
2. When answering a query, find the minimum hash value $M$ in the submatrix and output $\dfrac 1M-1$.

However, this algorithm is not satisfactory. Its output has expectation $\mathrm{E}\Big[\dfrac 1{\min\limits_i X_i}-1\Big]$, but in fact this is not equal to $\dfrac 1{\mathrm{E}\big[\min\limits_i X_i\big]}-1=k$; it is instead (as can be proved) equal to $\infty$.

In other words, we cannot put a single value of $\min\limits_i X_i$ directly in the denominator. We must first compute its expectation and then put the expected value in the denominator.

How do we compute the expected value? Take the average of multiple random samples.

Use $C$ different hash functions to perform the preceding process separately. When answering a query, compute $C$ different values of $M$, take their average $\overline M$, and output $\big(\overline M\big)^{-1}-1$.

Experiments show that taking $C\approx 80$ is sufficient. A rigorous proof is very tedious and is omitted here.

Finally, how do we find the minimum of a submatrix? Use a two-dimensional S-T table: preprocess in $O(nm\log n\log m)$ time and answer each query in $O(1)$.

Other applications of randomization in algorithms

Other uses of randomization include:

• Preventing the data setter from defeating the algorithm with targeted data, for example by randomly shuffling the order of neighbors during a search.
• Ensuring that the operations performed during the algorithm are uniform in some sense, for example in the simulated annealing algorithm.

In these situations, randomization is often, though not always, associated with ad hoc methods and attempts to obtain points.

Example: TJOI2015 Linear Algebra

The standard algorithm for this problem is network flow, but here we use the following ad hoc method:

• Randomly choose a position each time, flip the value at that position, check the value, and update the answer.

#include <algorithm>
#include <cstdlib>
#include <iostream>

int n;

int a[510], b[510], c[510][510], d[510];
int p[510], q[510];

int maxans = 0;

void check() {
  memset(d, 0, sizeof d);
  int nowans = 0;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) d[i] += a[j] * c[i][j];
  for (int i = 1; i <= n; i++) nowans += (d[i] - b[i]) * a[i];
  maxans = std::max(maxans, nowans);
}

int main() {
  srand(19260817);
  std::cin >> n;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) std::cin >> c[i][j];
  for (int i = 1; i <= n; i++) std::cin >> b[i];
  for (int i = 1; i <= n; i++) a[i] = 1;
  check();
  for (int T = 1000; T; T--) {
    int tmp = rand() % n + 1;
    a[tmp] ^= 1;
    check();
  }
  std::cout << maxans << '\n';
}

Example: (*) randomized heap³

The most common way to implement a mergeable heap is probably a leftist tree, which maintains the tree height and keeps the tree left-biased to guarantee merge complexity. However, maintaining the height is somewhat cumbersome, so we would like to avoid it as much as possible.

Thus we can consider using a randomized heap, which swaps children randomly instead of comparing their heights.

struct Node {
  int child[2];
  long long val;
} nd[100010];

int root[100010];

int merge(int u, int v) {
  if (!(u && v)) return u | v;
  int x = rand() & 1, p = nd[u].val > nd[v].val ? u : v;
  nd[p].child[x] = merge(nd[p].child[x], u + v - p);
  return p;
}

void pop(int &now) { now = merge(nd[now].child[0], nd[now].child[1]); }

A randomized heap has no hard or soft requirements on its shape, and the expected complexity of merging any two heaps, as arguments to the merge function, satisfies the same bound. We prove this below.

Proof techniques involving randomness

The following are several useful techniques.

Naturally, these few items cannot be exhaustive. If you know of a technique that is not listed, please feel free to add it.

Analysis of probability bounds

See the page on probability inequalities for details.

In addition to the inequalities mentioned on that page, the following conclusion is also frequently used in derivations:

Using the natural constant: $\Big(1-\dfrac{1}{n}\Big)^n\leq \dfrac{1}{\mathrm{e}},\forall n\geq1$

• The left-hand side is monotonically increasing with respect to $n\geq 1$ and its limit at $+\infty$ is $\dfrac{1}{\mathrm{e}}$, which proves the conclusion.
• This tells us that if $n$ mutually independent events each occur with probability $1-\dfrac 1n$, then the probability that they all occur is at most $\dfrac{1}{\mathrm{e}}$.

The coupling idea

The coupling idea is often used to handle more than one random object at the same time, or to handle a random object and a deterministic object simultaneously.

Prelude: connectivity of random graphs

This conclusion looks completely natural, but a rigorous proof is not quite so easy.

The idea used in this proof is called “coupling”, which can be understood from its literal meaning. Here it consists of combining two originally independent random processes into one.

Application: NERC 2019 Problem G: Game Relics

Observation: if we choose to draw items, we will certainly keep drawing until we obtain a new item.

• Reason: if a draw does not produce a new item, the state is exactly the same as before the draw. Therefore, if the optimal action in the old state is to draw once, the optimal action in the new state must also be to draw once more.

We can define $f_k$ as the expected amount of money needed to draw a new item when we currently own $k$ different items. By the observation above, we can treat $f_k$ directly as a fixed cost, turning the process into one in which we pay $f_k$ each time to obtain a new item at random.

Conclusion: the optimal strategy is always to draw several times first and then buy all items that were not drawn.

This conclusion agrees with intuition, because $f_k$ increases with $k$, so drawing early does indeed seem somewhat better than drawing late.

Based on this conclusion, we can equivalently transform the problem again: replace the operation “choose an item and buy it for its price” with “randomly choose an item not yet owned and buy it for its price”. The operations are equivalent because, if buying is only used to clean up at the end, it does not matter which item is chosen.

We now see that drawing and buying have effectively become the same operation; the only difference is the price paid. Choosing to buy or draw has no effect on the order in which items are obtained, and every order of obtaining the items is equally likely.

Observation: at a given moment, we should choose to buy if and only if the cost of the next draw, determined by the number of items already drawn, is greater than the average price of the remaining items; if they are equal, either choice is acceptable.

• It can be proved that, over time, the draw cost increases no more slowly than the average price of the remaining items. This shows that there is only one “threshold point” at which we switch from drawing to buying, further confirming the previous conclusion.

Finally, enumerate all possible states, that is, the sets of items already owned. Calculate the probability of reaching each state, given by the number of permutations of the owned items divided by the total number of permutations, multiply it by the cost of the optimal decision in the current state, determined by the number of owned items and the total price of the remaining items, and add everything together. This process can be optimized with knapsack-style DP, which solves the problem.

Review: The coupling technique is used twice in this problem. The first time is in the proof, where the two random processes use the same random source. The second time is in transforming buying into random buying, that is, introducing a random source so that buying and drawing become essentially the same operation by having them share a random source.

References