Korean, Edit

Lecture 3. Increasing sequences and Cauchy sequences

Recommended post: 【Analysis】 Table of contents for Analysis

1. Convergence and basic properties

2. Cauchy sequences

3. Example: optimal stopping and Cauchy sequences

1. Convergence of sequences and basic properties

⑴ What it means for a real sequence (a_n)_n∈ℕ to converge to a real number a

① For N ∈ ℕ, for all n ＞ N

② For every positive ε, there exists an N such that eventually ㅣ a_n - a ㅣ ＜ ε

⑵ Given a sequence (a_n) and an increasing sequence of natural numbers n₁ ＜ n₂ ＜ ···, the new sequence (a_nk)_k∈ℕ is called a subsequence of (a_n).

⑶ Exercise: Prove the following.

① If eventually a_n = a, then (a_n) converges to a.

② If (a_n) converges to a, then the set {a_n} is bounded.

③ Suppose (a_n) → a and (b_n) → b. If eventually a_n ≤ b_n, show that a ≤ b.

④ If (a_n) → a and eventually a_n ≤ b, then a ≤ b.

⑤ If (a_n) → a and also (a_n) → b, then a = b. That is, the limit of a convergent sequence is unique.

⑷ Exercise: Prove the following.

① If (a_n) → a, then every subsequence (a_nk) also converges to a.

② The sequence (1/n) converges to 0.

⑸ Exercise: Prove the following.

① When 0 ＜ p ＜ 1, the sequence (pⁿ) converges to 0.

② a_n, a ∈ ℝ −｛0｝ and if a is the limit of (a_n), show that the following holds.

⑹ Exercise: Prove the following.

① The sequence (a_n) = (1, 0, 1, 0, ···) does not converge.

② If a is the limit of (a_n) and b is the limit of (b_n) show that the following holds.

⑺ Exercise: Prove the following.

① Convergence of increasing sequences: If a₁ ≤ a₂ ≤ ··· and (a_n) is bounded, show that (a_n) converges. Can you reach the same conclusion for decreasing sequences?

② Let two sequences (a_n) and (b_n) satisfy a₁ = 1, b₁ = 2 and

and let

holds. Show that both sequences converge.

⑻ Exercise: Let the sequence (a_n) have a₁ = 3 and for each n ∈ ℕ, define

Show that (a_n) converges. To what does it converge?

2. Cauchy sequences

⑴ Definition of a Cauchy sequence

① For N ∈ ℕ, for all n, m ＞ N

② A real sequence (a_n) is a Cauchy sequence if for every ε ＞ 0, there exists an N such that eventually ㅣ a_n - a_m ㅣ ＜ ε

⑵ For a vector sequence ((a_n, b_n))_n∈ℕ in ℝ² to converge to the vector (a, b) is the same as

and

respectively.

⑶ Define the infinite series I as follows:

For a real sequence (a_n), saying that the infinite series I converges to A means that the sequence of partial sums (A_n) converges to A. Here A_n = a₁ + ··· + a_n.

⑷ Bolzano–Weierstrass theorem: If a real sequence (a_n) is bounded, it has a convergent subsequence. Can we say the same for ((a_n, b_n))_n∈ℕ?

⑸ Exercise: Show that if (a_n) is a Cauchy sequence, then it converges.

⑹ Exercise: If

then

holds. Prove this.

⑺ Exercise: Find an example where the limit of (a_n) is 0 but the infinite series I does not exist.

⑻ Exercise: For a real r, exactly when does the geometric series

converge?

⑼ Exercise: Let a real sequence a₁, a₂, a₃, ··· satisfy a_n ≥ 0 for each n. Show that the infinite series

converges if and only if the sequence of partial sums (A_n) is bounded.

⑽ Exercise: If the infinite series

converges, prove that the infinite series

also converges.

⑾ Exercise: Let the sequence (a_n) be defined by a₁ = 1 and for each n ∈ ℕ, define

Show that (a_n) converges. To what does it converge? Can this limit be expressed as a continued fraction?

○ Solution

By mathematical induction, a_2n and a_2n-1 can be shown to be increasing sequences.

Also, since a_n ＜ 2, the sequence (a_n) is bounded above.

An increasing and bounded sequence converges; hence (a_2n), (a_2n-1) converge.

As will be seen in the next steps, the limits of (a_2n) and (a_2n-1) are the same, so (a_n) converges.

Let a be the limit of (a_n); then we have the following.

The continued-fraction representation is as follows.

3. Example: optimal stopping and Cauchy sequences

⑴ Theorem 1. If V_t(i) = max{r(i), a + b∑_j∈S ℙ(j ㅣ i) V_t+1(j)} = max{r(i), a + b𝔼[V_t+1(j) ㅣ i]}, then V_t(i) ≥ V_t+1(i) holds

Proof 1. Algebraic proof: Use mathematical induction (backward induction)

Proof 2. Combinatorial proof: Similarly use mathematical induction. In a backward induction setting, if V_τ(i) ≥ V_τ+1(i) holds for τ = t+1, …, T-1 while a repetitive pattern recurs at each τ, then if we forcibly pick “status quo” at any single step along the trajectory from V_t(·) → V_T(·), the evolution can be made completely identical to the trajectory from V_t+1(·) → V_T(·). Therefore V_τ(i) ≥ V_τ+1(i) also holds at τ = t.

Note. The fact that it is a max is not essential. Even if it is defined with an inf in the next example, adding an extra stage gives a chance to add a nonnegative cost, so minimization cannot make the value go down. That is, V_n(i) ≤ V_n+1(i) (forward induction)

⑵ Theorem 2. If V_t(x) = max{-c + p(x)(1 + V_t+1(x-1)) + (1 - p(x))V_t+1(x), V_t+1(x)}, V_N+1(x) = 0, then the following hold

① Monotonicity in time: V_t(x) ≥ V_t+1(x)

Proof

V_t(x) = max{·, V_t+1(x)} ≥ V_t+1(x)

② Monotonicity in x: V_t(x) ≥ V_t(x-1)

Proof

Consider the grid formed by (t, x).

Check that at x = 0 we have V_t(x) = V_t+1(x) for all t.

In the order (t, x) = (N+1, 0), ⋯, (N+1, S), (N, 0), ⋯, (N, S), (N-1, 0), ⋯ we can verify that the above inductive hypothesis is preserved.

(If S = ∞, traverse along the diagonal.)

That is, at each induction step we can find A, B, C, D such that A ≤ B, C ≤ D, and V_t(x-1) = max(A, C) ≤ max(B, D) = V_t(x).

For example, B = -c + p(x)(1 + V_t+1(x-1)) + (1 - p(x))V_t+1(x).

③ Upper bound on marginal value: 1 ≥ V_t(x) - V_t(x-1)

Proof

Consider running the world with initial particle count x (A) and the world with x-1 (B) under the same action sequence (the same “look/skip” each day).

If there really exists a point where V_t(x) - V_t(x-1) > 1, then simply “replicating and executing” that policy in both worlds (with no other device) would create a stable excess profit for A over B exceeding 1.

Repeating such replication infinitely would imply the possibility of creating unbounded profit, which contradicts many rules of this world such as symmetry.

Therefore that profit gap can never exceed 1.

Hence such a point does not exist.

Intuition

Intuitively, expected gain cannot exceed sure gain, so V_t(x) - V_t(x-1) must be ≤ the sure gain 1.

Intuition

In practice, when you simulate V_t(x), it does not show a wildly oscillating shape. (∵ ⑥ Existence of a threshold)

In fact, by ⑤ Time relation of marginal value, V_t(x) - V_t(x-1) is monotone in time.

A bounded monotone sequence converges by the completeness axiom.

And by symmetry the limit must be exactly 1, neither larger nor smaller than 1.

④ Failure of concavity in x: V_t(x) - V_t(x-1) ≤ V_t(x-1) - V_t(x-2)

Counterexample

In all three of the following situations, concavity in x failed.

⑤ Time relation of marginal value: V_t(x) - V_t(x-1) ≥ V_t+1(x) - V_t+1(x-1)

Proof. Mimicking policy

We say that the marginal value of one extra particle, ΔV_τ(x) = V_τ(x) - V_τ(x-1), decreases as the remaining horizon shrinks.

From ② Monotonicity in x, we know ΔV_τ ≥ 0.

Suppose there are two worlds, one at time t (A) and one at time t+1 (B).

If we force A to wait one step and then run the same action sequence as B (the same “look/skip” each day), we can obtain the same marginal value.

But A has one more day of freedom than B, so it can choose actions that make V_t(x) - V_t(x-1) sufficiently larger.

Therefore V_t(x) - V_t(x-1) ≥ V_t+1(x) - V_t+1(x-1).

Significance

From ①, ②, ③, and ⑤, we can easily prove S_k = {x ㅣ c ≥ p(x)(1 + V_k+1(x-1) - V_k+1(x))}, and S_k ⊃ S_k+1.

For reference, S_k is the set of x values where the value function does not change on day k, i.e., where “stay” is chosen.

⑥ Existence of a threshold: G_t(x) = p(x)(1 - Δ_t+1(x)) is a monotone increasing function of x

**Proof. **

Let Sk = {x ㅣ c ≥ p(x)(1 - Δk+1(x))} = {x

c ≥ Gt(x)}.

When t = N we know G_t(x) = p(x), which is a monotone increasing function of x.

Consider the grid formed by (t, x).

In the order (t, x) = (N+1, 0), ⋯, (N+1, S), (N, 0), ⋯, (N, S), (N-1, 0), ⋯, verify that the above inductive hypothesis is preserved.

(If S = ∞, traverse along the diagonal.)

Suppose that for t+1, ···, N we have verified that Sk can be written as {0, 1, ···, x_k*}.

If “stay” is chosen at (t+1, x), then there is no further gain from “look,” so at (t, x) we also choose “stay.”

If “look” is chosen at (t+1, x) and also at (t+1, x-1), then at (t, x) we can safely choose “look.”

If “look” is chosen at (t+1, x) but “stay” at (t+1, x-1), then at (t, x) we may either wait briefly or choose “look.”

Therefore even at time t we still have S_k = {0, 1, ···, x_k}, and we have also checked the possibility that xt ≥ xt+1*.

Writing Sk as {0, 1, ···, x_k*} inductively proves that G_t(x) is monotone increasing.

This explains why V_t(x) does not exhibit a wildly oscillating shape.

Posted: 2019.12.25 00:53

Revised: 2025.10.25 18:10