The maximum of N distractor similarities

ProofAdvanced⏱ 30 minRAGmaximumsub-gaussianunion boundretrieval

Theory: Embedding Geometry and Similarity →

Problem

Prove $\E\max_{j\le N}\langle q,z_j\rangle\le\sqrt{2\log N/d}$ for independent uniform directions $z_j$ , and derive the high-probability version. Then compute the required query–document alignment for top-1 retrieval at $d = 768$ and $N = 10^3,10^6,10^9$ .

Write a complete argument. Every inequality you use should be one you could state precisely.

Solution

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Related problems

All problems

Problem	Field	Type	Difficulty	Time
Three similarities agree on the unit sphere	RAG	Proof	Foundation	15 min
When is the union bound tight?	Probability	Proof	Foundation	15 min
Generalisation for a finite class	Learning Theory	Proof	Beginner	30 min
A sufficient condition for correct retrieval	RAG	Proof	Intermediate	30 min
Measure anisotropy in an embedding space run	RAG	Coding	Intermediate	1 hour