随机算法 (Fall 2015) and Standard error: Difference between pages

From TCS Wiki
(Difference between pages)
Jump to navigation Jump to search
imported>Etone
 
imported>Auntof6
m (Typo fixing and/or general cleanup using AWB)
 
Line 1: Line 1:
{{Infobox
[[Image:standard deviation diagram.svg||325px|thumb|For a value that is sampled with an unbiased [[normal distribution|normally distributed]] error, the above depicts the proportion of samples that would fall between 0, 1, 2, and 3 standard deviations above and below the actual value.]]
|name        = Infobox
|bodystyle    =
|title        = <font size=3>随机算法
<br>Randomized Algorithms</font>
|titlestyle  =


|image        =
The '''standard error''' is the [[standard deviation]] of the [[sampling distribution]] of a [[statistic]].<ref>Everitt B.S. 2003. ''The Cambridge Dictionary of Statistics'', CUP. ISBN 0-521-81099-X</ref> The term may also be used for an estimate (good guess) of that standard deviation taken from a [[Sample (statistics)|sample]] of the whole group.
|imagestyle  =
|caption      =
|captionstyle =
|headerstyle  = background:#ccf;
|labelstyle  = background:#ddf;
|datastyle    =


|header1 =Instructor
The [[mean|average]] of some part of a group (called a sample) is the usual way to estimate the average for the whole group. It is often too hard or costs too much money to measure the whole group. But if a different sample is measured, it will have an average that is a little bit different from the first sample. The '''standard error of the mean''' is a way to know how close the average of the sample is to the average of the whole group. It is a way to know how sure you can be about the average from the sample.
|label1  =
|data1  =
|header2 =
|label2  =
|data2  = 尹一通
|header3 =
|label3  = Email
|data3  = yitong.yin@gmail.com  yinyt@nju.edu.cn 
|header4 =
|label4= office
|data4= 计算机系 804
|header5 = Class
|label5  =
|data5  =
|header6 =
|label6  = Class meetings
|data6  = Friday, 4pm-6pm <br> 仙I-206
|header7 =
|label7  = Place
|data7  =
|header8 =
|label8  = Office hours
|data8  = Tuesday, 2-4pm <br>计算机系 804
|header9 = Textbooks
|label9  =
|data9  =
|header10 =
|label10  =
|data10  = [[File:MR-randomized-algorithms.png|border|100px]]
|header11 =
|label11  =
|data11  = Motwani and Raghavan. <br>''Randomized Algorithms''.<br> Cambridge Univ Press, 1995.
|header12 =
|label12  =
|data12  = [[File:Probability_and_Computing.png|border|100px]]
|header13 =
|label13  =
|data13  =  Mitzenmacher and Upfal. <br>''Probability and Computing: Randomized Algorithms and Probabilistic Analysis''. <br> Cambridge Univ Press, 2005.
|belowstyle = background:#ddf;
|below =
}}


This is the page for the class ''Randomized Algorithms'' for the Fall 2015 semester. Students who take this class should check this page periodically for content updates and new announcements.  
In real measurements, the true value of the standard deviation of the mean for the whole group is usually not known. So the term ''standard error'' is often used to mean a close guess to the true number for the whole group. The more measurements there are in a sample, the closer the guess will be to the true number for the whole group.


= Announcement =
==How to find standard error of the mean==
*(2015/9/6) 第一次课程slides已上传。
One way to find the standard error of the mean is to have lots of samples. First, the average for each sample is found. Then the average and [[standard deviation]] of those sample averages is found. The standard deviation for all the sample averages is the standard error of the mean. This can be a lot of work. Sometimes it is too difficult or costs too much money to have lots of samples.
*(2015/9/22) Balls into bins 部分的slides已上传。
*(2015/9/25) 第一次作业已发布,10月9日上课收。
*(2015/10/29) 在蔡沛程同学的神勇帮助下,我们的课程网站服务器终于重新上线了!
*(2015/10/29) 10月30日周五的课,由于校运动会本科生和研究生课程都要停课,故再停课一次 -_-|||
*(2015/11/13) 讲义中关于随机图阈值现象的部分已经补齐。
*(2015/11/13) 第二次作业已发布,11月27日上课收。
*(2015/11/29) <font color=red size=4>Lovasz local lemma 部分的讲义目前正在大幅度的改写,以反应algorithmic LLL的最新内容。写好之后会通知。</font>


= Course info =
Another way to find the standard error of the mean is to use an equation that needs only one sample. Standard error of the mean is usually estimated by the [[standard deviation]] for a sample from the whole group ([[Standard deviation#With sample standard deviation|sample standard deviation]]) divided by the square root of the sample size.
* '''Instructor ''': 尹一通,
:*email: yitong.yin@gmail.com, yinyt@nju.edu.cn
:*office: 计算机系 804.
* '''Class meeting''': Friday 4pm-6pm, 仙I-206.
* '''Office hour''': Tuesday 2-4pm, 计算机系 804.


= Syllabus =
:<math>SE_\bar{x}\ = \frac{s}{\sqrt{n}}</math>


=== 先修课程 Prerequisites ===
where
* 必须:离散数学,概率论,线性代数。
* 推荐:算法设计与分析。


=== Course materials ===
:''s'' is the [[Standard deviation#With sample standard deviation|sample standard deviation]] (i.e., the sample-based estimate of the standard deviation of the population), and
* [[随机算法 (Spring 2014)/Course materials|<font size=3>教材和参考书</font>]]
:''n'' is the number of measurements in the sample.


=== 成绩 Grades ===
How big does the sample need to be so that the estimate of the standard error of the mean is close to the actual standard error of the mean for the whole group? There should be at least six measurements in a sample. Then the standard error of the mean for the sample will be within 5% of the standard error of the mean if the whole group were measured.<ref>{{cite journal |last=Gurland |first=J |coauthors=Tripathi RC |year=1971 |title=A simple approximation for unbiased estimation of the standard deviation |journal=American Statistician |volume=25 |issue=4|pages=30–32 |doi=10.2307/2682923 |jstor=2682923 |publisher=American Statistical Association }}</ref>
* 课程成绩:本课程将会有若干次作业和一次期末考试。最终成绩将由平时作业成绩和期末考试成绩综合得出。
* 迟交:如果有特殊的理由,无法按时完成作业,请提前联系授课老师,给出正当理由。否则迟交的作业将不被接受。


=== <font color=red> 学术诚信 Academic Integrity </font>===
== Corrections for some cases ==
学术诚信是所有从事学术活动的学生和学者最基本的职业道德底线,本课程将不遗余力的维护学术诚信规范,违反这一底线的行为将不会被容忍。
There is another equation to use if the number of measurements is for 5% or more of the whole group:<ref>{{cite journal
  | first = L.
  | last = Isserlis
  | year = 1918
  | title = On the value of a mean as calculated from a sample
  | journal = Journal of the Royal Statistical Society
  | volume = 81
  | issue = 1
  | pages = 75–81
  | jstor = 2340569
  | doi = 10.2307/2340569
  | publisher = Blackwell Publishing
  }} (Equation 1)</ref>


作业完成的原则:署你名字的工作必须由你完成。允许讨论,但作业必须独立完成,并在作业中列出所有参与讨论的人。不允许其他任何形式的合作——尤其是与已经完成作业的同学“讨论”。
There are special equations to use if a sample has less than 20 measurements.<ref>Sokal and Rohlf 1981. ''Biometry: principles and practice of statistics in biological research'', 2nd ed. p53 ISBN 0716712547</ref>


本课程将对剽窃行为采取零容忍的态度。在完成作业过程中,对他人工作(出版物、互联网资料、其他人的作业等)直接的文本抄袭和对关键思想、关键元素的抄袭,按照 [http://www.acm.org/publications/policies/plagiarism_policy ACM Policy on Plagiarism]的解释,都将视为剽窃。剽窃者成绩将被取消。如果发现互相抄袭行为,<font color=red> 抄袭和被抄袭双方的成绩都将被取消</font>。因此请主动防止自己的作业被他人抄袭。
Sometimes a sample comes from one place even though the whole group may be spread out. Also, sometimes a sample may be made in a short time period when the whole group covers a longer time. In this case, the numbers in the sample are not independent. Then special equations are used to try to correct for this.<ref>James R. Bence 1995. Analysis of short time series: correcting for autocorrelation. ''Ecology'' '''76'''(2): 628–639.</ref>


学术诚信影响学生个人的品行,也关乎整个教育系统的正常运转。为了一点分数而做出学术不端的行为,不仅使自己沦为一个欺骗者,也使他人的诚实努力失去意义。让我们一起努力维护一个诚信的环境。
== Usefulness ==
''A practical result:'' One can become more sure of an average value by having more measurements in a sample. Then the standard error of the mean will be smaller because the standard deviation is divided by a bigger number. However, to make the uncertainty (standard error of the mean) in an average value half as big, the sample size (n) needs to be four times bigger. This is because the standard deviation is divided by the square root of the sample size. To make the uncertainty one-tenth as big, the sample size (n) needs to be one hundred times bigger!


= Assignments =
Standard errors are easy to calculate and are used a lot because:
*[[随机算法 (Fall 2015)/Problem Set 1|Problem Set 1]], due on Oct 9, Friday, in class.
*If the standard error of several individual quantities is known then the standard error of some [[function (mathematics)|function]] of the quantities can be easily calculated in many cases;
*[[随机算法 (Fall 2015)/Problem Set 2|Problem Set 2]], due on Nov 27, Friday, in class.
*Where the [[probability distribution]] of the value is known, it can be used to calculate a good approximation to an exact [[confidence interval]]; and
*[[随机算法 (Fall 2015)/Problem Set 3|Problem Set 3]], due on December 18, Friday, in class.
*Where the probability distribution is not known, other equations can be used to estimate a confidence interval
* As the [[sample size]] gets very large the principle of the [[central limit theorem]] shows that the numbers in the sample are very much like the numbers in the whole group (they have a [[normal distribution]]).


= Lecture Notes =
== Relative standard error ==
# [[随机算法 (Fall 2015)/Identity Testing|Identity Testing]]: checking matrix multiplication, polynomial identity testing, communication complexity    | ([ftp://tcs.nju.edu.cn/slides/random2015/IdentityTesting.pdf slides])
The [[relative standard error]] (RSE) is the standard error divided by the average. This number is smaller than one. Multiplying it by 100% gives it as a percentage of the average. This helps to show whether the uncertainty is important or not. For example, consider two surveys of household income that both result in a sample average of $50,000.  If one survey has a standard error of $10,000 and the other has a standard error of $5,000, then the relative standard errors are 20% and 10% respectively. The survey with the lower relative standard error is better because it has a more precise measurement (the uncertainty is smaller).
# [[随机算法 (Fall 2015)/Fingerprinting|Fingerprinting]]: fingerprinting, the Karp-Rabin algorithm for pattern matching, primality testing    | ([ftp://tcs.nju.edu.cn/slides/random2015/Fingerprinting.pdf slides])
# [[随机算法 (Fall 2015)/Balls and Bins|Balls and Bins]]: balls into bins model, birthday problem, perfect hashing, coupon collector problem, stable matching, occupancy problem  | ([ftp://tcs.nju.edu.cn/slides/random2015/BallsNBins.pdf slides])
# [[随机算法 (Fall 2015)/Min-cut|Min-cut]]: Karger's Min-cut algorithm    | ([ftp://tcs.nju.edu.cn/slides/random2015/Min-Cut.pdf slides])
# [[随机算法 (Fall 2015)/Moment and Deviation|Moment and Deviation]]: Markov's inequality, Chebyshev's inequality, median selection, random graphs, threshold phenomenon    | ([ftp://tcs.nju.edu.cn/slides/random2015/Moments.pdf slides])
# [[随机算法 (Fall 2015)/Universal Hashing|Universal Hashing]]: <math>k</math>-wise independence, universal hash families, perfect hashing    | ([ftp://tcs.nju.edu.cn/slides/random2015/UniversalHashing.pdf slides])
# [[随机算法 (Fall 2015)/Randomized rounding|Randomized rounding]]: max-SAT, LP relaxation, randomized rounding    | ([ftp://tcs.nju.edu.cn/slides/random2015/RandomRounding.pdf slides])
# [[随机算法 (Fall 2015)/Lovász Local Lemma|Lovász Local Lemma]]:
# [[随机算法 (Fall 2015)/Chernoff Bound|Chernoff Bound]]: moment generating function, Chernoff bound, balls into bins, set balancing
# [[随机算法 (Fall 2015)/Concentration of Measure|Concentration of Measure]]: martingales, Azuma's inequality, Doob sequence, bounded difference method, Johnson-Lindenstrauss Theorem


= The Probability Theory Toolkit =
In fact, people who need to know average values often decide how small the uncertainty should be before they decide to use the information.  For example, the U.S. National Center for Health Statistics does not report an average if the relative standard error exceeds 30%. NCHS also requires at least 30 observations for an estimate to be reported.{{citation needed|date=October 2011}}
* [http://en.wikipedia.org/wiki/Probability_space Probability space] and [http://en.wikipedia.org/wiki/Probability_axioms probability axioms]
 
* [http://en.wikipedia.org/wiki/Independence_(probability_theory)#Independent_events Independent events]
== Example ==
* [http://en.wikipedia.org/wiki/Conditional_probability Conditional probability]
[[File:Uncertainty Example.png|thumb|center| 500 px]]
* [http://en.wikipedia.org/wiki/Random_variable Random variable] and [http://en.wikipedia.org/wiki/Expected_value expectation]
[[File:Red Drum (Sciaenops ocellatus).jpg||230px|thumb|right| Example of a redfish (also known as red drum, ''Sciaenops ocellatus'') used in the example.]]
* [http://en.wikipedia.org/wiki/Expected_value#Linearity Linearity of expectation]
 
* The [http://en.wikipedia.org/wiki/Law_of_total_probability law of total probability] and the [http://en.wikipedia.org/wiki/Law_of_total_expectation law of total expectation]
For example, there are many redfish in the water of the [[Gulf of Mexico]]. To find out how much a 42&nbsp;cm long redfish weighs on average, it is not possible to measure all of the redfish that are 42&nbsp;cm long. Instead, it is possible to measure some of them. The fish that are actually measured are called a sample. The table shows weights for two samples of redfish, all 42&nbsp;cm long. The average (mean) weight of the first sample is 0.741&nbsp;kg. The average (mean) weight of the second sample is 0.735&nbsp;kg, a little bit different from the first sample. Each of these averages is a little bit different from the average that would come from measuring every 42&nbsp;cm long redfish (which is not possible anyway).
* The [http://en.wikipedia.org/wiki/Boole's_inequality union bound]
 
* [http://en.wikipedia.org/wiki/Bernoulli_trial Bernoulli trials]
The uncertainty in the mean can be used to know how close the average of the samples are to the average that would come from measuring the whole group. The uncertainty in the mean is estimated as the standard deviation for the sample, divided by the square root of the number of samples minus one. The table shows that the uncertainties in the means for the two samples are very close to each other. Also, the relative uncertainty is the uncertainty in the mean divided by the mean, times 100%. The relative uncertainty in this example is 2.38% and 2.50% for the two samples.
* [http://en.wikipedia.org/wiki/Geometric_distribution Geometric distribution]
 
* [http://en.wikipedia.org/wiki/Binomial_distribution Binomial distribution]
Knowing the uncertainty in the mean, one can know how close the sample average is to the average that would come from measuring the whole group. The average for the whole group is between a) the average for the sample plus the uncertainty in the mean, and b) the average for the sample minus the uncertainty in the mean. In this example, the  average weight for all of the 42&nbsp;cm long redfish in the Gulf of Mexico is expected to be 0.723–0.759&nbsp;kg based on the first sample, and 0.717–0.753 based on the second sample.
* [http://en.wikipedia.org/wiki/Markov's_inequality Markov's inequality]
 
* [http://en.wikipedia.org/wiki/Variance Variance] and [http://en.wikipedia.org/wiki/Covariance covariance]
==References==
* [http://en.wikipedia.org/wiki/Pairwise_independence k-wise independence]
{{reflist}}
* The [http://en.wikipedia.org/wiki/Probabilistic_method  probabilistic method]
 
[[Category:Statistics]]

Latest revision as of 03:47, 2 July 2016

File:Standard deviation diagram.svg
For a value that is sampled with an unbiased normally distributed error, the above depicts the proportion of samples that would fall between 0, 1, 2, and 3 standard deviations above and below the actual value.

The standard error is the standard deviation of the sampling distribution of a statistic.[1] The term may also be used for an estimate (good guess) of that standard deviation taken from a sample of the whole group.

The average of some part of a group (called a sample) is the usual way to estimate the average for the whole group. It is often too hard or costs too much money to measure the whole group. But if a different sample is measured, it will have an average that is a little bit different from the first sample. The standard error of the mean is a way to know how close the average of the sample is to the average of the whole group. It is a way to know how sure you can be about the average from the sample.

In real measurements, the true value of the standard deviation of the mean for the whole group is usually not known. So the term standard error is often used to mean a close guess to the true number for the whole group. The more measurements there are in a sample, the closer the guess will be to the true number for the whole group.

How to find standard error of the mean

One way to find the standard error of the mean is to have lots of samples. First, the average for each sample is found. Then the average and standard deviation of those sample averages is found. The standard deviation for all the sample averages is the standard error of the mean. This can be a lot of work. Sometimes it is too difficult or costs too much money to have lots of samples.

Another way to find the standard error of the mean is to use an equation that needs only one sample. Standard error of the mean is usually estimated by the standard deviation for a sample from the whole group (sample standard deviation) divided by the square root of the sample size.

[math]\displaystyle{ SE_\bar{x}\ = \frac{s}{\sqrt{n}} }[/math]

where

s is the sample standard deviation (i.e., the sample-based estimate of the standard deviation of the population), and
n is the number of measurements in the sample.

How big does the sample need to be so that the estimate of the standard error of the mean is close to the actual standard error of the mean for the whole group? There should be at least six measurements in a sample. Then the standard error of the mean for the sample will be within 5% of the standard error of the mean if the whole group were measured.[2]

Corrections for some cases

There is another equation to use if the number of measurements is for 5% or more of the whole group:[3]

There are special equations to use if a sample has less than 20 measurements.[4]

Sometimes a sample comes from one place even though the whole group may be spread out. Also, sometimes a sample may be made in a short time period when the whole group covers a longer time. In this case, the numbers in the sample are not independent. Then special equations are used to try to correct for this.[5]

Usefulness

A practical result: One can become more sure of an average value by having more measurements in a sample. Then the standard error of the mean will be smaller because the standard deviation is divided by a bigger number. However, to make the uncertainty (standard error of the mean) in an average value half as big, the sample size (n) needs to be four times bigger. This is because the standard deviation is divided by the square root of the sample size. To make the uncertainty one-tenth as big, the sample size (n) needs to be one hundred times bigger!

Standard errors are easy to calculate and are used a lot because:

  • If the standard error of several individual quantities is known then the standard error of some function of the quantities can be easily calculated in many cases;
  • Where the probability distribution of the value is known, it can be used to calculate a good approximation to an exact confidence interval; and
  • Where the probability distribution is not known, other equations can be used to estimate a confidence interval
  • As the sample size gets very large the principle of the central limit theorem shows that the numbers in the sample are very much like the numbers in the whole group (they have a normal distribution).

Relative standard error

The relative standard error (RSE) is the standard error divided by the average. This number is smaller than one. Multiplying it by 100% gives it as a percentage of the average. This helps to show whether the uncertainty is important or not. For example, consider two surveys of household income that both result in a sample average of $50,000. If one survey has a standard error of $10,000 and the other has a standard error of $5,000, then the relative standard errors are 20% and 10% respectively. The survey with the lower relative standard error is better because it has a more precise measurement (the uncertainty is smaller).

In fact, people who need to know average values often decide how small the uncertainty should be before they decide to use the information. For example, the U.S. National Center for Health Statistics does not report an average if the relative standard error exceeds 30%. NCHS also requires at least 30 observations for an estimate to be reported.Template:Citation needed

Example

File:Uncertainty Example.png
File:Red Drum (Sciaenops ocellatus).jpg
Example of a redfish (also known as red drum, Sciaenops ocellatus) used in the example.

For example, there are many redfish in the water of the Gulf of Mexico. To find out how much a 42 cm long redfish weighs on average, it is not possible to measure all of the redfish that are 42 cm long. Instead, it is possible to measure some of them. The fish that are actually measured are called a sample. The table shows weights for two samples of redfish, all 42 cm long. The average (mean) weight of the first sample is 0.741 kg. The average (mean) weight of the second sample is 0.735 kg, a little bit different from the first sample. Each of these averages is a little bit different from the average that would come from measuring every 42 cm long redfish (which is not possible anyway).

The uncertainty in the mean can be used to know how close the average of the samples are to the average that would come from measuring the whole group. The uncertainty in the mean is estimated as the standard deviation for the sample, divided by the square root of the number of samples minus one. The table shows that the uncertainties in the means for the two samples are very close to each other. Also, the relative uncertainty is the uncertainty in the mean divided by the mean, times 100%. The relative uncertainty in this example is 2.38% and 2.50% for the two samples.

Knowing the uncertainty in the mean, one can know how close the sample average is to the average that would come from measuring the whole group. The average for the whole group is between a) the average for the sample plus the uncertainty in the mean, and b) the average for the sample minus the uncertainty in the mean. In this example, the average weight for all of the 42 cm long redfish in the Gulf of Mexico is expected to be 0.723–0.759 kg based on the first sample, and 0.717–0.753 based on the second sample.

References

Template:Reflist

  1. Everitt B.S. 2003. The Cambridge Dictionary of Statistics, CUP. ISBN 0-521-81099-X
  2. Template:Cite journal
  3. Template:Cite journal (Equation 1)
  4. Sokal and Rohlf 1981. Biometry: principles and practice of statistics in biological research, 2nd ed. p53 ISBN 0716712547
  5. James R. Bence 1995. Analysis of short time series: correcting for autocorrelation. Ecology 76(2): 628–639.