Chapter 30 Exercises

Foundational Exercises (1-10)

Exercise 1: State Space Enumeration

Given three binary events --- A (Fed raises rates), B (GDP > 3%), C (Unemployment < 4%) --- enumerate all eight possible states of the world. For each state, write a descriptive label (e.g., "Rate hike, strong GDP, low unemployment"). How many distinct Boolean expressions can be formed over these three events? (Hint: each Boolean expression corresponds to a subset of the eight states.)

Exercise 2: Joint Distribution Construction

You are given the following marginal probabilities and one conditional: - P(A) = 0.60 - P(B) = 0.45 - P(B | A) = 0.30

Compute the full joint distribution over A and B. Verify that all four state probabilities sum to 1. What is the implied correlation between A and B?

Exercise 3: Combinatorial Explosion Calculation

A prediction market platform wants to offer combinatorial markets on 25 binary events.

(a) How many states would the full combinatorial market require? (b) If each state requires 8 bytes of storage, how much total memory is needed for the share vector? (c) If computing the cost function requires iterating over all states and each iteration takes 1 nanosecond, how long does a single cost function evaluation take? (d) Is this feasible for a real-time market? What alternatives would you suggest?

Exercise 4: LMSR Price Calculation

A full combinatorial LMSR has 3 events and b = 50. The share vector is: - State (T,T,T): 20 shares - State (T,T,F): 15 shares - State (T,F,T): 10 shares - State (T,F,F): 25 shares - State (F,T,T): 5 shares - State (F,T,F): 0 shares - State (F,F,T): 8 shares - State (F,F,F): 12 shares

(a) Compute the price (probability) of each state. (b) Compute P(Event 1 = True). (c) Compute P(Event 2 = True | Event 1 = True). (d) Compute P(Event 1 AND Event 2).

Exercise 5: Partition Market Savings

You have 12 events that can be partitioned into three independent groups of sizes 4, 4, and 4.

(a) How many states does the full combinatorial market have? (b) How many total states do the three partition sub-markets have? (c) What is the speedup factor? (d) Now suppose the partition sizes are 6, 4, and 2. Recalculate. Which partition structure is more efficient and why?

Exercise 6: Independence Test

Two events X and Y have the following joint distribution:

(a) Are X and Y independent? Show your work. (b) Now consider:

Are X and Y independent? Compute the correlation.

Exercise 7: Conditional Token Splitting

You have $100 in collateral. Explain, step by step, how the conditional token framework would split this into tokens for the following question: "If the Democrats win the Senate, will the infrastructure bill pass?"

Show the token tree, including: - Level 0: Collateral - Level 1: Split on Senate outcome - Level 2: Split on bill outcome (conditional on Senate result)

What are the four final tokens, and what does each one pay?

Exercise 8: Bundle Order Cost

A market has three events with current prices: - P(A) = 0.60 - P(B) = 0.40 - P(C) = 0.55

A trader submits a parlay bundle: buy 10 shares of A, B, and C all being True.

(a) If the events are priced independently, what is the implied probability of the parlay? (b) If the LMSR has b = 50, estimate the cost of buying 10 shares of each event separately. (c) Why might the actual cost differ from this estimate?

Exercise 9: Maximum Loss Bound

A market operator runs an LMSR-C with b = 200 over 20 events.

(a) What is the maximum possible loss? (b) If only 8 of the 20 events have been activated by trades, what is the effective maximum loss? (c) Compare this to the maximum loss of 20 separate binary LMSR markets with the same b.

Exercise 10: Arbitrage Detection

A combinatorial market reports the following prices: - P(A) = 0.70 - P(B) = 0.60 - P(A AND B) = 0.55 - P(A OR B) = 0.80

Is this set of prices consistent? If not, identify the violation and describe an arbitrage strategy.

Intermediate Exercises (11-20)

Exercise 11: Bayesian Network Market

Design a Bayesian network for the following scenario: Rain (R) affects both Crop Yield (C) and Flood Risk (F). Crop Yield also depends on Temperature (T), which is independent of Rain.

(a) Draw the directed acyclic graph. (b) How many parameters does the full joint distribution require? (c) How many parameters does the Bayesian network factorization require? (d) Write the factored probability expression.

Exercise 12: Mean-Field Approximation

Given two events X and Y with joint distribution P(X=1, Y=1) = 0.4, P(X=1, Y=0) = 0.1, P(X=0, Y=1) = 0.1, P(X=0, Y=0) = 0.4:

(a) Compute the true marginals P(X=1) and P(Y=1). (b) Compute the mean-field approximation (product of marginals). (c) Compute the KL divergence from the mean-field approximation to the true distribution. (d) What information about the joint distribution does the mean-field approximation miss?

Exercise 13: Sampling-Based Pricing

You have a combinatorial market with 5 events and want to estimate P(event 1 AND event 2 | event 3) using importance sampling with 1000 samples from a uniform proposal distribution.

(a) Write pseudocode for this estimation procedure. (b) What is the expected number of samples that match the condition (event 3 = True)? (c) How would you improve the accuracy if the condition event has very low probability (e.g., P(event 3) = 0.01)?

Exercise 14: Partition Optimization

You have 10 events with the following known correlations (all other pairs have zero correlation): - corr(1,2) = 0.8 - corr(1,3) = 0.6 - corr(2,3) = 0.7 - corr(4,5) = 0.9 - corr(6,7) = 0.3 - corr(8,9) = 0.5 - corr(9,10) = 0.4

(a) What partition structure would you recommend? (b) Calculate the total number of states. (c) If you had a budget of at most 64 states per partition, would you change your recommendation?

Exercise 15: Conditional Market Mechanics

A conditional market for P(GDP Growth | Carbon Tax) has the following state prices after trading: - (Tax=T, GDP=T): 0.10 - (Tax=T, GDP=F): 0.30 - (Tax=F, GDP=T): 0.35 - (Tax=F, GDP=F): 0.25

(a) What is P(Carbon Tax passes)? (b) What is P(GDP Growth | Carbon Tax)? (c) What is P(GDP Growth | No Carbon Tax)? (d) What is the implied "causal effect" of the carbon tax on GDP growth? (e) A trader buys 10 shares of "GDP Growth given Carbon Tax." If the carbon tax does not pass, what happens to these shares?

Exercise 16: Lazy Evaluation Efficiency

An LMSR-C market has 30 events but traders have only ever traded on events {1, 2, 5, 7, 12}. Additionally, the trades have the following structure: - Buy event 1 - Buy event 2 - Buy (event 1 AND event 5) - Buy (event 7 AND NOT event 12)

(a) How many states does the lazy evaluation need to enumerate? (b) Compare this to the full state space. (c) If a new trade arrives on event 3, how does the state space change?

Exercise 17: Bundle Order Design

Design bundle orders for the following trading strategies:

(a) Positive correlation bet: You believe events A and B are more correlated than the market implies. (b) Negative correlation bet: You believe events C and D are negatively correlated. (c) Scenario hedge: You hold a large position in event E and want to hedge against the scenario where E is true but F is false. (d) Calendar spread: You believe Event_Q1 is more likely than Event_Q2 (events about the same question but different time periods).

For each, specify the positions (event, side, quantity) in the bundle.

Exercise 18: Correlation from Market Prices

A combinatorial market with events A and B shows the following state prices: P(TT) = 0.35, P(TF) = 0.15, P(FT) = 0.10, P(FF) = 0.40.

(a) Compute P(A), P(B), and P(A AND B). (b) Are A and B positively or negatively correlated? (c) Compute the exact correlation coefficient. (d) A new trader buys shares of the (TT) state. Which direction will the correlation move?

Exercise 19: Conditional Token Arbitrage

A conditional token market has the following prices: - Token "X=T, Y=T": $0.20 - Token "X=T, Y=F": $0.25 - Token "X=F, Y=T": $0.30 - Token "X=F, Y=F": $0.25

(a) Do these prices sum to 1? If not, is there an arbitrage opportunity? (b) A complete set of all four tokens should be worth exactly $1 (since exactly one will pay out). How would you exploit the mispricing?

Exercise 20: Computational Benchmark

Write a Python function that benchmarks the time to compute LMSR prices for different numbers of events (n = 5, 10, 15, 20, 25). For each n:

(a) Measure the time to compute all state prices. (b) Measure the time to compute the marginal probability of one event. (c) Plot the results and verify the exponential growth. (d) At what n does computation exceed 1 second?

Advanced Exercises (21-30)

Exercise 21: Custom Approximation Algorithm

Design and implement a custom approximation algorithm for a combinatorial market that combines: - Partition-based exact computation for a "core" set of 6 highly correlated events. - Mean-field approximation for 14 additional weakly correlated events.

Your algorithm should: (a) Compute exact prices within the core partition. (b) Use mean-field for cross-partition queries. (c) Measure and report the approximation error by comparing to exact computation for small test cases.

Exercise 22: Belief Propagation for Markets

Implement a simple belief propagation algorithm for a tree-structured combinatorial market: - Event A affects B and C (A is parent of B and C). - Event B affects D (B is parent of D). - Event C affects E (C is parent of E).

(a) Define conditional probability tables for each edge. (b) Implement message passing from leaves to root and back. (c) Compute marginal probabilities for all events. (d) Compare to exact enumeration for this small example.

Exercise 23: LMSR-C Cost Function Proof

Prove the following properties of the combinatorial LMSR cost function:

(a) Convexity: C(q) is a convex function. (b) No arbitrage: The prices derived from C form a valid probability distribution (non-negative, sum to 1). (c) Bounded loss: The maximum loss is b * n * ln(2) for n binary events. (d) Path independence: The total cost of a sequence of trades depends only on the final share vector, not the order of trades.

Exercise 24: Conditional Market Consistency

Three conditional markets exist: - Market 1: P(Y | X) - Market 2: P(Z | X) - Market 3: P(Y | Z)

Suppose the markets report: - P(Y=T | X=T) = 0.80 - P(Z=T | X=T) = 0.70 - P(Y=T | Z=T) = 0.60

(a) Are these three conditional probabilities mutually consistent? (i.e., does there exist a joint distribution P(X, Y, Z) that generates all three?) (b) If not, what constraints are violated? (c) Design an arbitrage strategy that exploits any inconsistency.

Exercise 25: Scalability Analysis

Analyze the scalability of the following approaches for n binary events:

Fill in the table with Big-O expressions. Which approach is best for: (a) n = 10, all events correlated? (b) n = 50, events in 10 independent groups of 5? (c) n = 100, only 5 events ever traded? (d) n = 1000, weak correlations everywhere?

Exercise 26: Multi-Level Conditional Market

Design and implement a three-level conditional market: - Level 1: "Will there be a recession?" - Level 2 (conditional on Level 1): "Will unemployment exceed 8%?" - Level 3 (conditional on Level 1 and Level 2): "Will the incumbent party win re-election?"

(a) How many final tokens exist? (b) Implement the splitting and pricing logic. (c) What is P(Incumbent wins | Recession AND High unemployment)? (d) How does this compare to P(Incumbent wins | No recession AND Low unemployment)?

Exercise 27: Market Maker Loss Simulation

Simulate 10,000 trades on an LMSR-C market with 10 events. Each trade randomly selects 1-3 events and buys or sells 1-10 shares of their conjunction.

(a) Track the market maker's running profit/loss. (b) After all trades, resolve each event randomly with P(True) = 0.5. (c) Compute the market maker's final profit/loss. (d) Repeat 1000 times and plot the distribution of final profit/loss. (e) Verify that the maximum loss is consistent with the theoretical bound.

Exercise 28: Causal Inference from Market Prices

A combinatorial market has three events: Treatment (T), Biomarker (B), and Recovery (R). Market prices reveal: - P(R | T) = 0.70 - P(R | NOT T) = 0.40 - P(R | T, B) = 0.75 - P(R | T, NOT B) = 0.65 - P(R | NOT T, B) = 0.55 - P(R | NOT T, NOT B) = 0.25

(a) What is the naive "causal effect" of Treatment on Recovery? (b) Is Biomarker a confounder, mediator, or collider in the relationship between T and R? (c) Using the conditional prices, compute the adjusted causal effect controlling for Biomarker. (d) What additional market structure would you need to definitively identify the causal effect?

Exercise 29: Gas-Efficient Conditional Tokens

In a blockchain-based conditional token market, every state transition costs "gas" (computation fees). Design an optimized implementation that minimizes gas costs for:

(a) Splitting collateral into conditional tokens (should be O(1) gas, not O(2^n)). (b) Merging conditional tokens back to collateral. (c) Trading conditional tokens on an AMM. (d) Resolving the market and distributing payouts.

Describe the data structures and algorithms. You do not need to write Solidity code --- pseudocode and complexity analysis are sufficient.

Exercise 30: Full System Design

Design a complete combinatorial prediction market system for a company that wants to forecast 50 product-related events (feature launches, competitor actions, market conditions, etc.).

Your design should address: (a) Partition strategy: Which events should be in the same partition? (b) Approximation method: What method for cross-partition queries? (c) UI/UX: How do traders interact with 50 events without being overwhelmed? (d) Liquidity: How is the LMSR liquidity parameter set for each sub-market? (e) Consistency: How are cross-market arbitrage opportunities handled? (f) Resolution: How are events resolved and payouts computed?

Write a 1-2 page design document covering these points.