Not quite that bad - if song selection is truly random, it’s “only” one chance in 36,000,000, assuming the co-worker also has 6000 songs on his device. The chance that device A will play song X at any time is 1 in 6000. The chance that device B will play song X at any (same or other) time is 1 in 6000. Now if you want to include the chances that song X prior to that was not played on either device A or B for a specific very large number of plays, it gets very complicated very fast!
I guess it would be if random and not a song repeated.