  Estimating frequency moments of data streams is a very well studied problem
and tight bounds are known on the amount of space that is necessary and
sufficient when the stream is adversarially ordered. Recently, motivated by
various practical considerations and applications in learning and statistics,
there has been growing interest into studying streams that are randomly
ordered. In the paper we improve the previous lower bounds on the space
required to estimate the frequency moments of a randomly ordered streams.
