Random numbers in linq queries

Is it true that random data inside a lazy statement might get evaluated differently at runtime? With the following code, I see "wow" printed to the console many times. However, if I force the result of the query (i.e. call ToList() on xs and ys), things seem to work fine.

    public static void Main(string[] args)
    {
        var generator = new Random();
        var xs = from x in Enumerable.Range(0, 20000)
                 select generator.Next();

        var ys = from y in Enumerable.Range(0, 5000)
                 select generator.Next();

        foreach (var x in xs)
        {
            var q1 = from y in ys where y > x select y;
            var q2 = from y in ys where y > x select y;

            if (!q1.SequenceEqual(q2))
                Console.WriteLine("wow!");
        }

        Console.WriteLine("done");
        Console.ReadLine();

    }

I suspect that this has to do with the fact that linq queries are "lazy". Is this accurate?