Can someone explain me what are X, I and Pr in this proof ? and also why first sigma start from j=i+1?

Question

I am reading CLRS Algorithm and i saw this Theorem.

Theorem 11.2: In a hash table in which collisions are resolved by chaining, a successful search takes average-case time: theta(1+n/m) under the assumption of simple uniform hashing.

in this theorem, m => number of slots in table and n => number of elements in each slot .

and this is the proof:

Help Me Please. I can not understand this yellow parts at all :(

Answer 1

I is the Indicator function. Its value is 1 when the condition is met, and 0 otherwise.

X_ij is the indicator of hash collision. That is, X_ij == 1 when h(k_i) == h(k_j), and X_ij == 0 when h(k_i) != h(k_j).

Pr is probability. The highlighted statement means that the probability of a hash collision is 1/m.

The sum starts from i+1 because in order to find x_i, we only need to examine elements inserted after x_i. Those inserted before x_i will be located after it in the list, so the search will terminate before reaching them.