nhaliday + pigeonhole-markov   12

Diophantine approximation - Wikipedia
- rationals perfectly approximated by themselves, badly approximated (eps~1/q) by other rationals
- irrationals well-approximated (eps~1/q^2) by rationals: https://en.wikipedia.org/wiki/Dirichlet%27s_approximation_theorem
nibble  wiki  reference  math  math.NT  approximation  accuracy  levers  pigeonhole-markov  multi  tidbits  discrete  rounding 
august 2017 by nhaliday
Evolution Runs Faster on Short Timescales | Quanta Magazine
But if more splashes of paint appear on a wall, they will gradually conceal some of the original color beneath new layers. Similarly, evolution and natural selection write over the initial mutations that appear over short timescales. Over millions of years, an A in the DNA may become a T, but in the intervening time it may be a C or a G for a while. Ho believes that this mutational saturation is a major cause of what he calls the time-dependent rate phenomenon.

“Think of it like the stock market,” he said. Look at the hourly or daily fluctuations of Standard & Poor’s 500 index, and it will appear wildly unstable, swinging this way and that. Zoom out, however, and the market appears much more stable as the daily shifts start to average out. In the same way, the forces of natural selection weed out the less advantageous and more deleterious mutations over time.
news  org:mag  org:sci  evolution  bio  nature  mutation  selection  time  methodology  stylized-facts  genetics  population-genetics  genomics  speed  pigeonhole-markov  bits  nibble  org:inst 
march 2017 by nhaliday
Count–min sketch - Wikipedia
- estimates frequency vector (f_i)
- idea:
d = O(log 1/δ) hash functions h_j: [n] -> [w] (w = O(1/ε))
d*w counters a[r, c]
for each event i, increment counters a[1, h_1(i)], a[2, h_2(i)], ..., a[d, h_d(i)]
estimate for f_i is min_j a[j, h_j(i)]
- never underestimates but upward-biased
- pf: Markov to get constant probability of success, then exponential decrease with repetition
lecture notes: http://theory.stanford.edu/~tim/s15/l/l2.pdf
- note this can work w/ negative updates. just use median instead of min. pf still uses markov on the absolute value of error.
algorithms  data-structures  sublinear  hashing  wiki  reference  bias-variance  approximation  random  tcs  multi  stanford  lecture-notes  pdf  tim-roughgarden  nibble  pigeonhole-markov  PAC 
february 2017 by nhaliday
6.896: Essential Coding Theory
- probabilistic method and Chernoff bound for Shannon coding
- probabilistic method for asymptotically good Hamming codes (Gilbert coding)
- sparsity used for LDPC codes
mit  course  yoga  tcs  complexity  coding-theory  math.AG  fields  polynomials  pigeonhole-markov  linear-algebra  probabilistic-method  lecture-notes  bits  sparsity  concentration-of-measure  linear-programming  linearity  expanders  hamming  pseudorandomness  crypto  rigorous-crypto  communication-complexity  no-go  madhu-sudan  shannon  unit  p:**  quixotic 
february 2017 by nhaliday
5/8 bound in group theory - MathOverflow
very elegant proof (remember sum d_i^2 = |G| and # irreducible rep.s = # conjugacy classes)
q-n-a  overflow  math  tidbits  proofs  math.RT  math.GR  oly  commutativity  pigeonhole-markov  nibble  shift 
january 2017 by nhaliday
(Gil Kalai) The weak epsilon-net problem | What's new
This is a problem in discrete and convex geometry. It seeks to quantify the intuitively obvious fact that large convex bodies are so “fat” that they cannot avoid “detection” by a small number of observation points.
gowers  mathtariat  tcstariat  tcs  math  concept  rounding  linear-programming  research  open-problems  geometry  math.CO  magnitude  probabilistic-method  math.MG  discrete  nibble  org:bleg  questions  curvature  pigeonhole-markov  convexity-curvature 
january 2017 by nhaliday

bundles : abstractmathproblem-solving

related tags

academia  accuracy  acm  acmtariat  alg-combo  algorithms  apollonian-dionysian  applications  approximation  arrows  atoms  bias-variance  big-picture  bio  bits  chart  checklists  clever-rats  coarse-fine  coding-theory  communication-complexity  commutativity  complexity  concentration-of-measure  concept  conceptual-vocab  confluence  convexity-curvature  course  crypto  curvature  data-structures  deep-learning  differential  dimensionality  discrete  distribution  ends-means  entropy-like  estimate  evolution  expanders  extrema  fedja  fields  finiteness  fourier  genetics  genomics  geometry  gowers  graph-theory  graphical-models  graphs  ground-up  hamming  hashing  hi-order-bits  high-dimension  homogeneity  ideas  impact  information-theory  init  inner-product  intuition  knowledge  lecture-notes  levers  limits  linear-algebra  linear-programming  linearity  list  machine-learning  madhu-sudan  magnitude  manifolds  martingale  math  math.AG  math.CA  math.CO  math.GN  math.GR  math.MG  math.NT  math.RT  mathtariat  measure  meta:math  metabuch  metameta  methodology  mit  model-class  multi  mutation  nature  news  nibble  no-go  novelty  oly  open-problems  optimization  org:bleg  org:inst  org:mag  org:sci  orourke  overflow  p:**  p:***  PAC  paradox  pdf  pigeonhole-markov  polynomials  population-genetics  pragmatic  pre-2013  prioritizing  probabilistic-method  probability  problem-solving  proofs  pseudorandomness  q-n-a  questions  quixotic  random  ratty  reference  research  rigorous-crypto  roadmap  rounding  s:**  s:***  scholar-pack  selection  series  shannon  shift  skeleton  smoothness  soft-question  sparsity  spatial  spectral  speed  stanford  stochastic-processes  studying  stylized-facts  sublinear  synthesis  tcs  tcstariat  telos-atelos  tidbits  tim-roughgarden  time  toolkit  top-n  topology  track-record  tricki  unit  visual-understanding  wiki  yoga  🎓  👳 

Copy this bookmark: