nhaliday + probabilistic-method   23

st.statistics - Lower bound for sum of binomial coefficients? - MathOverflow
- basically approximate w/ geometric sum (which scales as final term) and you can get it up to O(1) factor
- not good enough for many applications (want 1+o(1) approx.)
- Stirling can also give bound to constant factor precision w/ more calculation I believe
- tighter bound at Section 7.3 here: http://webbuild.knu.ac.kr/~trj/Combin/matousek-vondrak-prob-ln.pdf
q-n-a  overflow  nibble  math  math.CO  estimate  tidbits  magnitude  concentration-of-measure  stirling  binomial  metabuch  tricki  multi  tightness  pdf  lecture-notes  exposition  probability  probabilistic-method  yoga 
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
probability - How to prove Bonferroni inequalities? - Mathematics Stack Exchange
- integrated version of inequalities for alternating sums of (N choose j), where r.v. N = # of events occuring
- inequalities for alternating binomial coefficients follow from general property of unimodal (increasing then decreasing) sequences, which can be gotten w/ two cases for increasing and decreasing resp.
- the final alternating zero sum property follows for binomial coefficients from expanding (1 - 1)^N = 0
- The idea of proving inequality by integrating simpler inequality of r.v.s is nice. Proof from CS 150 was more brute force from what I remember.
q-n-a  overflow  math  probability  tcs  probabilistic-method  estimate  proofs  levers  yoga  multi  tidbits  metabuch  monotonicity  calculation  nibble  bonferroni  tricki  binomial  s:null  elegance 
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
Borel–Cantelli lemma - Wikipedia
- sum of probabilities finite => a.s. only finitely many occur
- "<=" w/ some assumptions (pairwise independence)
- classic result from CS 150 (problem set 1)
wiki  reference  estimate  probability  math  acm  concept  levers  probabilistic-method  limits  nibble  borel-cantelli 
november 2016 by nhaliday

bundles : abstractmathpatternsproblem-solvingtcs

related tags

accretion  acm  acmtariat  additive  additive-combo  advice  alg-combo  algebra  algorithms  aphorism  arrows  big-list  big-picture  binomial  bits  bonferroni  books  boolean-analysis  borel-cantelli  caching  calculation  cartoons  characterization  chart  circuits  clever-rats  coding-theory  coloring  combo-optimization  communication-complexity  complexity  concentration-of-measure  concept  constraint-satisfaction  convexity-curvature  course  crypto  curvature  dan-luu  definition  dimensionality  direction  discrete  discussion  elegance  embeddings  emergent  engineering  entropy-like  estimate  existence  expanders  expectancy  expert  expert-experience  exposition  extrema  fields  fourier  geometry  gowers  graph-theory  graphs  ground-up  hamming  hi-order-bits  high-dimension  homo-hetero  identity  information-theory  init  inner-product  intersection  intersection-connectedness  intuition  knowledge  lecture-notes  lens  levers  limits  linear-algebra  linear-programming  linearity  list  local-global  lower-bounds  madhu-sudan  magnitude  markov  math  math.AG  math.AT  math.CA  math.CO  math.FA  math.MG  math.NT  math.RT  mathtariat  memory-management  metabuch  metameta  mit  monotonicity  monte-carlo  multi  nibble  no-go  novelty  oly  open-problems  org:bleg  org:edu  org:inst  os  overflow  p:**  p:whenever  paradox  pdf  performance  pigeonhole-markov  polynomials  princeton  probabilistic-method  probability  problem-solving  programming  proofs  pseudorandomness  q-n-a  quantifiers-sums  questions  quixotic  rand-approx  random  ratty  reading  recommendations  reference  reflection  relaxation  research  rigidity  rigorous-crypto  rounding  s:**  s:***  s:null  separation  shannon  shift  skeleton  smoothness  soft-question  sparsity  spatial  stanford  stirling  symmetry  synchrony  synthesis  systems  tcs  tcstariat  techtariat  tidbits  tightness  tim-roughgarden  toolkit  top-n  tricki  tricks  uniqueness  unit  valiant  washington  wigderson  wiki  wisdom  yoga  👳 

Copy this bookmark: