Hard distribution & Easy distribution

< List of probability distributions < Hard distribution & Easy distribution

What is a hard distribution?

A “hard distribution” is so-called because it can be difficult to identify the distribution, or work with components or data points. The opposite is an “easy distribution.”

For example, computer models can be classified as “hard” or “harder” depending on their complexity and how well they model data. If model B is harder than C, that means the best algorithm for B does worse than the best algorithm for C.

hard distribution / easy distribution:  example of a nearest neighbor algorithm
Some algorithms, such as this nearest neighbor algorithm, are easier than others.

Hard distribution and hardness examples

Hardness is a measure of either sampling complexity or the complexity of computing a distribution function:

  • Ting et al. define a hard distribution as one that is hard for a DBSCAN density-based clustering algorithm to identify all the clusters in the distribution [1].
  • Rochetto et al. [2] describe hard distributions as those that are conjectured to be difficult to sample without the use of quantum computing.
  • Markov Chain Monte Carlo (MCMC) can sample from a hard distribution that can’t be explicitly written out; Often we can’t compute simulations for very large distribution because a Markov Chain has too many states; it could take a computer eons to calculate some of these problems. The workaround is to simulate the Markov Chain for many iterations until a “good” state solution is found [3].

References

  1. Ting et. al. August 2016. Overcoming Key Weaknesses of Distance-based Neighbourhood Methods using a Data Dependent Dissimilarity Measure. Conference: 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD ’16). DOI: 10.1145/2939672.2939779
  2. Rocchetto, A., Grant, E., Strelchuk, S. et al. Learning hard quantum distributions with variational autoencoders. npj Quantum Inf 4, 28 (2018). https://doi.org/10.1038/s41534-018-0077-z
  3. Tsum A. Probability & Statistics with Applications to Computing. Chapter 9: Applications to Computing. 9.6: Markov Chain Monte Carlo (MCMC).

 


Comments? Need to post a correction? Please Contact Us.

Leave a Comment