There's a random number generator in the root chain (i.e. the beacon chain) and validators are assigned shortly before validation and may require validation of any random shard. The validator can validate blocks in a "stateless" manner, meaning that they don't have to validate the entire shard but can still validate a single block (which is necessary, because if validators needed data for all shards it would destroy the scaling benefits)