pigeonhole-markov   11

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

related tags

accuracy  acm  alg-combo  algorithms  approximation  bias-variance  bio  bits  coarse-fine  coding-theory  communication-complexity  commutativity  complexity  concentration-of-measure  concept  convexity-curvature  course  crypto  curvature  data-structures  dimensionality  discrete  elegance  estimate  evolution  expanders  extrema  fedja  fields  fourier  genetics  genomics  geometry  gowers  graph-theory  graphs  ground-up  hamming  hashing  high-dimension  information-theory  init  inner-product  intuition  lecture-notes  levers  limits  linear-algebra  linear-programming  linearity  madhu-sudan  magnitude  math.ag  math.co  math.gr  math.mg  math.nt  math.rt  math  mathtariat  measure  methodology  mit  multi  mutation  nature  news  nibble  no-go  novelty  oly  open-problems  org:bleg  org:inst  org:mag  org:sci  orourke  overflow  p:**  pac  paradox  pdf  polynomials  population-genetics  probabilistic-method  probability  proofs  pseudorandomness  q-n-a  questions  quixotic  random  reference  research  rigorous-crypto  rounding  s:**  selection  shannon  shift  soft-question  sparsity  spatial  speed  stanford  stylized-facts  sublinear  tcs  tcstariat  tidbits  tim-roughgarden  time  unit  visual-understanding  wiki  yoga 

Copy this bookmark:



description:


tags: