I don't think so. I think the point of the removal in X <- X \ {a_i} With probability p, X <- X U {a_i} is that afterwards a_i is in X with probability p

I don't think so. I think the point of the removal in X <- X \ {a_i} With probability p, X <- X U {a_i} is that afterwards a_i is in X with probability p regardless of how many times it occurs in the stream.