Computing expected values directly can be problematic, but they can often be computed based on probabilities of events instead. For example, in the case of this problem, if we let ~P_i~ be the probability that exactly ~i~ different houses will have been TP-ed after all ~M~ passes, then the expected number of different houses to be TP-ed is ~\sum_{i=0}^N i \cdot P_i~.

Now, how can we compute these ~P~ values? We can use dynamic programming. Let ~DP[p][h]~ be the probability that exactly ~h~ houses will have been TP-ed after ~p~ passes. For starters, we know that ~DP[0][0] = 1~, and ~DP[0][1 \dots N] = 0~. From a given state ~(p, h)~, there are only ~3~ possible transitions to consider: whether the ~(p+1)~-th pass results in ~0~, ~1~, or ~2~ additional houses getting TP-ed (leading to states ~(p+1, h)~, ~(p+1, h+1)~, or ~(p+1, h+2)~). We'll need to compute the probability of each of these ~3~ transitions occurring. For starters, there are ~t = \frac{N(N-1)}{2}~ total possible pairs of houses, and if ~h~ houses have been TP-ed so far, then ~h_2 = N-h~ houses have not.

In order for zero new houses to be TP-ed, both targeted houses must have already been TP-ed. The number of such houses is ~c_0 = \frac{h(h-1)}{2}~. Therefore, the probability of this transition is ~\frac{c_0}{t}~. As a result, we add ~DP[p][h] \times \frac{c_0}{t}~ onto ~DP[p+1][h]~.

Similarly, there are ~c_1 = h \times h_2~ pairs of targeted houses which would result in ~1~ new house getting TP-ed, and there are ~c_2 = \frac{h_2(h_2-1)}{2}~ pairs which result in ~2~ new houses getting TP-ed. In the same way, we can add ~DP[p][h] \times \frac{c_1}{t}~ onto ~DP[p+1][h+1]~, and ~DP[p][h] \times \frac{c_2}{t}~ onto ~DP[p+1][h+2]~.

Finally, once we've considered all states for ~p = 0 \dots (M-1)~ and ~h = 0 \dots N~, we'll have populated the whole ~DP~ array. There are ~\mathcal O(NM)~ states and only a constant number (~3~) of transitions from each state, meaning that the time complexity of this algorithm is ~\mathcal O(NM)~. For each ~i~, ~P_i = DP[M][i]~, so we can proceed to calculate the expected value as described initially.

This problem can also be solved in ~\mathcal O(1)~ with some more advanced math. For any given house, ~N-1~ pairs of houses result in it getting TP-ed on any given pass. Therefore, the probability of it getting TP-ed on any given pass is ~\frac{N-1}{t} = \frac{N-1}{\left(\frac{N(N-1)}{2}\right)} = \frac 2 N~, and the probability of it not getting TP-ed is therefore ~1-\frac 2 N~. As such, the probability of any given house not getting TP-ed at all across all ~M~ passes is ~(1-\frac 2 N)^M~. Due to the property of linear expectation, the expected number of houses which won't get TP-ed at all is simply ~N~ times that value. Thus, the expected number of houses which will get TP-ed is ~N-N(1-\frac 2 N)^M~.