Homework 3
Due Date: Tuesday, November 3, 2026 at 11:59pm
Submission: Single PDF on Gradescope
Download: hw_03.pdf
Instructions & Course Policies
- Collaboration Policy: You are encouraged to work in groups of up to three students. However, each student must write up their solutions completely independently in their own words. You must explicitly list all group members and external resources consulted on the first page of your submission.
- AI and Other Resources: You are encouraged to use AI agents to help format your solutions, and may also consult them about the mathematics. Declare all textbooks, papers, websites, and AI tools consulted, and explain how you used them, in a footnote or bibliography.
- Submission: Solutions must be typeset in LaTeX and submitted as a single PDF on Gradescope. Start each problem on a new page.
- Clarity and Rigor: Define your random variables and justify each use of independence, conditioning, and a tail inequality. You may use a preceding subpart’s stated conclusion even if you have not proved it. Hints are suggestions, not additional requirements.
- Review Parts: Parts marked Review revisit material from the lecture notes. Reconstruct the argument in your own words and justify the requested details; citing a result alone does not replace a requested proof. These parts carry the stated points and are required within your chosen problem. Review and extension also asks for an additional application or example.
- Grading: This problem set contains 4 problems, each worth 100 points, for a total of 100 points. You have to solve only one problem. You are encouraged to think about all of them, as they are fair game for the midterm.
Problems
- Problem 1: Exposure Martingales [100 pts]
- Problem 2: The Power of Two Choices [100 pts]
- Problem 3: Learning from a Stream [100 pts]
- Problem 4: Estimating Frequency Moments [100 pts]