Put . Before , all three players are active. Each unordered pair is selected with probability , and each direction of transfer then has conditional probability . Given the current holdings , a transfer within the first pair has mean product
For transfers within the other two pairs the analogous values are and . Averaging over pairs gives
At and after elimination the product is zero, since an eliminated player never re-enters. In particular the stopped process has increment
The indicator function is -measurable, and the expression in parentheses has zero conditional expectation on its support. The stopped process is adapted and integrable: at fixed , its absolute value is bounded by . Hence
This is the product martingale for three-player token exchange.
A discrete-time stopping time for a filtration is a random variable taking values in such that for every . It means that whether stopping has occurred by time can be determined from the information available then.
For the first elimination time,
Each event in this finite union belongs to , by the definition of the natural filtration. Therefore is a stopping time. This verification does not require first knowing whether is finite almost surely.
Choose as the pointwise limit of a sequence of where it exists, and as zero otherwise. The convergence event and every are -measurable, so this is an exactly -measurable version, bounded by . Part (a)(ii), the Doob-Dynkin lemma, supplies a Borel measurable function on such that . Applying scalar clipping to with bounds preserves that equality and ensures everywhere.
Part (c)(ii) and the conditional expectation formula from part (b)(iv) now give
Since the indices form a countable family, these identities may be taken on one common full-probability event.
For fixed , both the slope and the displayed average are constant on the atom , whose probability is . An equality holding almost surely of these constants forces the deterministic equality
Sum over . The telescoping sum gives
Thus the desired identity holds at every dyadic endpoint, including , without evaluating the undefined slope at .
Finally, given , take dyadic endpoints . The Lipschitz condition implies , and the bound on the Borel measurable function gives
Passing to the limit of a sequence proves
This is a martingale proof of the integral representation of a Lipschitz function. It constructs a bounded Lebesgue integrable function representing the increments of , and in particular proves absolute continuity of . No prior assumption that has a derivative is needed.
The uniformly integrable martingale convergence theorem states that a uniformly integrable martingale has an integrable terminal random variable such that almost surely and in the L1 norm, and
The last identity follows by passing to the limit of a sequence in for and , using convergence in L1.
Part (b)(iii) verifies uniform integrability for , so
Moreover almost surely. In this particular problem the common bound also yields convergence in Lp for every finite , including convergence in L2: the dominated convergence theorem applies to . General uniform integrability alone does not assert these higher-power conclusions.
Each is a bounded Borel measurable function of , including the specified value at . Therefore is an adapted process for and consists of integrable random variables.
Fix an atom of a sigma-algebra in with positive probability, corresponding to the dyadic interval , with . By the uniform distribution, each half has conditional probability . The conditional expectation of on that atom is therefore
The middle values cancel. On the zero-probability atom the conditional expectation can be chosen as zero, agreeing with our version of . Hence
so is a martingale. This is the dyadic slope martingale associated with the Lipschitz function .
For , repeated use of the floor function identity gives
Thus the filtration satisfies . Each positive-probability atom of a sigma-algebra here has the form
with probability ; is a possible additional null set atom. Averaging over each dyadic interval gives a version
For a globally defined version of the right side, assign any value, for example zero, on .
Indeed, the displayed random variable is -measurable and bounded by . On each its integral is
by the uniform distribution. Every member of is a union of the displayed sets and the possible zero-probability atom. Summing these identities therefore verifies the defining conditional expectation property on all of .
A family of integrable random variables is uniformly integrable when
The Lipschitz condition gives, on ,
Our chosen zero value on satisfies the same bound. Hence the random variables are integrable, and for every tail expectation in the definition vanishes. Therefore the family is uniformly integrable.
Every is a Borel measurable function of , by the formula involving the floor function. Thus
Conversely, part (i) gives the everywhere identity . For fixed , this is the pointwise limit of random variables measurable with respect to . Such a limit of a sequence is measurable, so . Consequently
These are increasing-precision observations even when the first finitely many are discarded; they do not behave like the independent random variables whose tail sigma-algebra appears in Question 1(b).
The floor function gives the deterministic bound
for every outcome, including . Thus all three convergence assertions hold: there is pointwise, and hence almost sure convergence, as well as convergence in probability and convergence in L2. In detail, for the probability is zero as soon as ; also
The uniform distribution even gives the exact second moment of the error by integrating over the dyadic partition:
We prove the Doob-Dynkin lemma here by simple function approximation. Choose such that everywhere, and let
Each is a finite-valued -measurable function and pointwise. Write its level sets as , with associated values . By part (i), choose Borel sets with . Define the Borel measurable functions
Although the chosen need not partition all of , their inverse images do partition , so exactly.
Apply scalar clipping to each with bounds , preserving this equality, and define . A bounded limit superior of Borel measurable functions is a finite Borel measurable function. At every the limit of a sequence exists and gives
Thus the factorization is exact for a bounded, exactly -measurable function. If hypotheses are instead given only up to null sets, the corresponding conclusion is a factorization holding almost surely after choosing a representative.
The sigma-algebra generated by a random variable is the smallest sigma-algebra on making a measurable function into . Equivalently, it is the intersection of all sigma-algebras containing the inverse images of Borel sets .
Let . This collection is already a sigma-algebra: ,
The right-hand sets are in , since the Borel sigma-algebra is closed under the indicated operations. Any sigma-algebra making measurable must contain every member of . Conversely makes measurable by definition. Hence
This equality holds exactly as a collection of sets, without completing the sigma-algebra.
Suppose the events are mutually independent events. Then is independent of , first by factorization against finite intersections of previous events and then by part (a). Therefore
If , the sum in part (ii) is infinite almost surely, and consequently
This is the Second Borel-Cantelli lemma. In fact part (ii) also yields probability zero in the convergent case for these independent events.
Both and are increasing, so each has a limit of a sequence in . Apply part (c)(ii) to the martingale , whose bounded increments were verified in part (i).
On we would have . On we would have . Both events have probability zero by the convergence-or-oscillation conclusion. Hence the two divergence events agree up to a null set. Since means precisely that infinitely many occur,
Taking probabilities proves the displayed equality in the question. This stronger agreement of events is the Conditional Borel-Cantelli lemma.
Choose versions
The stochastic process is increasing, and its th increment is -measurable, so it is predictable. The Doob decomposition theorem therefore gives
To check the martingale property directly, each summand is integrable and has zero conditional expectation given . The sums are an adapted process for the given filtration. Thus . Its bounded increments satisfy .
Apply part (i) for every positive integer and discard the countable union of its exceptional null sets. A sample path bounded below never reaches for some such , and must therefore converge to a finite limit of a sequence.
Apply the same argument to the martingale . Outside one more null set, every sample path bounded above also converges finitely. Thus a sample path which does not converge finitely must be unbounded in both directions. Each finite initial segment has finite values, so removing any such segment preserves unboundedness. It follows that the limit superior is and the limit inferior is . Consequently
This proves the bounded-increment martingale convergence-or-oscillation dichotomy; in particular one-sided divergence to infinity is impossible with positive probability.
The first entrance time is a stopping time, because . Before this time ; at entrance, the bounded increments give . Thus the stopped martingale
is a nonnegative martingale. Here the stopped process is a martingale since its increment is , whose conditional expectation given is zero.
The martingale convergence theorem states that a nonnegative martingale converges almost surely to a finite integrable random variable; indeed its expectations are constant, giving the required bound in the L1 norm. Apply this theorem to . On the stopped process equals the original one at every time. Hence
The overshoot bound is why the assumption of bounded increments matters.
Yes. The preceding calculation established . For every , the stopped martingale satisfies
Here is a single nonnegative integrable random variable that bounds the whole family. Thus, for any ,
The last limit follows from the dominated convergence theorem. This is precisely uniform integrability. It also gives with convergence in L1, and therefore , consistently with the preceding answer. A common bound on the individual expected values alone would not have sufficed; the integrable dominating random variable is what supplies control of every tail.
The optional stopping theorem at a bounded stopping time states that an integrable martingale satisfies whenever for a fixed finite . Apply this first to at . The simple symmetric random walk cannot cross an integer endpoint without hitting it, so
The preceding part gives almost surely, hence almost surely. The constant bound permits the dominated convergence theorem, yielding . Since is either or , solving gives its full probability distribution:
Now let
This counts the visit at time , and excludes the exit time. Apply the same bounded-time optional stopping theorem to . For each it gives
The visit counts increase to , so monotone convergence applies to the left. Dominated convergence applies to the right using . Consequently is an integrable random variable and
This is the origin case of expected occupation before interval exit for a simple symmetric random walk. The argument obtains integrability of the total occupation count before using any unbounded-time optional stopping for , so it does not presuppose the uniform integrability asked about next. The endpoint probabilities also agree with the standard gambler's ruin calculation.[ref]
For each ,
since is adapted. This verifies directly that is a stopping time.
Set . On , the random walk is at some integer strictly between and . If its next steps are all , it must hit within that block. These future steps are independent of and have probability of being all . Hence
The law of total expectation and mathematical induction give the geometric tail bound from a uniform escape probability:
Therefore . In fact this also proves by grouping the tail-sum formula into blocks of length . No assertion of independence between successive survival events is needed.
The filtration is generated by the successive independent random variables . Each is adapted, and makes it an integrable random variable. Since independence gives ,
Thus is a martingale.
Write the accumulated number of visits to zero as
It is adapted, and . Thus is also adapted and an integrable random variable. For every integer ,
Conditioning on and using independence of the next step therefore gives
The drift of the absolute value is cancelled exactly by the visit count, so . Hence both and are martingales. The latter is the absolute value martingale of a simple symmetric random walk, a discrete Tanaka formula in which visits to zero supply the correction at the corner of the absolute-value function.

There are unlisted articles, also show them or only show them.