Homework 2

Due: Thursday, April 16 at 12:00 PM

Problem 1: Kelly Betting with Cash

In the horse race model from lecture, a gambler must distribute all wealth across $n$ horses. Now suppose the gambler may also hold back a fraction $b_0 \geq 0$ of wealth in cash (which is always returned regardless of the outcome). The gambler chooses bets $b_1, \ldots, b_n \geq 0$ on the horses with $b_0 + \sum_{j=1}^{n} b_j = 1$. Horse $j$ wins with known probability $p_j$ (where $\sum_j p_j = 1$) and pays odds $r_j > 1$ (for each dollar bet on horse $j$, you receive $r_j$ dollars if it wins, and nothing otherwise). If horse $i$ wins, the gambler’s wealth is multiplied by $b_0 + b_i r_i$.

The gambler seeks to maximize the expected log-growth rate:

\[G(b_0, b_1, \ldots, b_n) = \sum_{i=1}^{n} p_i \log(b_0 + b_i r_i).\]

(a) Verify that $G$ is a concave function of $(b_0, b_1, \ldots, b_n)$. Write down the KKT conditions for the constrained optimization problem. Show that the Lagrange multiplier for the budget constraint satisfies $\lambda = 1$.

(b) Using the KKT conditions, show that the optimal strategy has the following structure. There is an active set $A \subseteq \{1, \ldots, n\}$ of horses that receive positive bets, determined by the threshold rule: horse $j \in A$ if and only if $p_j r_j > b_0^\star$. The optimal bets are:

\[b_j^\star = p_j - \frac{b_0^\star}{r_j} \quad \text{for } j \in A, \qquad b_0^\star = \frac{\sum_{j \notin A} p_j}{1 - \sum_{j \in A} 1/r_j}.\]

What is the meaning of these active bets in practice?

(Note: the active set $A$ and $b_0^\star$ must be determined self-consistently. That is, the rule $p_j r_j > b_0^\star$ must generate the same set $A$ used to compute $b_0^\star$. Hint: consider sorting the horses by their expected return $p_j r_j$.)

(c) Show that when $b_0^\star = 0$ (i.e., all horses are in the active set), the solution reduces to $b_j^\star = p_j$, recovering the standard Kelly result. For the case of a single horse with probability $p$ and odds $r$, show that the formula gives $b^\star = (pr - 1)/(r - 1)$, which is positive only when $pr > 1$ (the bet has positive expected value).

(d) A racetrack offers three horses with $(p_1, p_2, p_3) = (0.5, 0.3, 0.2)$ and odds $(r_1, r_2, r_3) = (3, 2, 2)$. Compute the optimal betting strategy. Which horses should you bet on, and how much cash should you hold?

Problem 2: The KT Estimator as a Universal Portfolio

The Krichevsky-Trofimov (KT) estimator for a binary sequence predicts $q_t = (n_1 + 1/2)/t$, where $n_1$ is the number of 1s in $x_1, \ldots, x_{t-1}$ and $t = n_0 + n_1 + 1$. This problem reveals that the KT estimator is a special case of the universal portfolio algorithm on a two-stock market.

(a) Define a market with two “stocks” corresponding to the two binary outcomes. At each round $t$, if $x_t = 1$ the price relatives are $(x_{1,t}, x_{2,t}) = (1, 0)$, and if $x_t = 0$ they are $(0, 1)$. Show that the wealth of the constant-rebalanced portfolio $\text{CRP}_b$ (with fraction $b$ in stock 1 and $1-b$ in stock 2) after observing $x_1, \ldots, x_{t-1}$ is:

\[S_{t-1}(b) = b^{n_1}(1-b)^{n_0}\]

where $n_1$ and $n_0$ are the counts of 1s and 0s. Observe that this is exactly the Bernoulli likelihood $P_b(x_1, \ldots, x_{t-1})$.

(b) Consider running Cover’s universal portfolio on this market with the Dirichlet(1/2, 1/2) prior $\mu(b) \propto b^{-1/2}(1-b)^{-1/2}$ (the Jeffreys prior on $[0,1]$). The algorithm plays:

\[\hat{b}_t = \frac{\int_0^1 b \cdot S_{t-1}(b) \, d\mu(b)}{\int_0^1 S_{t-1}(b) \, d\mu(b)}.\]

Using the Beta function identity $B(a,b) = \Gamma(a)\Gamma(b)/\Gamma(a+b)$, show that:

\[\hat{b}_t = \frac{n_1 + 1/2}{t}\]

which is precisely the KT estimator. (What estimator do you get with the uniform prior instead?)

(c) The Dirichlet(1/2, …, 1/2) universal portfolio on $m$ stocks achieves regret $\frac{m-1}{2}\log n + O(1)$. Explain why setting $m = 2$ immediately recovers the KT regret bound $\frac{1}{2}\log T + O(1)$. In light of this connection, interpret the KT estimator: what is it “doing” in portfolio language?

Problem 3: Universal Portfolios and the Volume Argument

(Note: we discussed this proof briefly in class, but didn’t address the details. Please work them out here!)

Consider Cover’s Universal Portfolio algorithm over the $m$-dimensional simplex $\Delta_m$, which at each round plays the performance-weighted portfolio:

\[\hat{b}_{t+1} = \frac{\int_{\Delta_m} b \cdot S_t(b) \, db}{\int_{\Delta_m} S_t(b) \, db}\]

where $S_t(b) = \prod_{s=1}^{t} \langle b, x_s \rangle$ is the wealth achieved by constant-rebalanced portfolio $b$.

(a) Let $b^\star = \arg\max_b S_T(b)$. Prove that for any region $K \subseteq \Delta_m$, the wealth of the universal portfolio satisfies:

\[\hat{S}_T \geq S_T(b^\star) \cdot \left( \min_{b \in K} \frac{S_T(b)}{S_T(b^\star)} \right) \cdot \frac{\text{Vol}(K)}{\text{Vol}(\Delta_m)}\]

(b) Show that for any portfolio in the “shrunken simplex” defined by $K = \{ b = (1-\epsilon)b^\star + \epsilon v : v \in \Delta_m \}$, the wealth achieved satisfies $S_T(b) \geq (1-\epsilon)^T S_T(b^\star)$. By evaluating the volume of this region and setting $\epsilon = O(1/T)$, conclude that the regret is $O((m-1)\log T)$.

Problem 4: Applying Kraft’s Inequality

You may use the following facts without proof:

• Kraft’s Inequality: A prefix-free binary code with codeword lengths $\ell_1, \ldots, \ell_n$ satisfies $\sum_{i=1}^{n} 2^{-\ell_i} \leq 1$. Conversely, if lengths satisfy this inequality, a prefix-free code with those lengths exists.
• Shannon Coding: For any probability distribution $P$ over $\{1, \ldots, n\}$, the code lengths $\ell_i = \lceil \log_2(1/P(i)) \rceil$ form a valid prefix-free code and satisfy $H(P) \leq \mathbb{E}[\ell_i] < H(P) + 1$.

(a) Recall that prefix-free Kolmogorov complexity $K(x)$ is defined using a universal prefix-free Turing machine $U$: $K(x) = \min\{\lvert p \rvert : U(p) = x\}$. Using Kraft’s inequality, show that the set of valid programs for $U$ satisfies $\sum_{x \in \{0,1\}^\star} 2^{-K(x)} \leq 1$. Interpret this: in what sense does $2^{-K(x)}$ define a probability distribution? How does this connect to Solomonoff’s universal prior $M(x) = \sum_{p:U(p)=x} 2^{-\lvert p \rvert}$?

(b) Suppose you have two prefix-free codes $C_1$ and $C_2$ with codeword lengths $\ell_i^{(1)}$ and $\ell_i^{(2)}$ for symbols $i \in \{1, \ldots, n\}$. Show that there exists a prefix-free code with lengths $\ell_i \leq \min(\ell_i^{(1)}, \ell_i^{(2)}) + 1$ for all $i$. (Hint: construct a new code that, given a single extra bit, selects the shorter codeword.) Interpret this in terms of combining two compressors: if one compressor is good for English text and another is good for Python code, what does the combined code achieve?

(c) Let $P$ and $Q$ be two probability distributions over a finite set $\mathcal{X}$. Using Shannon coding for $P$ and $Q$ respectively, and part (b), show that there exists a single prefix-free code whose expected codeword length under any distribution $R$ satisfies:

\[\mathbb{E}_R[\ell_i] \leq \min\left(\mathbb{E}_R[\lceil \log_2(1/P(i)) \rceil],\; \mathbb{E}_R[\lceil \log_2(1/Q(i)) \rceil]\right) + 1\]

Why does this mean the “regret” of the combined code, relative to the better of the two models, is at most 1 bit?

Problem 5: Properties of Kolmogorov Complexity

Let $K(x)$ denote the prefix-free Kolmogorov complexity of string $x \in \{0,1\}^\star$.

(a) Prove that $K(x) \leq \lvert x \rvert + 2\log\lvert x \rvert + O(1)$ for all $x$. (Hint: design a self-delimiting encoding.)

(b) Show that for every $n$, at least half of all strings of length $n$ satisfy $K(x) \geq n - 1$. Conclude that “most strings are incompressible.”

(c) Prove the Symmetry of Information (up to logarithmic terms): $K(x,y) = K(x) + K(y \mid x) + O(\log(K(x,y)))$. You may use the Invariance Theorem freely (see Lecture 6 notes, Section 2.2: for any two universal TMs $U_1, U_2$, $\lvert K_{U_1}(x) - K_{U_2}(x) \rvert \leq c$).

Problem 6: Solomonoff’s Convergence Bound

Let $M(x) = \sum_{p: U(p) = x} 2^{-\lvert p \rvert}$ be the universal semimeasure (Solomonoff’s prior), where the sum is over all programs $p$ that cause universal Turing machine $U$ to output $x$. Let $\mu$ be any computable measure over binary sequences. The Dominance Property states that there exists a constant $c_\mu > 0$ such that $M(x) \geq c_\mu \cdot \mu(x)$ for all $x$.

Using the Dominance Property, show that the Solomonoff predictor’s total expected KL divergence from $\mu$ is bounded:

\[\sum_{t=1}^{\infty} \mathbb{E}_{x_{1:t} \sim \mu} \left[ D_{\text{KL}}\left(\mu(\cdot \mid x_{< t}) \;\lVert\; M(\cdot \mid x_{< t})\right) \right] \leq K(\mu) \ln 2\]

where $K(\mu)$ is the Kolmogorov complexity of $\mu$ (the length of the shortest program that computes $\mu$).

(Hint: consider the log-likelihood ratio $\log \frac{\mu(x_{1:t})}{M(x_{1:t})}$ and use the chain rule for conditional probabilities to telescope the sum.)