Try
Twelve labeled components form six designated pairs: A₁/A₂, B₁/B₂, through F₁/F₂. Choose an unordered set of four components uniformly. Let X count designated pairs whose two components are both selected. A set containing A₁,A₂,B₁,C₂ has X=1; a set containing A₁,A₂,B₁,B₂ has X=2.
List one outcome with X=0. Can X be three? It cannot: three complete disjoint pairs require six items. The possible counts are therefore 0,1,2. The components and sampling mechanism are synthetic, chosen to make every outcome countable by hand; no manufacturing claim is being inferred.
Predict
Predict whether completing pair A makes completing pair B more likely or less likely. Four selected slots must serve all six pairs. Events that concern different labels can still be dependent because selection uses the same limited slots.
Also predict whether dependence prevents adding expectations. It does not. An indicator I_A is one if A is complete and zero otherwise. The total X is the sum of six indicators. We will add their expected values, but we will not multiply their probabilities without checking independence.
Experiment
There are C(12,4)=495 equally likely four-element subsets. C(n,k) means the number of unordered choices of k items from n. If we instead draw four items in order without replacement, every resulting subset has exactly 4! orders, so forgetting order still gives this uniform distribution.
Complete the following count table before reading the arithmetic. In the zero-pair row, choose four pair labels and then one member of each. In the one-pair row, choose the complete pair, two other pair labels and one member from each of those.
| X | Construction of the selected set | Number of subsets | Probability |
|---|
| 0 | Four different pairs, one member each | C(6,4)·2⁴=240 | 16/33 |
|---|
| 1 | One complete pair, two single members from distinct other pairs | 6·C(5,2)·2²=240 | 16/33 |
|---|
| 2 | Two complete pairs | C(6,2)=15 | 1/33 |
|---|
The counts sum to 495. Explain why the one-pair construction neither misses nor repeats an outcome. Its complete pair is uniquely identified; the remaining two members must come from distinct other pairs. Changing the sampling mechanism can invalidate this table. For example, first choosing a complete pair guarantees X≥1 and cannot produce a uniform four-subset.
As a paper experiment, hide the probability column and reconstruct it. Then change the sample size to three. Identify the new possible values of X before attempting any formula.
Understand
Expectation on a finite sample space is a weighted average: E[X]=Σω p(ω)X(ω), where ω ranges over outcomes and their probabilities sum to one. An indicator has expectation equal to its event probability, since its only nonzero contribution is one on that event.
For pair A, selecting its two fixed members leaves two places chosen from the other ten items. Thus P(I_A=1)=C(10,2)/495=45/495=1/11. Every designated pair has the same marginal probability. Expanding the finite sums gives E[Σ I_i]=Σ E[I_i]: interchange the outcome sum and the six-item sum. No product probability and no independence assumption appears. Consequently E[X]=6/11. The distribution table independently gives 0·16/33+1·16/33+2·1/33=18/33=6/11. An expectation need not be a possible integer outcome.
For two distinct designated pairs A and B, completing both forces exactly their four components. The joint probability is 1/495. This differs from the product (1/11)², so the indicators are not independent. Given A is complete, the remaining two selected items form a uniform pair from ten; only one of those 45 choices is B. Therefore P(I_B=1 given I_A=1)=1/45, smaller than its unconditional 1/11. The conditional probability and the joint calculation tell the same story.
Now prove a tail bound without deriving the entire distribution. At every outcome, X≥2 times the indicator of X≥2. Multiplying each inequality by its nonnegative outcome probability and adding yields E[X]≥2P(X≥2). Hence P(X≥2)≤3/11. This is a first-moment bound: it uses the expected count and nonnegativity. It remains valid despite dependence, but it is much larger than the exact 1/33 in the table.
Apply
Improve the bound by counting pairs of completed pairs. Define Y=Σ over i<j of I_i I_j. If X pairs are complete, there are C(X,2) ways to choose two of them, so Y=C(X,2). Whenever X≥2, Y≥1. The same pointwise argument gives P(X≥2)≤E[Y]. There are 15 unordered choices of designated pair labels, each jointly complete with probability 1/495. Thus E[Y]=15/495=1/33.
Here the improved bound is exact: X can only be 0,1,2, so Y equals the indicator of X≥2. In another experiment X might exceed two; then Y can exceed one and the inequality can be strict. A factorial-moment bound is not automatically better than a first-moment bound. Always compute and interpret both rather than treating the second formula as a universal upgrade.
Try the changed case of five selected items from the same twelve. A specified complete pair now has probability 5·4/(12·11), while two specified complete pairs leave one free choice among eight items. Explain why X still cannot exceed two and why counting two completed pairs still gives the exact tail. The practice asks you to supply the full arithmetic and an independent direct count.
For a different transfer, independently assign cards to trays and count empty trays. The individual assignments may be independent while the empty-tray events are dependent. Define the elementary outcomes first; “independent experiment” is not a license to multiply every derived event probability.
Continue
Keep four items in your evidence: the sample space and weights, an indicator definition, a joint-event check, and a pointwise inequality justifying the tail bound. An exact distribution is a useful independent check, but it is not always necessary to prove a bound. Finite enumeration verifies this small model, not a different sampling policy or a real process whose probabilities have not been established.
For targeted review use unordered selections and linearity in the probabilistic method. These finite arguments need sums, fractions and counting, not calculus or completion of the entire probability course. Written solutions still require review; matching a fraction alone does not demonstrate the modeling and proof steps.
Choose a focused return, then bring back a proof
Open only the group you need. These links reuse existing explanations and specific practice tasks; you do not need to complete their surrounding courses. Read the short preparation below, attempt a linked task before opening its worked solution, and record the assumptions and evidence you would use in your current argument.
Matching, Hall’s condition and König certificates
Preparation: A bipartite graph separates vertices into left and right parts, with edges only between parts. A matching uses no vertex twice. For a left subset S, its neighbor set N(S) contains all right vertices adjacent to at least one member. A vertex cover meets every edge.
Hall’s condition checks every left subset: its neighbors must number at least as many as its members. Checking individual degrees is insufficient. A matching and a vertex cover of the same size certify optimality, because disjoint matching edges require distinct covering vertices.
Bring back: either an explicit deficient subset with fewer neighbors, or a matching and equal-size cover. Explain why the displayed objects are valid certificates; a claimed matching size alone is not the proof.
Partial orders, chains and Dilworth’s theorem
Preparation: A partial order is reflexive, antisymmetric and transitive. Distinct elements may be incomparable. A chain has every pair comparable; an antichain has no distinct comparable pair. A chain partition uses each element once.
For the split graph, make left and right copies of each element and join a left copy to a right copy when the first is strictly smaller. Selected matching edges become directed paths: strict order rules out cycles. A chain partition needs at least as many chains as any antichain has elements.
Bring back: a chain partition and an antichain of the same size, checking comparability and coverage element by element. Explain the lower bound that makes their equal sizes an optimality certificate.
Planarity: necessary bounds and actual obstructions
Preparation: A planar graph admits a drawing without edge crossings except at shared endpoints. In a connected plane drawing, n−m+f=2 counts vertices, edges and faces, including the unbounded face. “Simple” excludes loops and parallel edges.
For simple planar graphs with n≥3, m≤3n−6; if also bipartite, m≤2n−4. These are necessary bounds, not complete tests. Do not apply them without their hypotheses or conclude planarity merely because one inequality holds.
Bring back: the vertex and edge counts, the relevant graph assumptions, and a violated necessary bound when available. If no bound is violated, report that this test is inconclusive; a planar drawing would supply different evidence.
RSA correctness for all residue classes
Preparation: Work modulo n=pq with distinct primes p and q and positive exponents e,d satisfying ed≡1 modulo lcm(p−1,q−1). Congruence means the difference is divisible by the modulus. The Chinese remainder theorem combines agreement modulo p and modulo q into agreement modulo pq.
A message need not be relatively prime to n. For each prime separately, its residue is either zero, whose positive powers remain zero, or nonzero, where Fermat’s theorem applies. This case split extends decryption correctness to every residue; using Euler’s theorem only on units would leave a gap.
Bring back: the zero/nonzero cases for both primes and the final CRT step. State separately what the arithmetic proves: toy decryption correctness does not establish secure encryption.
Finite probability: counting, indicators and Markov’s bound
Preparation: State a finite sample space and its probabilities, which are nonnegative and sum to one. Counting favorable outcomes divided by total outcomes is valid only when those outcomes are equally likely. An indicator is 1 when its event happens and 0 otherwise; its expectation is that event’s probability.
Finite linearity of expectation needs no independence. Independence may still be needed to multiply probabilities when calculating a particular indicator’s expectation. For a nonnegative random variable X and positive t, Markov gives P(X≥t)≤E(X)/t; a bound exceeding one can be replaced by one.
Bring back: your sample space, an indicator sum, the marginal probabilities and a justified tail or existence conclusion. Name exactly where independence enters and distinguish a probability bound from an exact probability.
These are selected preparation and proof opportunities. Following links or recording answers does not establish mastery, independent review or equivalence to a full discrete-mathematics course.
