Your example is inconsistent with your question: different functional forms -- exponents or no exponents?

Solution confusion: OP wrote: "I expect the best possible lower bound to be $$\frac{1}{2} \sqrt{T \log(K)}$$." ... Unfortunately, this does not seem remotely close to the exact theoretical solution. Why not put up a plot showing your calculated (theoretical or Monte Carlo approximation of the) exact solution (as k and T vary), and comparing it to your proposed best possible lower bound.

Duplicate of: math.stackexchange.com/questions/611503/…

This is standard text book material. See: Cox and Miller The Theory of Stochastic Processes

@Carlo I agree with your formulation that the probability sought is P(sample range > d). However, I get a different result.

OP wrote: The question was originally asked on math.SE. .... Not quite. The question posed on math.SE is about $n$ Uniformly random points on a disc of unit radius (i.e. of area $\pi$). The question here is about Uniformly random points on a unit square.

See also the answer to this question: math.stackexchange.com/questions/562119/… ... which provides the pmf of the difference of 2 Binomials.