levers   126

« earlier     later »

Kolmogorov's zero–one law - Wikipedia
In probability theory, Kolmogorov's zero–one law, named in honor of Andrey Nikolaevich Kolmogorov, specifies that a certain type of event, called a tail event, will either almost surely happen or almost surely not happen; that is, the probability of such an event occurring is zero or one.

tail events include limsup E_i
math  probability  levers  limits  discrete  wiki  reference  nibble 
february 2017 by nhaliday
Dvoretzky's theorem - Wikipedia
In mathematics, Dvoretzky's theorem is an important structural theorem about normed vector spaces proved by Aryeh Dvoretzky in the early 1960s, answering a question of Alexander Grothendieck. In essence, it says that every sufficiently high-dimensional normed vector space will have low-dimensional subspaces that are approximately Euclidean. Equivalently, every high-dimensional bounded symmetric convex set has low-dimensional sections that are approximately ellipsoids.

math  math.FA  inner-product  levers  characterization  geometry  math.MG  concentration-of-measure  multi  q-n-a  overflow  intuition  examples  proofs  dimensionality  gowers  mathtariat  tcstariat  quantum  quantum-info  norms  nibble  high-dimension  wiki  reference  curvature  convexity-curvature  tcs 
january 2017 by nhaliday
Wald's equation - Wikipedia
important identity that simplifies the calculation of the expected value of the sum of a random number of random quantities
math  levers  probability  wiki  reference  nibble  expectancy  identity 
january 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 
january 2017 by nhaliday
Computational Complexity: Favorite Theorems: The Yao Principle
The Yao Principle applies when we don't consider the algorithmic complexity of the players. For example in communication complexity we have two players who each have a separate half of an input string and they want to compute some function of the input with the minimum amount of communication between them. The Yao principle states that the best probabilistic strategies for the players will achieve exactly the communication bounds as the best deterministic strategy over a worst-case distribution of inputs.

The Yao Principle plays a smaller role where we measure the running time of an algorithm since applying the Principle would require solving an extremely large linear program. But since so many of our bounds are in information-based models like communication and decision-tree complexity, the Yao Principle, though not particularly complicated, plays an important role in lower bounds in a large number of results in our field.
tcstariat  tcs  complexity  adversarial  rand-approx  algorithms  game-theory  yoga  levers  communication-complexity  random  lower-bounds  average-case  nibble  org:bleg 
january 2017 by nhaliday
Carathéodory's theorem (convex hull) - Wikipedia
- any convex combination in R^d can be pared down to at most d+1 points
- eg, in R^2 you can always fit a point in convex hull in a triangle
tcs  acm  math.MG  geometry  levers  wiki  reference  optimization  linear-programming  math  linear-algebra  nibble  spatial  curvature  convexity-curvature 
january 2017 by nhaliday

« earlier    later »

related tags

6dof  aaronson  academia  accuracy  ace  acm  acmtariat  adna  adversarial  aero  agri-mindset  algebra  algorithms  analogy  aphorism  apollonian-dionysian  applicability-prereqs  applications  approximation  archaeology  architecture  arrows  article  assembly  atoms  autism  average-case  base  ben-recht  bicycle  big-list  big-picture  bike  bikes  biking  binomial  bio  biodet  bioinformatics  bonferroni  boolean-analysis  borel-cantelli  brake  brakelevers  brakes  branches  building  calculation  calculations  cameramounts  cameras  campagnolo  campy  cartoons  case  cassette  castle  causation  cbr250  cbr500  chain  characterization  chart  cheatsheet  checklists  clever-rats  cliometrics  coding-theory  coloring  combo-optimization  communication-complexity  comparison  complexity  compressed-sensing  concentration-of-measure  concept  conceptual-vocab  concrete  confluence  confusion  convergence  convexity-curvature  cool  coral  counterexample  counterweight  cs  curvature  cycling  data  database  deep-learning  degrees-of-freedom  dials  differential  dimensionality  direction  discrete  discussion  disease  distribution  door  duality  dura  ejector  electric  embeddings  ends-means  enhancement  entanglement  entropy-like  erdos  ergo  ergodic  estimate  evolution  examples  expectancy  explanans  explanation  exposition  extratricky  extrema  features  fields  filming  filmmaking  finiteness  fisher  fittslaw  fixed-point  flash  flat  flattop341  flickr  flight  force  formulas  fourier  frontier  g5_machines  game-theory  gavisti  gcta  gear  gearing  gears  gene-flow  generalization  genetics  genomics  geography  geometry  giants  gowers  gradient-descent  graph-theory  graphical-models  graphs  gravity  grip  ground-up  gwas  gwern  hardware  hari-seldon  heuristic  hi-order-bits  high-dimension  homo-hetero  homogeneity  honda  howto  ideas  identity  iidness  impact  index  indexed  indexing  inference  information-theory  inner-product  insight  interdisciplinary  intuition  invariance  inverse  iterative-methods  ixd  jargon  junior  knobs  knowledge  learning-theory  lecture-notes  leverage  lexical  lifts-projections  limits  linear-algebra  linear-programming  linearity  liner-notes  links  list  local-global  logic  lower-bounds  machine-learning  magnitude  manifolds  map-territory  markov  martingale  matching  math.ac  math.ag  math.ca  math.co  math.ds  math.fa  math.gn  math.gr  math.mg  math.nt  math  mathtariat  measure  measurement  mechanics  mental-math  meta:math  metabuch  metameta  methodology  metric-space  michael-jordan  missing-heritability  ml-map-e  model-class  models  moments  monotonicity  motion  motivation  motorcycle  mrtz  mtb  multi  multiplicative  mutation  neurons  nibble  nitty-gritty  norms  novelty  objektbuch  off-convex  oly  optimization  order-disorder  orders  org:bleg  org:edu  oscillation  overflow  p:***  p:whenever  pac  paradox  parts  pdf  perturbation  physics  pigeonhole-markov  pivots  poast  polynomials  pop-structure  population-genetics  positivity  pragmatic  pre-2013  prioritizing  probabilistic-method  probability  problem-solving  process  products  proofs  properties  pseudorandomness  psychiatry  pulls  q-n-a  qra  qtl  quantifiers-sums  quantitative-qualitative  quantum-info  quantum  quixotic  rand-approx  random-matrices  random  ratty  rec-math  red  reduction  reference  repair  research  retrofit  rigidity  rigor  roadmap  robust  s:***  s:**  s:null  sampling  scaling-up  schematic  scholar-pack  scitariat  seat  selection  sensitivity  series  servomotors  shannon  shift  shifters  shifting  shimano  signum  simplex  simulation  skeleton  slides  smoothness  soft-question  sparsity  spatial  spearhead  spectral  speed  speeds  spreading  stackex  state  stats  stewart  sti  stirling  stochastic-processes  street-fighting  structure  study  studying  stylized-facts  summary  symmetry  synthesis  table  talks  tcs  tcstariat  techtariat  telos-atelos  thermo  things  thinking  thurston  tidbits  time  tip-of-tongue  tire  toolkit  top-n  topology  toread  track-record  tractors  trees  tricki  tricks  tube  tutorial  unit  upgrading  variance-components  video  videos  visual-understanding  volo-avolo  von-neumann  waves  weights  west-hunter  wiki  work  wormholes  worrydream  xcite  yoga  youtube  zooming  🌞  🎓  👳  🔬 

Copy this bookmark: