Geometric Distribution and Expected Value
When modeling scenarios with repeated independent trials where success occurs with probability $p$, the process follows a geometric distribution. The expected number of trials to achieve the first success is mathematically derived as $1/p$.
Let $E(X)$ denote the expected number of draws required. Using the definition of expectation based on the linearity principle:
$$ E(X) = \sum_{i=1}^{\infty} i \cdot p(1-p)^{i-1} $$
Alternatively, we can formulate an equation directly by considering the outcome of the first trial:
$$ E(X) = p \cdot 1 + (1-p)(1 + E(X)) $$
Solving this yields $E(X) = 1/p$. This approach avoids infinite series summation and is often more efficient in programming contexts.
Application: Recovery Optimization
Consider a scenario where a character recovers over $n$ stages. From stage $i$, one can either wait for natural recovery ($n-i$ days) or attempt a challenge. A successful challenge (probability $p_i$) ends the process, while failure sends the character back to stage $a_i$.
The optimal strategy involves comparing the expected time of waiting versus challenging at each stage. Let $Y_i$ be the expected additional time if challenging at stage $i$. If successful, 0 additional time is needed beyond the current step; otherwise, the system resets partially.
$$ Y_i = p_i \cdot 0 + (1 - p_i)(1 + i - a_i + Y_i) $$
Rearranging terms gives:
$$ Y_i = \frac{(1-p_i)(i - a_i + 1)}{p_i} $$
The total expectation for starting at stage $i$ is $X + Y_i$, where $X$ is the path length to reach $i$. The final answer compares natural recovery against the minimum of these calculated expectations across all stages.
Core Concepts in Discrete Probability
A Random Experiment satisfies three conditions: repeatability under identical conditions, well-defined sample outcomes, and uncertainty of specific results. The set of all possible outcomes constitutes the Sample Space ($\Omega$). Subsets of the sample space are defined as Events.
Independent vs. Mutually Exclusive Events
Two events $A$ and $B$ are independent if $P(A \cap B) = P(A)P(B)$. They are mutually exclusive if they cannot occur simultaneously ($A \cap B = \emptyset$). For mutually exclusive events, probabilities sum: $P(A \cup B) = P(A) + P(B)$. Understanding this distinction is critical when decomposing complex probabilistic spaces.
Random Variables
A random variable $X$ is a function mapping sample points to real numbers. Key properties include:
- Expectation: $E(X) = \sum x \cdot P(X=x)$.
- Linearity: $E(X + Y) = E(X) + E(Y)$, regardless of independence.
- Vector/Higher Dimension: Variables can represent coordinates or multi-dimensional states.
Linearity of Expectation is particularly powerful in competitive programming. It allows us to calculate the expectation of a sum of variables by summing their individual expectations, even when the variables are correlated.
Combinatorial Techniques and Symmetry
When dealing with permutations, symmetry arguments often replace brute-force counting. For instance, calculating the probability that $p_i$ is the maximum in the prefix $p_{1 \sim i}$ relies on the fact that any element within the first $i$ positions has an equal chance of being the maximum.
$$ P(p_i = \max(p_{1 \dots i})) = \frac{1}{i} $$
Similarly, determining the probability of subsequences appearing in random permutations reduces to analyzing relative orderings. For a subsequence of length $k$, the probability of it appearing in a specific relative order is $1/k!$. This holds true whether observing the full array or just the subset of relevant elements.
Adjacency in Deletion Processes
Consider a problem where elements are deleted randomly one by one. The probability that two specific elements $x$ and $y$ become adjacent during the process depends only on the relative ordering of elements between them and themselves. If there are $k$ elements in the range including endpoints, the probability is determined by combinatorial constraints on their positions.
Linearity of Expectation Exercises
The power of linearity becomes evident in problems involving sums of indicators.
Drawing Balls
In a box containing balls numbered $1$ to $n$, if $m$ balls are drawn without replacement, the expected sum of values is:
$$ E = \sum_{j=1}^m E(j\text{-th draw}) = m \times \frac{n+1}{2} $$
This result holds even without replacement because each specific ball position is equally likely to be filled by any number from the set.
Peaks in Permutations
To find the expected number of local maxima (peaks) in a random permutation:
$$ X = \sum_{i=1}^n I_i $$
where $I_i$ is an indicator variable. Boundary conditions apply to the first and last elements, leading to an expectation of $(n+1)/3$. Similarly, counting occurrences of patterns like "01" in binary sequences generated by ball drawings simplifies to summing transition probabilities.
Random Walks and Markov Chains
Fundamentals
A Markov Chain describes a sequence of events where the future state depends only on the current state. The transition matrix defines probabilities between states. In algorithmic contests, these often manifest as linear systems of equations solvable via Gaussian elimination or dynamic programming if the graph is a DAG.
One-Dimensional Walks
For a symmetric walk on a segment $[0, N]$, the probability $f(i)$ of reaching 0 before $N$ satisfies:
$$ f(i) = \frac{1}{2}f(i-1) + \frac{1}{2}f(i+1) $$
With boundary conditions $f(0)=1, f(N)=0$, the solution forms an arithmetic progression yielding $f(i) = 1 - i/N$. The expected time to absorption is quadratic, specifically $i(N-i)$ for simple symmetric walks.
Graph-Based Walks
On directed graphs, if topological order exists, Dynamic Programming suffices. For undirected graphs with cycles, linear equations must be solved.
// Solving for Expected Steps using Gaussian Elimination
int n, m;
cin >> n >> m;
vector<vector<double>> mat(n + 1, vector<double>(n + 1));
for(int i = 1; i < n; ++i) {
int sz = outdegree[i];
mat[i][i] = 1.0;
for(int v : adj[i]) {
mat[i][v] -= 1.0 / sz;
mat[i][n] += 1.0 / sz; // RHS term for 'cost'
}
}
mat[n][n] = 1.0; // Boundary condition
GaussianElimination(mat);
Grid and High-Dimensional Walks
For fixed steps $N$ on a grid, the problem maps to counting paths. A random walk of length $N$ ending at $(x, y)$ requires satisfying parity constraints ($|x| + |y| \le N$ and $(N - (|x| + |y|)) % 2 == 0$). The probability is derived by summing over possible splits of horizontal vs vertical moves, utilizing combinations.
long long prob = 0;
for(int k = 0; k <= N; ++k) {
long long waysX = nCr(k, (k + x)/2);
long long waysY = nCr(N - k, ((N - k) + y)/2);
// Combine counts and normalize by total paths
ans += waysX * waysY;
}
Advanced Transformations
State Space Reduction
Complex games often involve state compression. In problems involving resource synthesis (e.g., crafting items), the state is defined by remaining resources. If choices exist (e.g., different assistants in a game), the value function selects the maximum expected yield between strategies.
$$ f[i] = \max \left( \frac{P}{100}(f[i+B] + 2), \frac{Q}{100}(f[i+B-1] + 1) + \dots \right) $$
Self-loops in expectation equations (e.g., retrying a failed craft) are handled by algebraic rearrangement similar to the geometric distribution derivation.
Probabilistic Analysis
For large-scale games like poker-style all-ins, the winning probability can sometimes be reduced to geometric progressions. If a player needs to double their chips, the probability of success in a single round might be constant, but the cumulative effect leads to a closed-form solution involving logarithmic properties or modular exponentiation.