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 productFor transfers within the other two pairs the analogous values are and . Averaging over pairs givesAt and after elimination the product is zero, since an eliminated player never re-enters. In particular the stopped process has incrementThe 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 . HenceThis 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 giveSince 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 equalitySum over . The telescoping sum givesThus 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 givesPassing to the limit of a sequence provesThis 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, andThe 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 , soMoreover 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 thereforeThe middle values cancel. On the zero-probability atom the conditional expectation can be chosen as zero, agreeing with our version of . Henceso is a martingale. This is the dyadic slope martingale associated with the Lipschitz function .
For , repeated use of the floor function identity givesThus the filtration satisfies . Each positive-probability atom of a sigma-algebra here has the formwith probability ; is a possible additional null set atom. Averaging over each dyadic interval gives a versionFor 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 isby 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 whenThe 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. ThusConversely, 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 . ConsequentlyThese 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 boundfor 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 ; alsoThe 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 letEach 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 functionsAlthough 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 givesThus 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. HenceThis 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). ThereforeIf , the sum in part (ii) is infinite almost surely, and consequentlyThis 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 versionsThe stochastic process is increasing, and its th increment is -measurable, so it is predictable. The Doob decomposition theorem therefore givesTo 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 . ConsequentlyThis 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 martingaleis 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. HenceThe overshoot bound is why the assumption of bounded increments matters.
Yes. The preceding calculation established . For every , the stopped martingale satisfiesHere 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, soThe 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 letThis counts the visit at time , and excludes the exit time. Apply the same bounded-time optional stopping theorem to . For each it givesThe visit counts increase to , so monotone convergence applies to the left. Dominated convergence applies to the right using . Consequently is an integrable random variable andThis 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]
Probability: Theory and Examples (fifth edition) by Rick Durrett. §4.8.1, Theorem 4.8.7(a), printed pp. 257–258: symmetric random-walk interval-exit probabilities
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 . HenceThe 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 asIt 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 givesThe 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.