In this work, we study the distinguishability of random states drawn from the Wishart ensemble as well as black hole microstates. We compute the relative entropy and many generalizations, including the Petz Rényi relative entropy, sandwiched Rényi relative entropy, fidelities, and trace distances. These generalized quantities are able to teach us about new structures in the space of random states and black hole microstates where the von Neumann and relative entropies were insufficient. We further generalize to generic random tensor networks where new phenomena arise due to the locality in the networks. These phenomena sharpen the relationship between holographic states and random tensor networks. We discuss the implications of our results on the black hole information problem using replica wormholes, specifically the state dependence (hair) in Hawking radiation. Understanding the differences between Hawking radiation of distinct evaporating black holes is an important piece of the information problem that was not addressed by entropy calculations using the island formula. We interpret our results in the language of quantum hypothesis testing and the subsystem eigenstate thermalization hypothesis (ETH), deriving that chaotic (including holographic) systems obey subsystem ETH for all subsystems less than half the total system size.