数据科学基础 (Fall 2025)/Problem Set 6

• 每道题目的解答都要有完整的解题过程，中英文不限。

• 我们推荐大家使用LaTeX, markdown等对作业进行排版。

• 没有条件的同学可以用纸笔完成作业之后拍照。

Assumption throughout Problem Set 6

Without further notice, we are working on probability space [math]\displaystyle{ (\Omega,\mathcal{F},\Pr) }[/math].

Without further notice, we assume that the expectation of random variables are well-defined.

Problem 1 (LLN & CLT)

• [Proportional betting] In each of a sequence of independent bets, a gambler either wins 30%, or loses 25% of her current fortune, each with probability [math]\displaystyle{ 1/2 }[/math]. Denoting her fortune after [math]\displaystyle{ n }[/math] bets by [math]\displaystyle{ F_n }[/math], show that [math]\displaystyle{ \mathbb E(F_n)\to\infty }[/math] as [math]\displaystyle{ n \to\infty }[/math], while [math]\displaystyle{ F_n \to 0 }[/math] almost surely.
• [Entropy] The interval [math]\displaystyle{ [0,1] }[/math] is partitioned into [math]\displaystyle{ n }[/math] disjoint sub-intervals with lengths [math]\displaystyle{ p_1,p_2,\dots,p_n }[/math], and the entropy of this partition is defined to be [math]\displaystyle{ h= −\sum^n_{i=1} p_i log p_i }[/math]. Let [math]\displaystyle{ X_1,X_2,\dots }[/math] be independent random variables having the uniform distribution on [math]\displaystyle{ [0,1] }[/math], and let [math]\displaystyle{ Z_m^{(i)} }[/math] be the number of the [math]\displaystyle{ X_1,X_2,\dots,X_m }[/math] which lie in the [math]\displaystyle{ i }[/math]-th interval of the partition above. Show that [math]\displaystyle{ R_m =\prod^n_{i=1} p_i^{Z_m^{(i)}} }[/math] satisfies [math]\displaystyle{ m^{−1}\cdot\log R_m \to −h }[/math] almost surely as [math]\displaystyle{ m \to\infty }[/math].
• [Mobilizing a Supermajority] In a society of [math]\displaystyle{ n }[/math] independent individuals, each person independently (i) attends the vote with probability [math]\displaystyle{ \tau }[/math] and abstains with probability [math]\displaystyle{ 1-\tau }[/math]; (ii) if attending, votes "Yes" with probability [math]\displaystyle{ p }[/math] and "No" with probability [math]\displaystyle{ 1-p }[/math].
  A proposal is accepted if among all attendees, the fraction of Yes votes is at least a supermajority threshold [math]\displaystyle{ \theta \in (1/2,1) }[/math] (e.g., [math]\displaystyle{ \theta = 2/3 }[/math]). A mobilization campaign may add [math]\displaystyle{ m }[/math] extra supporters who certainly attend and certainly vote Yes. Your goal is to determine the minimal [math]\displaystyle{ m }[/math] such that the proposal passes with probability at least [math]\displaystyle{ 1-\delta }[/math].

Problem 3 (Concentration of measure)

• [Tossing coins] We repeatedly toss a fair coin (with an equal probability of heads and tails). Let the random variable [math]\displaystyle{ X }[/math] be the number of throws required to obtain a total of [math]\displaystyle{ n }[/math] heads. Show that [math]\displaystyle{ \Pr[X \gt 2n + \delta\sqrt{n\log n}]\leq n^{-\delta^2/6} }[/math] for any real [math]\displaystyle{ 0\lt \delta\lt \sqrt{\frac{4n}{\log n}} }[/math].

• [[math]\displaystyle{ k }[/math]-th moment bound] Let [math]\displaystyle{ X }[/math] be a random variable with expectation [math]\displaystyle{ 0 }[/math] such that moment generating function [math]\displaystyle{ \mathbf{E}[\exp(t|X|)] }[/math] is finite for some [math]\displaystyle{ t \gt 0 }[/math]. We can use the following two kinds of tail inequalities for [math]\displaystyle{ X }[/math]:
  • Chernoff Bound: [math]\displaystyle{ \Pr[|X| \geq \delta] \leq \min_{t \geq 0} {\mathbb{E}[e^{t|X|}]}/{e^{t\delta}} }[/math];
  • [math]\displaystyle{ k }[/math]th-Moment Bound: [math]\displaystyle{ \Pr[|X| \geq \delta] \leq {\mathbb{E}[|X|^k]}/{\delta^k} }[/math].

1. Show that for each [math]\displaystyle{ \delta }[/math], there exists a choice of [math]\displaystyle{ k }[/math] such that the [math]\displaystyle{ k }[/math]th-moment bound is no weaker than the Chernoff bound. (Hint: Use the probabilistic method. Construct a distribution over all [math]\displaystyle{ k }[/math]th-moment bound, and show that the expected bound is not weaker than the Chernoff bound.)
2. Why would we still prefer the Chernoff bound to the (seemingly) stronger [math]\displaystyle{ k }[/math]-th moment bound?

• [Densest induced subgraph in random graph] For a graph [math]\displaystyle{ G }[/math] on vertex set [math]\displaystyle{ [n] = {1,2,\dots,n} }[/math], define the average-degree density of an induced subgraph as [math]\displaystyle{ \mathrm{dens}(S) := \frac{e(S)}{|S|} }[/math], where [math]\displaystyle{ e(S) }[/math] is the number of edges with both endpoints in [math]\displaystyle{ S }[/math]. Define the densest induced subgraph of [math]\displaystyle{ G }[/math] as [math]\displaystyle{ \mathrm{dens}(G) := \max_{S \subseteq [n], |S|\ge 2} \mathrm{dens}(S) }[/math]. Show that, with probability at least [math]\displaystyle{ 2/3 }[/math], the densest induced subgraph in [math]\displaystyle{ G(n,1/2) }[/math] satisfies [math]\displaystyle{ \mathrm{dens}(G(n,1/2)) \le \frac{n}{2} + O(n^{1/2}) }[/math]. More precisely, prove that there exists an absolute constant [math]\displaystyle{ C \gt 0 }[/math] such that [math]\displaystyle{ \Pr\big( \mathrm{dens}(G(n,1/2)) \le \frac{n}{2} + C n^{1/2} \big) \ge \frac{2}{3} }[/math].

Problem 3 (Random processes)

• [High-dimensional random walk] Consider an unbiased random walk over [math]\displaystyle{ \mathbb R^n }[/math] with [math]\displaystyle{ n\gt 1 }[/math]. At each step, assuming we are at position [math]\displaystyle{ X }[/math] without loss of generality, for each dimension [math]\displaystyle{ i }[/math], we choose a movement [math]\displaystyle{ \delta_i\in\mathbb R }[/math] with [math]\displaystyle{ \mathbb E [\delta_i]=0 }[/math] (i.e. unbiased) at random, then move to [math]\displaystyle{ X+\sum_i\sigma_i }[/math]. Prove that an unbiased random walk in any number of dimensions, regardless of the distributions of [math]\displaystyle{ \sigma_i }[/math]'s, is an example of a martingale.

• [Pólya’s urn]A bag contains red and blue balls, with initially [math]\displaystyle{ r }[/math] red and [math]\displaystyle{ b }[/math] blue where [math]\displaystyle{ rb \gt 0 }[/math]. A ball is drawn from the bag, its color noted, and then it is returned to the bag together with a new ball of the same color. Let [math]\displaystyle{ R_n }[/math] be the number of red balls after [math]\displaystyle{ n }[/math] such operations. Show that [math]\displaystyle{ Y_n = R_n/(n + r + b) }[/math] is a martingale.

• [Optional stopping 1-D symmetric random walk] Let [math]\displaystyle{ S_n = a + \sum_{r=1}^n X_r }[/math] be a simple symmetric random walk. The walk stops at the earliest time [math]\displaystyle{ T }[/math] when it reaches either [math]\displaystyle{ 0 }[/math] or [math]\displaystyle{ K }[/math], where [math]\displaystyle{ 0 \lt a \lt K }[/math]. Show that [math]\displaystyle{ M_n = \sum_{r=0}^n S_r - \tfrac{1}{3} S_n^3 }[/math] is a martingale, and deduce that [math]\displaystyle{ \mathbb{E}\left( \sum_{r=0}^{T} S_r \right) = \tfrac{1}{3} (K^2 - a^2) a + a. }[/math]

• [Random walk on a graph] A particle performs a random walk on the vertex set of a connected graph [math]\displaystyle{ G }[/math], which for simplicity we assume to have neither loops nor multiple edges. At each stage it moves to a neighbor of its current position, each such neighbor being chosen with equal probability. If [math]\displaystyle{ G }[/math] has [math]\displaystyle{ \eta\lt \infty }[/math] edges, show that the stationary distribution is given by [math]\displaystyle{ \pi(v) = d_v/(2\eta) }[/math], where [math]\displaystyle{ d_v }[/math] is the degree of vertex [math]\displaystyle{ v }[/math].
• [Reversibility versus periodicity] Can a reversible chain be periodic?
• [Metropolis–Hastings algorithm] To sample a state, for each state [math]\displaystyle{ x }[/math], the Glauber dynamics uniformly chooses a state among the adjacent states of [math]\displaystyle{ x }[/math] together with state [math]\displaystyle{ x }[/math] itself at random in each step, and moves to the chosen state. The Metropolis-Hastings algorithm generalizes the idea of Glauber dynamics. Let us assume that we have designed an irreducible state space for our Markov chain; now we want to construct a Markov chain on this state space with a stationary distribution [math]\displaystyle{ \pi_x = b(x)/B }[/math], where for all [math]\displaystyle{ x \in \Omega }[/math] we have [math]\displaystyle{ b(x) \gt 0 }[/math] and such that [math]\displaystyle{ B =\sum_{x\in\Omega} b(x) }[/math] is finite.

1. For a finite state space [math]\displaystyle{ \Omega }[/math] and neighborhood structure [math]\displaystyle{ \{N(X ) | x \in\Omega\} }[/math], let [math]\displaystyle{ N = \max_{x\in\Omega} |N(x)| }[/math]. Let [math]\displaystyle{ M }[/math] be any number such that [math]\displaystyle{ M \ge N }[/math]. For all [math]\displaystyle{ x \in \Omega }[/math], let [math]\displaystyle{ \pi_x \gt 0 }[/math] be the desired probability of state [math]\displaystyle{ x }[/math] in the stationary distribution. Consider a Markov chain where [math]\displaystyle{ P_{x,y} = \begin{cases}(1/M) \min(1, \pi_y/\pi_x ) &\text{if $x \ne y$ and $y \in N(x)$},\\ 0 &\text{if $x \ne y$ and $y \notin N(x)$},\\ 1 − \sum_{y\ne x} P_{x,y} &\text{if $x = y$}\end{cases} }[/math]. Assume this chain is irreducible and aperiodic, verify that the stationary distribution is given by the probabilities [math]\displaystyle{ \pi_x }[/math]. (Hint: Show the time-reversibility.)
2. Let [math]\displaystyle{ S = \sum_{i=1}^\infty i^{−2} = \pi^2/6 }[/math]. Design a Markov chain based on the Metropolis-Hastings algorithm on the positive integers such that, in the stationary distribution, [math]\displaystyle{ \pi_i = 1/(S\cdot i^2) }[/math] . The neighbors of any integer [math]\displaystyle{ i \gt 1 }[/math] for your chain should be only [math]\displaystyle{ i − 1 }[/math] and [math]\displaystyle{ i + 1 }[/math], and the only neighbor of [math]\displaystyle{ 1 }[/math] should be the integer [math]\displaystyle{ 2 }[/math].