User contributions for Etone

Results for Etone talk block log uploads logs
A user with 1,279 edits. Account created on 30 August 2022.
Jump to navigation Jump to search
Search for contributionsExpandCollapse
⧼contribs-top⧽
⧼contribs-date⧽
(newest | oldest) View (newer 50 | ) (20 | 50 | 100 | 250 | 500)

16 September 2026

15 September 2026

  • 12:0012:00, 15 September 2026 diff hist +10,715 N 高级算法 (Fall 2026)/Conditional expectations Created page with "= Conditional Expectations = The '''conditional expectation''' of a random variable <math>Y</math> with respect to an event <math>\mathcal{E}</math> is defined by :<math> \mathbf{E}[Y\mid \mathcal{E}]=\sum_{y}y\Pr[Y=y\mid\mathcal{E}]. </math> In particular, if the event <math>\mathcal{E}</math> is <math>X=a</math>, the conditional expectation :<math> \mathbf{E}[Y\mid X=a] </math> defines a function :<math> f(a)=\mathbf{E}[Y\mid X=a]. </math> Thus, <math>\mathbf{E}[Y\mid..." current
  • 11:5911:59, 15 September 2026 diff hist +41,013 N 高级算法 (Fall 2026)/Concentration of measure Created page with "=Chernoff Bound= Suppose that we have a fair coin. If we toss it once, then the outcome is completely unpredictable. But if we toss it, say for 1000 times, then the number of HEADs is very likely to be around 500. This phenomenon, as illustrated in the following figure, is called the '''concentration''' of measure. The Chernoff bound is an inequality that characterizes the concentration phenomenon for the sum of independent trials. File:Coinflip.png|border|450px|cent..." current
  • 11:5911:59, 15 September 2026 diff hist +165 高级算法 (Fall 2026) →Lecture Notes

9 September 2026

8 September 2026

7 September 2026

  • 10:1310:13, 7 September 2026 diff hist +5,755 N 高级算法 (Fall 2026)/Basic deviation inequalities Created page with "=Markov's Inequality= One of the most natural information about a random variable is its expectation, which is the first moment of the random variable. Markov's inequality draws a tail bound for a random variable from its expectation. {{Theorem |Theorem (Markov's Inequality)| :Let <math>X</math> be a random variable assuming only nonnegative values. Then, for all <math>t>0</math>, ::<math>\begin{align} \Pr[X\ge t]\le \frac{\mathbf{E}[X]}{t}. \end{align}</math> }} {{Proo..." current
  • 10:1310:13, 7 September 2026 diff hist +15,812 N 高级算法 (Fall 2026)/Limited independence Created page with "= <math>k</math>-wise independence = Recall the definition of independence between events: {{Theorem |Definition (Independent events)| :Events <math>\mathcal{E}_1, \mathcal{E}_2, \ldots, \mathcal{E}_n</math> are '''mutually independent''' if, for any subset <math>I\subseteq\{1,2,\ldots,n\}</math>, ::<math>\begin{align} \Pr\left[\bigwedge_{i\in I}\mathcal{E}_i\right] &= \prod_{i\in I}\Pr[\mathcal{E}_i]. \end{align}</math> }} Similarly, we can define independence between..." current
  • 10:1210:12, 7 September 2026 diff hist +49,292 N 高级算法 (Fall 2026)/Hashing and Sketching Created page with "=Balls into Bins= The following is the so-called balls into bins model. Consider throwing <math>m</math> balls into <math>n</math> bins uniformly and independently at random. This is equivalent to a random mapping <math>f:[m]\to[n]</math>. Needless to say, random mapping is an important random model and may have many applications in Computer Science, e.g. hashing. We are concerned with the following three questions regarding the balls into bins model: * birthday problem..." current
  • 10:1210:12, 7 September 2026 diff hist +245 高级算法 (Fall 2026) →Lecture Notes

2 September 2026

17 June 2026

  • 04:0504:05, 17 June 2026 diff hist +34,076 N 组合数学 (Fall 2026)/Matching theory Created page with "== Systems of Distinct Representatives (SDR)== A '''system of distinct representatives (SDR)''' (also called a '''transversal''') for a sequence of (not necessarily distinct) sets <math>S_1,S_2,\ldots,S_m</math> is a sequence of <font color=red>''distinct''</font> elements <math>x_1,x_2,\ldots,x_m</math> such that <math>x_i\in S_i</math> for all <math>i=1,2,\ldots,m</math>. === Hall's marriage theorem === If the sets <math>S_1,S_2,\ldots,S_m</math> have a system of dist..." current
  • 04:0404:04, 17 June 2026 diff hist +141 组合数学 (Spring 2026) →Lecture Notes

20 May 2026

  • 13:3313:33, 20 May 2026 diff hist +26,029 N 组合数学 (Fall 2026)/Ramsey theory Created page with "== Ramsey's Theorem == === Ramsey's theorem for graph === {{Theorem|Ramsey's Theorem| :Let <math>k,\ell</math> be positive integers. Then there exists an integer <math>R(k,\ell)</math> satisfying: :If <math>n\ge R(k,\ell)</math>, for any coloring of edges of <math>K_n</math> with two colors red and blue, there exists a red <math>K_k</math> or a blue <math>K_\ell</math>. }} {{Proof| We show that <math>R(k,\ell)</math> is finite by induction on <math>k+\ell</math>. For the..." current
  • 13:3213:32, 20 May 2026 diff hist +137 组合数学 (Spring 2026) →Lecture Notes

13 May 2026

6 May 2026

  • 05:0105:01, 6 May 2026 diff hist +18,939 N 组合数学 (Fall 2026)/Extremal graph theory Created page with "== Forbidden Cliques == Extremal graph theory studies the problems like "how many edges that a graph <math>G</math> can have, if <math>G</math> has some property?" === Mantel's theorem === We consider a typical extremal problem for graphs: the largest possible number of edges of '''triangle-free''' graphs, i.e. graphs contains no <math>K_3</math>. {{Theorem|Theorem (Mantel 1907)| :Suppose <math>G(V,E)</math> is graph on <math>n</math> vertice without triangles. Then <m..." current
  • 05:0005:00, 6 May 2026 diff hist +158 组合数学 (Spring 2026) →Lecture Notes

17 April 2026

16 April 2026

8 April 2026

(newest | oldest) View (newer 50 | ) (20 | 50 | 100 | 250 | 500)
Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=Special:Contributions/Etone"