A lower bound for the discrepancy of a random point set

We show that there are constants k,K>0k,K>0 such that for all N,s∈NN,s∈N, s≤Ns≤N, the point set consisting of NN points chosen uniformly at random in the ss-dimensional unit cube [0,1]s[0,1]s with probability at least 1−e−ks1−e−ks admits an axis-parallel rectangle [0,x]⊆[0,1]s[0,x]⊆[0,1]s containing KsN points more than expected. Consequently, the expected star discrepancy of a random point set is of order s/N.