Try
Toss two fair coins in order. Declare HH a success, HT a failure, and either TH or TT a restart. A restart means toss a new pair of independent fair coins; it does not reuse either old coin outcome. Continue until success or failure occurs. Predict the eventual success probability and the average number of pairs tossed.
The four outcomes of one attempt are equally likely. That fact alone does not mean eventual success has probability one quarter: a restart gives another chance. Nor does another chance mean success is certain, because failure also stops the process.
Predict
Let a be the probability of success on one attempt, b the probability of failure, and r the probability of restart. These three events are disjoint and exhaust the possibilities, so a+b+r=1. In the coin example, a=b=1/4 and r=1/2.
Before calculating, distinguish three questions: success on the first attempt, success eventually, and success by a fixed cap. Also distinguish an attempt from a restart outcome. A terminating run with three attempts contains two restarts and one terminal result; counting all three as restarts overstates the work category.
Experiment
Construct the first two levels of an outcome tree on paper. Only the restart branches continue. The table collects branches by the attempt on which they stop, so different rows describe disjoint events.
| Event | Probability | Attempts used with cap two |
|---|
| Success immediately | 1/4 | 1 |
|---|
| Failure immediately | 1/4 | 1 |
|---|
| Restart then success | (1/2)(1/4)=1/8 | 2 |
|---|
| Restart then failure | 1/8 | 2 |
|---|
| Two restarts: unresolved | 1/4 | 2 |
|---|
Check the probabilities sum to one. By the cap, success and failure each have probability 3/8, while unresolved has probability 1/4. Expected attempts are (1/2)·1+(1/2)·2=3/2. Do not silently relabel unresolved as failure: it means the finite run has not produced either terminal outcome.
Now predict a third level before reading the general formulas. The unresolved probability becomes 1/8 and success by three becomes 1/4+1/8+1/16=7/16. These finite quantities approach limits; no finite table alone proves the infinite claim.
Understand
Assume attempts are independent and identically distributed. Success exactly on attempt j requires j−1 restarts followed by success, so its probability is r^(j−1)a. Adding these disjoint events through cap m gives a(1−r^m)/(1−r), provided r is less than 1. Failure has the same expression with b in place of a. The unresolved probability is r^m.
For 0≤r<1, r^m tends to zero. Thus termination occurs with probability one, and eventual success and failure are respectively a/(1−r)=a/(a+b) and b/(a+b). Almost-sure termination does not give a deterministic bound on the attempt count when r is positive: every finite number of consecutive restarts still has positive probability.
The familiar first-step equation agrees. If p is eventual success probability, then p=a+rp. Immediate success contributes a, immediate failure contributes zero, and a restart returns to the same independent problem. Solving gives the same ratio. The finite-tail argument additionally proves the unresolved mass disappears, rather than relying only on formal algebra.
For work, define T as the number of attempts through the first terminal result, and set T=∞ if that result never occurs. For every path, min(T,m) equals the sum of the indicators of T>j for j=0,…,m−1. In plain language, attempt j+1 is made exactly when the process has survived the first j attempts. Therefore
E[min(T,m)]=1+r+⋯+r^(m−1)=(1−r^m)/(1−r).
This is finite linearity of expectation, with no independence required between these indicators; independence was used earlier to obtain the tail probability r^j. The expectation of a nonnegative count is the limit of its capped expectations. Taking this limit proves E[T]=1/(1−r). Because terminating paths have T−1 restarts, the expected restart count is r/(1−r). For the coin example, eventual success is 1/2, mean attempts are 2 and mean restarts are 1. Every attempt uses two coin tosses, so expected tosses are 4; attempts and primitive operations are different units.
The boundary r=1 must be treated separately. Then a=b=0, every attempt restarts, and eventual success, eventual failure and termination each have probability zero. Work is infinite without a cap and exactly m attempts with cap m. The equation p=p is underdetermined, while the actual success event is empty. The quotient 0/0 and success conditional on a terminal outcome are undefined; neither is a valid answer of “any probability.”
Apply
Change the one-attempt probabilities to a=1/3,b=1/6,r=1/2. Predict the eventual outcome ratio, capped outcome probabilities at m=2 and expected attempts. Explain why the work matches the fair-coin example although the success probability changes.
Check the changed weights
Eventual success is 2/3 and failure 1/3. By two attempts success is (1/3)(1+1/2)=1/2, failure is 1/4, and unresolved is 1/4. Expected capped attempts are 3/2, while the uncapped mean is 2. Work depends on the restart probability; the division of terminal mass determines the success ratio.
Finally ask what a reset really restores. Drawing cards without replacement changes the remaining deck, so a restart does not reproduce the original experiment. Even when symmetry preserves the eventual success probability, the expected work may change. The practice compares replacement and no replacement by computing the changing conditional tails directly.
Continue
For a restarted procedure, specify the attempt boundary, terminal categories, retained state, cap and unit of work before writing a recurrence. Report unresolved probability separately, and state when a conditional probability requires a positive conditioning event. Finite calculations, a general tail argument and a reset assumption play different roles in the proof; numerical agreement on one example cannot replace any of them.
