(b)(i): communicating classes. Every increment is divisible by , so the residue class modulo is preserved. Conversely, if is divisible by , Bézout's identity applied to gives a path just as in (b)(i). Thus the original Markov chain is reducible on , with exactly the closed communicating classesThe specified walk starting at zero stays in .
(b)(ii): period of a state in a Markov chain. The return equation reduces to . Hence , . For every state, the period of a state in a Markov chain is thereforeThis is still at least two, so no state is aperiodic.
(b)(iii): stationary distribution. The conclusion is unchanged: there is no stationary distribution on . The maximum-mass proof in (b)(iii) applies verbatim, without using coprimality. Equivalently, each closed communicating class, after translating and dividing its state labels by , is the same centered random walk with step sizes and has no stationary distribution.
(b)(iv): occupation of zero. On , the rescaled walk has exactly the transition probabilities of the coprime walk with parameters . The return-probability argument in (b)(iv) therefore makes this class null recurrent. The renewal process proof of the occupation limit applies unchanged:Starting in another residue class would make every visit to zero impossible, also giving occupation proportion zero.
(c)(i): modified communicating classes. These are unchanged: is one finite closed communicating class, and all other states are transient singleton classes. The original proof used consecutive reset destinations and never used coprimality. Resetting to the consecutive integers connects different residue classes, so it would be incorrect to split according to residue classes modulo .
(c)(ii): limiting distribution. The column-sum calculation, the irreducible Markov chain property on a finite class, positive self-transition probabilities, and geometric entrance argument also required no coprimality. Thus for every initial state the same convergence in distribution holds:In particular, the denominator is unchanged; it is not divided by .
The strong law of large numbers states that, for independent and identically distributed random variables with ,Thus, outside an event of probability zero, the sample mean converges to the common expected value.
For a Borel set , the joint probability density givesFor each , substitute . The change of variables for probability densities contributes , with the absolute value accounting for the reversed orientation when . The line has two-dimensional Lebesgue measure zero, so omitting it changes no probability. By the Tonelli theorem,The bracket is nonnegative and its integral over is one. This proves the probability density of a product of random variables formula:As usual, a probability density function is determined only almost everywhere; exceptional infinite values are harmless.
For the independent random variables with the specified uniform distribution, on and zero elsewhere. When , the conditions and are equivalent to . ThereforeThe value assigned at zero is arbitrary. Substitution checks normalization of a probability distribution: . This is the product of independent uniform random variables law.
If , then almost surely. Intersecting these events over all still gives an event of probability one. On it, , so the products have a finite nonnegative limit .
For every , the inclusion and part (c)(i) imply . Taking for positive integers proves almost surely. ThusThe monotonicity is the extra ingredient that upgrades convergence in probability to almost sure convergence here.
Every step changes the population by one, so has the parity of when . Hence . A return in two steps has positive probability from every state, and all return times are even, so the period of a state in a Markov chain is exactly two.
Each transition exchanges the even and odd classes. Since is an invariant distribution, their masses are equal: . The chain sampled at times , restricted to the even states, is irreducible and positive recurrent, and it is aperiodic because its diagonal entries are positive. Its stationary distribution is on even . The countable-state Markov chain convergence theorem applied to this sampled chain yieldsSince , the full sequence has no limit. Its time average nevertheless tends to by the countable-state Markov chain ergodic theorem.
Write and . The two conditional expectation identities supply a -measurable version of and a -measurable version of . Work with those versions, which do not change any almost sure equality. Both lie in L2 space, and the Cauchy-Schwarz inequality makes their product an integrable random variable.
Testing the first conditional expectation identity against , and the second against , givesFor completeness, these tests with unbounded multipliers are valid by first using the bounded truncations and , then passing to the limit with the Cauchy-Schwarz inequality and convergence in L2. Consequently,A nonnegative random variable with zero expected value vanishes almost surely. Therefore almost surely. This is mutual conditional expectation rigidity in L2; it also follows from the equality case for conditional second moments.
For a counterexample to equality of the original random variables, let give probability to each of , set , and use the nonconstant function . Then takes both values and . It is measurable with respect to both generated sigma-algebras, so both required conditional expectation identities hold. Symmetry gives , while neither random variable can be zero. Thus
Retain the binary random variables . Iterating the recursion givesEach binary history determines the full vector , so its sigma-algebra is finite by the sigma-algebra of a finite-valued random vector. Conversely, because , the integer uniquely determines the digits ; also . ThusAll binary histories have positive probability. By independence of the driving uniform random variables, along a fixed finite history every intermediate state is in , so each subsequent conditional branch probability, either or , is strictly positive. It follows that has nonempty fibres, each an atom of a sigma-algebra, and exactly elements.
Adaptedness from the preceding part gives . For , however, contains the events for every . They have distinct probabilities , so there are infinitely many distinct such events. Consequently the finite sigma-algebra cannot equal . The inclusion is strict for every .
The tail sigma-algebra of this sequence isFor each fixed , the preceding event equality givesEvery event on the right is determined by coordinates with index at least . Therefore for every , and . The random variables are independent, so Kolmogorov's zero–one law applies: every tail event has probability zero or one. Hence .
The role of independence can also be seen directly. A tail event is independent of each finite initial sigma-algebra . The Monotone class theorem extends this independence to ; since itself lies there, it is independent of itself. Thus .[ref]
Probability: Theory and Examples (fifth edition) by Rick Durrett. §2.5, Theorem 2.5.3, printed pp. 81–82: the tail sigma-field zero–one law
For , the definition of the common cumulative distribution function givesThe strict exceedance matters here: an atom of a measure at belongs to , so it is already included in . The events are mutually independent events, since each depends on a separate member of the independent random variables .
If , countable subadditivity gives, for every ,Continuity of probability then gives . This is the First Borel-Cantelli lemma and does not need independence.
If the series diverges, independence and give, for every fixed ,Taking shows that the probability of no exceedance after is zero. A countable union over shows that finitely many exceedances has probability zero. This is the Second Borel-Cantelli lemma. Together with the preceding event equality, it proves
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.
For , fix signs . The constraints leave exactly two choices for the signs : choose freely, then set and for . Each input tuple has probability by independence. ConsequentlyEvery finite subfamily is a marginal distribution of one such initial segment, so the entire sequence is independent, with fair sign probability distributions.
Using the usual everywhere sign-valued representatives, for every we haveThe right side is measurable with respect to . Therefore is measurable with respect to their intersection .
Write . The Kolmogorov zero-one law applies to the independent random variables , so every event has probability zero or one. Also is independent of : this follows first for finite intersections of sign events from the given independence, then for their generated sigma-algebra by part (a).
The sets with and form a pi-system generating . If , the event has probability zero and is independent of every event in . If , it differs from by a null set, so the same independence follows from that of and . Another application of part (a) provesIn particular cannot contain the nontrivial event , whereas does. Thus adjoining a sigma-algebra need not commute with a decreasing intersection.
There is a small version qualification if the assumptions specify only the probability distributions, allowing exceptional values other than signs. Put when the denominator is nonzero, and otherwise. For , is measurable with respect to . The limit superior of , after scalar clipping to , is therefore -measurable and equals almost surely. Literal measurability of an arbitrary version of need not follow without choosing sign-valued representatives or adjoining the ambient null sets. All the independence conclusions are unaffected.
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.
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.
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:
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 .
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.
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 .
After , the token product remains zero, whereas the deterministic term continues to increase. Combining this with the pre-elimination calculation in part (ii),The stochastic process is adapted and integrable at each fixed time, and the displayed conditional expectation is nonnegative. Thus is a submartingale.
For it is neither a martingale nor a supermartingale. If , there is positive probability that the first player transfers a token to the second in each of the next rounds. Until the last such round all three remain active, so this event has probability and entails . At time the displayed conditional expectation is therefore strictly positive on an event of positive probability, ruling out both the zero drift required of a martingale and the nonpositive drift required of a supermartingale. If an initial holding is zero, and the same conclusion follows immediately. The degenerate case gives a constant martingale.