Briefly, the reason this holds is as follows: in the regime when d is small ( √ d = o(log 2 n)), any word vector v w and discourse c satisfies that , and since E [1F ] = exp(−Ω(log 2 n)), the claim follows directly; In the regime when d is large ( √ d = Ω(log 2 n)), we can use concentration inequalities to show that except with a small probability exp(−Ω(d)) = exp(−Ω(log 2 n)), a uniform sample from the sphere behaves equivalently to sampling all of the coordinates from a standard Gaussian distribution with mean 0 and variance 1 d , in which case the claim is not too difficult to show using Gaussian tail bounds.
it suffices to only consider (A.3).