On: Computer scientists invent an efficient new way to count

[edflsafoiewq]

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.