Calculate centiles of distances between random pairs in a dataset.

    This an alternative to the median kNN distance for setting the kernel
    length scale.

def pair_distance_centile(X, centile, max_pairs=5000):
    """
    Calculate centiles of distances between random pairs in a dataset.

    This an alternative to the median kNN distance for setting the kernel
    length scale.
    """
    N = X.shape[0]
    n_pairs = min(max_pairs, N**2)
    # randorder1 = np.random.permutation(N)
    # randorder2 = np.random.permutation(N)

    dists = np.zeros(n_pairs)

    for i in range(n_pairs):
        pair = np.random.randint(0, N, 2)
        pairdiff = X[pair[0], :]-X[pair[1], :]
        dists[i] = np.dot(pairdiff, pairdiff.T)
    dists.sort()

    out = dists[int(n_pairs*centile/100.)]
    return np.sqrt(out)