Validators are actually miners, and they aren't chosen at random.
Now we know that there's this block chain, and that new blocks can only be added by "validators" that are selected every ten minutes. These validators are knows as miners.
But how does the bitcoin protocol select who gets to validate the new blocks that are being created, especially given that the network is completely decentralized?
This brings us to the second incredible innovation that bitcoin made, a system called Proof-of-Work (PoW for short). Bitcoin selects the next miner based on having everyone solve an incredibly computationally expensive mathematical puzzle (technical details at the bottom). Every time a block is created, a new mathematical puzzle that should take approximately ten minutes to solve, is assigned to everyone in the network. After the puzzle is out there, every miner runs their machines furiously in an effort to be the first to solve it, and the first person who does gets the honor of being the validator for that round. There's no way to predict which miner will be the first to solve it, so every miner has an equal chance (assuming they're using the same hardware).
What do you get when you validate a block? A few things:
Because the person who solves the puzzle first gets bitcoin for his service, the act of solving the puzzle is called mining.
You might wonder: Why does the puzzle always takes ten minutes to solve?
The answer is that the network continuously adjusts the difficulty of the puzzles so that the amount of time it takes the network to solve them is approximately ten minutes. For example, if the last five puzzles have been solved in two minutes each, everyone on the network would start demanding puzzles that are 5x as difficult to solve, and rejecting blocks that don't solve these more difficult puzzles.
Note that this happens in a completely decentralized way. Because the difficulty of the puzzle is defined based on the previous blocks in the chain, and because all of these blocks include timestamps, everyone knows exactly what kind of puzzle to work on, and what kind of puzzle to accept by looking at the previous blocks. There's no need for a central authority to assign the puzzle. The increasing difficulty in the puzzle leads everyone with an interest in mining to continuously improve their hardware so they can solve the puzzles faster than everyone else and capture the block rewards and fees.
Small technical note: For the computer scientists and mathematicians, the "puzzle" referred to above effectively boils down to finding a nonce that satisfies hash(last_block_hash, nonce) < X, where the lower X is, the more nonces you have to try, and therefore the more difficult the problem is. In general, the algorithm demands that X start with a certain number of zeroes. A hash is just a way to convert a chunk of data into an alphanumeric string with a fixed length — this string is called a hash of the data, and the function that converts the data to the string is called a hashing function.
Miners are heavily invested in the network. They are incentivized to keep the network functioning properly since they want the value of Bitcoin to keep appreciating. If the network was compromised in some way, then the value of Bitcoin would tank and their resulting electricity costs and the specialized hardware miners use would no longer be economical.
Why can't a miner simply change the contents of old blocks, in an attempt to sabotage the network?
The reason is actually quite clever. Each block in the blockchain contains a hash of the previous block, so if anyone tries to change any of the previous blocks, it will invalidate the hash of any of the subsequent blocks in the blockchain. So the miner would have to recompute all the puzzles starting from the block he mined to make sure all the hashes match up, which is cryptographically quite infeasible.
Because there's a strong incentive to be the creator of new blocks, in the form of fees and block rewards, and because the network constantly adjusts the difficulty to make the puzzles you have to solve harder and harder, the bitcoin network ends up being incredibly expensive to operate. At the time of this writing, ~1,800 bitcoins are being given out in block reward per day, which at ~$13,000 per bitcoin is roughly $23 million. That means that it's effectively worth it to spend millions of dollars a day on useless computation if it means you can be the fastest. However, some other coins have innovated to make the process of validating blocks more efficient and less wasteful.