Random works on the basis of a seed value; create a new instance of Random with the same seed value and out come the same numbers, in the same order, every time.

This is inherent to Random; the spec demands that it works this way. Straight from the javadoc:

An instance of this class is used to generate a stream of pseudorandom numbers. The class uses a 48-bit seed, which is modified using a linear congruential formula. (See Donald Knuth, The Art of Computer Programming, Volume 2, Section 3.2.1.)

It does this (and has to, as per spec) even if you don’t bother with a seed value. If you don’t bother with it (just new Random()) you get a random seed value, but, there still is one. You can reset it even (with setSeed()).

The system is fundamentally synchronized. When explaining a spec, the moment you say ‘in the same order’, you lose the game immediately. Those words lock you into synchronizing the lot (or not doing so and having the thing fall to bits, i.e. spec dictates that unsynced access means bizarre things can occur, such as repeated values). They didn’t do that for kicks – it’s to enable that seed functionality.

But I don’t care or need it!

Great, but, that’s not how specs work. That’s why there’s ThreadLocal, which does have a seed value but each thread has its own completely independent rng and seed, or various other sources of randomness which make no promises about the reliability of the emitted sequence in the face of repeating the seed value, thus ‘freeing’ it from the shackles that that implies (Namely, that access has to be ordered, which requires locking).

Programming is hard. Abstraction is very hard.

In this specific case you thought Random is an abstraction for a concept that doesn’t have anything whatsoever to do with ordering, so why in the blazes would a lock even apply? Except, Random is an abstraction that can cover many use cases, and ‘same numbers in the same order’ is one of those use cases.

This is common: multicore performance and multicore behaviour in general ‘does not compose’ – you can’t just write components such that the concurrency of each component makes sense and is easy/obvious to use, and also have that if you slap these components together that the end result automatically has sensible behaviour and performance as well.

Alternate designs are imaginable; for example, a basic Random class or more likely interface that makes very few guarantees and locks down very little (such as: It would make no promises about concurrent behaviour at all, it would make no promises about how it works, it would neither offer a way to initialize one based off of a seed value nor would it have setSeed), and then various implementations or even a factory toolkit concept where you pass in your particular desires (such as ‘I want it to be seed based’ or ‘I want it to be as fast as possible; I will accept, as long as it is rare, that 2 concurrent threads end up getting identical values, speed is more important to me’), but that’d be a rather heavyhanded, kinda ‘overengineered’ feel, and such extremes are best left to libraries instead of the core; libraries can update and break API if it is warrented. Core can pretty much never do that.

It’s a thread contention problem as stated in the Java documentation

In other words, Since you are sharing an instance of Random to multiple threads, whenever one of the threads attempts to get the next Random number it has to “lock” the instance to perform the work and get the next number. At the same time another thread tries to generate a number with the same instance, it has to wait for the first thread to complete its work and release the “lock” before it can start for the next number.

Each instance of Random can only generate one number at a time.

With ThreadLocalRandom you eliminate that problem, because each thread uses it’s own Random instance.

EDIT: Someone pointed out this doesn’t explain why Random works in that way, in short, this is because of the specs. An other answer explained it well, but simply put Random guarantees that given the same seed and the same method calls in the same order will always result in the same output. This could not be achieved if the threads could work on the instance at the same time because you would mess up with the ordering.

As to why they chose to design the specs that way, this is a common approach in multiple languages because generating the same numbers between multiple program runs is a common use case that would otherwise be hard to implement without the use of Random.

EDIT:
It’s been a while since I touched any Java and remembered that there was this feature of class instances getting synchronized between threads automatically, but I incorrectly assumed this was the default behavior of any class when multiple threads were running.
To be honest I don’t know why they chose to make it synchronized, it’s not the only class made like that either. They made a choice and went with it. It probably would’ve made more sense to just make it non-thread-safe, but that’s not how it is.