The random-hyperplane collision probability

ProofIntermediate⏱ 30 minRAGlshsimhashanglerotational invariance

Theory: Vector Search — Exact and Approximate Nearest Neighbours →

Problem

Prove $\P(\sign\langle w,u\rangle\ne\sign\langle w,v\rangle) = \theta(u,v)/\pi$ for $w\sim\Ncal(0,I_d)$ , and deduce the variance of a $b$ -bit SimHash estimate of the angle.

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
Product quantisation budget arithmetic	RAG	Numerical	Beginner	30 min
Recall composes multiplicatively	RAG	Numerical	Beginner	15 min
Implement SimHash LSH and measure recall run	RAG	Coding	Advanced	3 hours
Why space-partitioning trees fail in high dimension	RAG	Proof	Advanced	30 min
The LSH amplification exponent abyss	RAG	Proof	Graduate	1 hour