1 00:00:03,340 --> 00:00:07,050 Our next topic regarding the processing of streams is how we estimate the number of 2 00:00:07,050 --> 00:00:11,990 dis, distinct elements in the stream without storing everything we have seen. 3 00:00:11,990 --> 00:00:16,380 The technique is known as the Flajolet-Martin algorithm, we'll also see 4 00:00:16,380 --> 00:00:19,670 a generalization of the technique to computing moments of the stream, 5 00:00:19,670 --> 00:00:22,810 which are essentially polynomials in the number of occurrences of 6 00:00:22,810 --> 00:00:26,090 each of the elements that appear in the stream. 7 00:00:26,090 --> 00:00:29,380 That sounds confusing but we'll make the definition clear before long. 8 00:00:32,780 --> 00:00:37,550 So I have a stream of elements chosen from some universal set of possible elements. 9 00:00:37,550 --> 00:00:41,610 We'll assume that there are n elements in the set but n might be extremely large. 10 00:00:41,610 --> 00:00:45,950 For example, the number of IPv6 addresses that could exist or 11 00:00:45,950 --> 00:00:47,820 the set of urls crawled by Google. 12 00:00:48,950 --> 00:00:51,870 All we want to do is know how many different elements have appeared in 13 00:00:51,870 --> 00:00:52,410 the stream. 14 00:00:54,690 --> 00:00:58,920 If not too many elements different elements have been 15 00:00:58,920 --> 00:01:03,590 seen we can store all of them with the index like a hash table. 16 00:01:03,590 --> 00:01:07,920 So, we can tell an element arriving in the stream is new or has been seen before. 17 00:01:08,940 --> 00:01:12,290 That requires a great deal of space if, either the number of different elements 18 00:01:12,290 --> 00:01:16,760 is large or we are maintaining counts for a large number of streams. 19 00:01:16,760 --> 00:01:20,100 In our other case we can't maintain what we need in main memory and 20 00:01:20,100 --> 00:01:24,330 storing the setters or sets on disk will slow us down too much. 21 00:01:27,230 --> 00:01:29,660 Here are some example applications for this problem. 22 00:01:32,520 --> 00:01:34,240 We might be crawling a website and 23 00:01:34,240 --> 00:01:36,750 want to know how many different words appear at that site. 24 00:01:38,130 --> 00:01:42,370 Curiosity isn't a great motivation but doing this count might tell us 25 00:01:42,370 --> 00:01:46,165 something about whether the site is an artificial site constructed by a spammer. 26 00:01:47,360 --> 00:01:51,480 When a spammer has to create a great number of pages without doing much work, 27 00:01:51,480 --> 00:01:54,660 they might use the same page over and over. 28 00:01:54,660 --> 00:01:58,220 Which would lower the number of distinct words below one would expect for 29 00:01:58,220 --> 00:01:59,420 the total size of the site. 30 00:02:00,530 --> 00:02:04,180 Or they might pick random pages on the web which would mean the site has no 31 00:02:04,180 --> 00:02:05,460 coherent topic. 32 00:02:05,460 --> 00:02:09,579 That would cause a number of distinct words to be unexpectedly large. 33 00:02:12,780 --> 00:02:16,210 Major websites like to advertise the number of distinct users who 34 00:02:16,210 --> 00:02:17,490 have visited the site or 35 00:02:17,490 --> 00:02:21,620 used particular features of the site in the most recent day, week or month. 36 00:02:25,040 --> 00:02:26,890 Suppose now we are crawling the web, 37 00:02:27,900 --> 00:02:33,830 we can't afford to follow links to every page we visit, the job would never end. 38 00:02:33,830 --> 00:02:36,600 So we have to cut off the surge at some point. 39 00:02:36,600 --> 00:02:40,820 There will be some pages we know exist because we found links to them, but 40 00:02:40,820 --> 00:02:44,350 we don't know what is on them or what links exist on those pages. 41 00:02:45,360 --> 00:02:48,860 So which pages should we crawl and which should we not bother to crawl? 42 00:02:50,210 --> 00:02:54,250 Well, a heuristic essentially a simple approximation to the page rank, 43 00:02:54,250 --> 00:02:57,030 it's the count the number end links to each page we know about. 44 00:02:58,080 --> 00:03:01,050 We then choose to crawl pages that have the highest number of n links. 45 00:03:02,710 --> 00:03:06,620 This is an example of an application where the sets we are counting are rather small. 46 00:03:06,620 --> 00:03:08,828 Most pages have few n links. 47 00:03:08,828 --> 00:03:11,440 However, there are very many pages that need to be counted, so 48 00:03:11,440 --> 00:03:15,950 compressing the list of URLs with links to a given page is a good thing to do. 49 00:03:18,720 --> 00:03:20,720 We're going to explore he case where there's the set or 50 00:03:20,720 --> 00:03:25,090 sets we need to count are large enough that we cannot conveniently maintain 51 00:03:25,090 --> 00:03:30,210 the set's explicitly in mail memory, we can't ever 52 00:03:30,210 --> 00:03:33,490 get exact counts if we don't store the entire set of elements seen. 53 00:03:33,490 --> 00:03:35,640 So we'll look for the next best thing. 54 00:03:35,640 --> 00:03:38,480 The way to estimate the count in a way that converges to 55 00:03:38,480 --> 00:03:41,920 the true answer as we allocate more space to estimating each count. 56 00:03:44,340 --> 00:03:47,060 The algorithm for estimating counts that we will cover is called 57 00:03:47,060 --> 00:03:50,000 the Flajolet-Martin algorithm after the inventors. 58 00:03:51,500 --> 00:03:56,421 So to start let's pick a hash function that takes stream elements as its argument 59 00:03:56,421 --> 00:04:01,150 and return a bit strings who's length is sufficiently large that there are more 60 00:04:01,150 --> 00:04:06,450 possible results of the hashing than there are elements that might appear in the set. 61 00:04:06,450 --> 00:04:11,925 That is, we need at least log in bits if they are n elements in the universal set. 62 00:04:15,802 --> 00:04:18,077 If a is a possible stream element, 63 00:04:18,077 --> 00:04:22,940 define r of a to be the length of the tail of the hash value, h of a. 64 00:04:22,940 --> 00:04:27,319 That is the number of trailing 0's in the bit string, h of a. 65 00:04:30,874 --> 00:04:33,772 Define capital R to be the maximum value of r 66 00:04:33,772 --> 00:04:37,230 of a that we have seen in the stream so far. 67 00:04:37,230 --> 00:04:40,540 That is, cap R is the largest number of trailing 0's in 68 00:04:40,540 --> 00:04:44,490 the hash function h applied to each of the elements we've seen in the stream. 69 00:04:46,350 --> 00:04:49,370 The estimate of the number of distinct elements that we make from 70 00:04:49,370 --> 00:04:51,060 these calculations is 2 to the R. 71 00:04:52,090 --> 00:04:55,940 This may seem ridiculous because our estimate is always a power of 2, and 72 00:04:55,940 --> 00:05:00,280 it surely not every stream has a number of distinct elements that is the power of 2, 73 00:05:00,280 --> 00:05:02,710 but we're going to use several hash functions and 74 00:05:02,710 --> 00:05:05,680 get several different values of capital R. 75 00:05:05,680 --> 00:05:09,410 By combining them in the right way, we can in principle get any count as our 76 00:05:09,410 --> 00:05:12,250 estimate of the number of distinct elements. 77 00:05:12,250 --> 00:05:15,590 There is intuition why this idea, it gives a good estimate. 78 00:05:15,590 --> 00:05:19,310 First notice that the number of times an element repeats in 79 00:05:19,310 --> 00:05:21,980 the stream has no effect on the value of R, 80 00:05:21,980 --> 00:05:25,364 because each time we hash the same value, we get the same tail of 0s. 81 00:05:26,570 --> 00:05:30,810 The value of r depends only on the number of distinct elements in the stream. 82 00:05:31,900 --> 00:05:33,820 The probability that the hash value for 83 00:05:33,820 --> 00:05:38,280 any given element ends in i 0's goes down exponentially with i. 84 00:05:38,280 --> 00:05:42,230 So when we increase i by one we need to double the number of different elements to 85 00:05:42,230 --> 00:05:47,480 have a good chance of seeing i plus one 0's at the end of some hash value. 86 00:05:47,480 --> 00:05:50,665 That is why raising 2 to the power equal to the longest tail of 87 00:05:50,665 --> 00:05:54,890 0's is a reasonable estimate for how many different elements we've seen. 88 00:05:54,890 --> 00:05:57,260 The next slide tries to make this idea formal. 89 00:06:01,135 --> 00:06:04,610 First, the probability that the hash value of an element ends in i or 90 00:06:04,610 --> 00:06:07,310 more 0's is exactly 2 to the minus i. 91 00:06:08,460 --> 00:06:09,010 That is, for 92 00:06:09,010 --> 00:06:13,550 i equals 0, there is probability one that the, the tail has at least zero 0s. 93 00:06:14,840 --> 00:06:18,700 For i equals 1, there is half a chance that the last bit is 0. 94 00:06:18,700 --> 00:06:22,880 For i equals 2, the chance is a quarter that the last two bits are 0, and so on. 95 00:06:26,100 --> 00:06:29,954 So suppose the number of distinct elements seen in the stream so far is m. 96 00:06:31,250 --> 00:06:33,860 Here is the formula for the probability that R, 97 00:06:33,860 --> 00:06:37,460 the length of the longest tail is at least i. 98 00:06:41,600 --> 00:06:48,510 To see why, remember, 2 to the minus i is the probability a tail has a least i 0's. 99 00:06:48,510 --> 00:06:52,970 So 1 minus 2 to the minus i is the probability that a tail does not end in 100 00:06:52,970 --> 00:06:57,360 as many as i 0's. 101 00:06:57,360 --> 00:07:01,510 And if we have m independent hashings of different elements, we raise this 102 00:07:01,510 --> 00:07:07,440 probability to the nth power to get the probability that no tail is as long as i. 103 00:07:07,440 --> 00:07:12,290 Finally, 1 minus that is the probability that some element has a tail at 104 00:07:12,290 --> 00:07:13,410 least as long as i. 105 00:07:16,940 --> 00:07:21,460 To see why 2 to the r is generally close to m, look at the formula for 106 00:07:21,460 --> 00:07:23,650 the probability that R is at least i, it's that. 107 00:07:26,210 --> 00:07:29,330 We're only interested in the case where i is large. 108 00:07:29,330 --> 00:07:32,095 So 2 to the minus i is tiny compared with 1. 109 00:07:33,370 --> 00:07:43,282 I claim that this is approximately this, where e is the base of natural logarithms. 110 00:07:43,282 --> 00:07:48,029 The proof is similar to the one we just gave regarding the throwing of 111 00:07:48,029 --> 00:07:52,377 darts to targets, and I'm not going to repeat it here [SOUND]. 112 00:07:52,377 --> 00:07:56,150 So the first case is where 2 to the i is much greater than m. 113 00:07:56,150 --> 00:08:00,720 We don't expect to find a tail as large as i among m hash values. 114 00:08:00,720 --> 00:08:03,960 But to see the math, start with the formula for 115 00:08:03,960 --> 00:08:05,760 the probability that R is at least i. 116 00:08:07,270 --> 00:08:10,029 And again, that's, that's this. 117 00:08:16,877 --> 00:08:21,647 Okay, since m times 2 to the minus i is small when 2 to 118 00:08:21,647 --> 00:08:27,265 the i is much bigger than m, we can estimate this exponential, 119 00:08:27,265 --> 00:08:34,490 that's again, that by the first two terms of its Taylor expansion. 120 00:08:34,490 --> 00:08:39,930 Remember that e to the x is 1 plus x 121 00:08:41,420 --> 00:08:48,760 plus x squared over 2 factorial plus x cubed over 3 factorial and so on. 122 00:08:51,300 --> 00:08:55,495 If X is much less than 1 only the first 2 terms are significant. 123 00:08:59,360 --> 00:09:02,600 And that is what we have done here where we 124 00:09:02,600 --> 00:09:09,130 replaced the exponential by the first two terms of, of the expansion. 125 00:09:12,590 --> 00:09:20,140 But the 1's cancel and the plus of course becomes a minus becomes a plus. 126 00:09:20,140 --> 00:09:23,370 And that leaves us with m over 2 to the i. 127 00:09:25,540 --> 00:09:27,740 And since we assume two of the i's much bigger than an m, 128 00:09:27,740 --> 00:09:32,180 the conclusion is that there is very little probably that 129 00:09:32,180 --> 00:09:36,475 R the largest value of i that will be found among the tail lengths is such that 130 00:09:36,475 --> 00:09:40,750 2 to the R our estimate of m is much larger than m itself. 131 00:09:45,300 --> 00:09:49,890 On the other hand, suppose 2 to the i is much smaller than m, and 132 00:09:49,890 --> 00:09:52,220 m times 2 to the minus i is large and 133 00:09:52,220 --> 00:09:59,300 e raised to a large negative power, that's this, is small. 134 00:09:59,300 --> 00:10:03,100 So the probability of seeing a tail of length at least i is close to 1. 135 00:10:08,358 --> 00:10:11,933 Our conclusion is that 2 to the R is almost always near m, 136 00:10:11,933 --> 00:10:14,550 not much too big, and not much too small. 137 00:10:19,280 --> 00:10:22,890 Unfortunately, reasoning about the small probability of an over or 138 00:10:22,890 --> 00:10:25,920 under estimate of m doesn't tell the whole story. 139 00:10:25,920 --> 00:10:29,350 The fact is that the expected value of 2 to the R is infinite in 140 00:10:29,350 --> 00:10:33,280 principle although the fact that there is a upper limit on the length of a tail. 141 00:10:33,280 --> 00:10:37,870 The number of bits in the hash value that means 142 00:10:37,870 --> 00:10:42,240 the expected value is not really infinite, but some much too large number. 143 00:10:43,880 --> 00:10:49,140 The argument for infinite expectation is that we, as we move from R to R plus 1 and 144 00:10:49,140 --> 00:10:52,470 probability of getting a tail that large halves, but 145 00:10:52,470 --> 00:10:54,680 the value of 2 to the R doubles. 146 00:10:54,680 --> 00:10:57,840 As a result, each value of R up to the maximum posi, 147 00:10:57,840 --> 00:11:01,960 possible tail length contributes the same amount to the expectation. 148 00:11:04,770 --> 00:11:08,740 To deal with the infinite expected value, we will need to use a large number of 149 00:11:08,740 --> 00:11:12,320 independent hash functions and those get many samples of values for R. 150 00:11:13,450 --> 00:11:15,715 We need to do that anyway since one value, 151 00:11:15,715 --> 00:11:19,014 even if it were a good estimate, would not be exact, and 152 00:11:19,014 --> 00:11:23,715 only by combining many estimates can we be reasonably sure we're close to the truth. 153 00:11:25,675 --> 00:11:28,890 So we need to combine the samples of R that we get. 154 00:11:28,890 --> 00:11:30,590 It's not obvious how we do that. 155 00:11:31,920 --> 00:11:33,990 For example, if we take the average, 156 00:11:33,990 --> 00:11:37,620 than one unusually large value will distort the average too much. 157 00:11:38,880 --> 00:11:41,110 And another option is to take the median. 158 00:11:41,110 --> 00:11:43,010 The median lets us ignore really large or 159 00:11:43,010 --> 00:11:46,350 small values, but the trouble with medians is, 160 00:11:46,350 --> 00:11:51,160 is that they are always one of the values in the set whose median you're taking. 161 00:11:51,160 --> 00:11:53,610 And this set is a collection of powers of 2. 162 00:11:53,610 --> 00:11:56,139 So the result would always be a power of 2. 163 00:12:00,710 --> 00:12:02,320 Here’s the way we combine averages and 164 00:12:02,320 --> 00:12:05,590 medians to get an estimate that is not biased to the high end and 165 00:12:05,590 --> 00:12:09,240 which will converge to the exact answer if we take enough samples. 166 00:12:09,240 --> 00:12:11,360 That is, we use enough different hash functions and 167 00:12:11,360 --> 00:12:13,509 compute the maximum tail length for each. 168 00:12:15,370 --> 00:12:16,970 Here is the way we combine averages and 169 00:12:16,970 --> 00:12:20,720 medians to get an estimate that is not biased to the high end, and 170 00:12:20,720 --> 00:12:24,270 which will converge to the exact answer if we take enough samples. 171 00:12:24,270 --> 00:12:26,390 That is, we use enough different hash functions and 172 00:12:26,390 --> 00:12:29,950 compute the maximum tail length for each. 173 00:12:29,950 --> 00:12:32,519 We're going to partition the samples into small groups. 174 00:12:33,780 --> 00:12:36,700 The group should be of size around log n, 175 00:12:36,700 --> 00:12:41,240 at least log n where n is the size of the universal set. 176 00:12:43,450 --> 00:12:45,720 Then within a group we take the average. 177 00:12:47,770 --> 00:12:54,060 And among all the averages of the groups we take the median average, and 178 00:12:54,060 --> 00:12:58,490 the result then will be an unbiased estimate of m the number of 179 00:12:59,690 --> 00:13:01,030 different elements in the stream. 180 00:13:06,140 --> 00:13:10,730 I want to move on to a generalization of the problem of counting distinct elements. 181 00:13:10,730 --> 00:13:14,930 It's called estimating moments, and the count of distinct elements will, 182 00:13:14,930 --> 00:13:17,980 as we shall see, turn out to be the 0th moment of the stream. 183 00:13:19,350 --> 00:13:22,940 So as before, let's imagine we have a stream whose elements are chosen from 184 00:13:22,940 --> 00:13:24,830 a universal set of n elements. 185 00:13:26,190 --> 00:13:30,020 And let the ith element occur, m sub i times n stream so far. 186 00:13:33,999 --> 00:13:38,765 And the kth moment of the stream is the sum of all kth powers of the m's sub i's. 187 00:13:41,805 --> 00:13:44,788 Here are the first three moments of the stream and 188 00:13:44,788 --> 00:13:50,860 the meanings, the 0th moment is the sum of each m's of i raised to the 0th power. 189 00:13:50,860 --> 00:13:53,620 0th power of anything except 0 is 1. 190 00:13:53,620 --> 00:13:58,170 So we're actually counting the number of distinct elements that have appeared so 191 00:13:58,170 --> 00:13:59,020 far in the stream. 192 00:14:00,120 --> 00:14:06,470 That is, the 0th moment is the problem that the Flajolet-Martin algorithm solves. 193 00:14:06,470 --> 00:14:08,800 The first moment is the sum of the m sub i's. 194 00:14:08,800 --> 00:14:13,600 That is, the sum of the counts of the number of occurrences of all the elements. 195 00:14:13,600 --> 00:14:15,550 That's just the length of the stream. 196 00:14:15,550 --> 00:14:18,270 We can count the length of the stream with a single counter that we 197 00:14:18,270 --> 00:14:20,040 increment once per input. 198 00:14:20,040 --> 00:14:20,800 This is easy. 199 00:14:20,800 --> 00:14:24,610 Much easier than the other moments and no estimation is needed. 200 00:14:24,610 --> 00:14:30,780 The second moment, that is the sum of the squares of the m's sub, 201 00:14:30,780 --> 00:14:34,050 is is sometimes referred to as the surprise number and 202 00:14:34,050 --> 00:14:38,400 it gives a measure of how uneven the distribution of elements in the stream is. 203 00:14:41,100 --> 00:14:44,140 So, here's an example of computing the second moment and 204 00:14:44,140 --> 00:14:46,280 what the surprise is all about. 205 00:14:46,280 --> 00:14:50,380 Well supposed that 100 elements have arrived so far on the stream, and 206 00:14:50,380 --> 00:14:54,790 that these elements are divided among eleveron, eleven different values. 207 00:14:55,820 --> 00:14:59,260 What would be unsurprising is that they all appear at approximately the same 208 00:14:59,260 --> 00:15:00,690 number of times. 209 00:15:00,690 --> 00:15:04,535 The best we could do in that regard is to have one appear 10 times and 210 00:15:04,535 --> 00:15:06,097 the other is 9 times each. 211 00:15:06,097 --> 00:15:15,366 The sum of these counts is 10 squared plus 10 times 9 squared, 212 00:15:15,366 --> 00:15:23,654 which is 100 plus 10 times 81 and is equal to 910. 213 00:15:23,654 --> 00:15:26,120 That would be the lowest possible surprise number for 214 00:15:26,120 --> 00:15:28,380 stream with this number of different elements. 215 00:15:34,404 --> 00:15:39,811 Now what would be really surprising is if one of the 11 numbers appeared 90 times, 216 00:15:39,811 --> 00:15:42,860 and the other 10 appeared once each. 217 00:15:42,860 --> 00:15:48,014 The sum of the squares of the counts in this 218 00:15:48,014 --> 00:15:53,021 case would be 90 squared plus n times 1 219 00:15:53,021 --> 00:15:59,529 squared which is 8100 plus 10 or 8110. 220 00:15:59,529 --> 00:16:04,049 That is the largest possible surprise number in this situation. 221 00:16:07,664 --> 00:16:11,954 I'm now going to introduce a technique due to Alon, Matias, and Szegedy for 222 00:16:11,954 --> 00:16:13,810 estimating a moment of a stream. 223 00:16:15,790 --> 00:16:17,460 It works to compute any moment. 224 00:16:19,960 --> 00:16:22,540 But we'll talk only about the second moment. 225 00:16:24,280 --> 00:16:27,580 The method involves keeping track of the value of many different random 226 00:16:27,580 --> 00:16:30,380 variables X as the stream grows. 227 00:16:30,380 --> 00:16:34,550 Each random variable is analogous to recording the maximum number of zeros in 228 00:16:34,550 --> 00:16:39,060 the tail using a fixed hash function like we did for the Flajolet-Martin algorithm. 229 00:16:41,310 --> 00:16:44,350 And as for the Flajolet-Martin algorithm, 230 00:16:44,350 --> 00:16:46,960 each random variable requires storage of an integer. 231 00:16:46,960 --> 00:16:48,290 Preferably in main memory. 232 00:16:48,290 --> 00:16:51,953 So we're limited in how many variables we can compute for each stream. 233 00:16:54,759 --> 00:16:57,340 So let's see how we manage one random variable. 234 00:16:57,340 --> 00:17:00,680 We can manage as many as we can afford in the same way of course. 235 00:17:00,680 --> 00:17:02,520 Using different random numbers for each. 236 00:17:05,040 --> 00:17:05,610 Okay. So 237 00:17:05,610 --> 00:17:08,900 let n be the length of the stream seen so far. 238 00:17:08,900 --> 00:17:10,630 N is going to grow as time goes on, 239 00:17:10,630 --> 00:17:13,170 surely, but right now it has some particular value. 240 00:17:15,080 --> 00:17:19,580 For the random variable x, we need to pick a random place in the stream to start so 241 00:17:19,580 --> 00:17:22,830 that any starting point is equally likely to be chosen. 242 00:17:22,830 --> 00:17:25,650 This choice introduces the randomness. 243 00:17:25,650 --> 00:17:28,900 If we have many random variables they will be independent because for 244 00:17:28,900 --> 00:17:32,060 each we choose a random starting point independently of the others. 245 00:17:34,700 --> 00:17:37,720 So let a be the element found at the chosen starting point. 246 00:17:37,720 --> 00:17:41,240 The value of random variable X is n, 247 00:17:41,240 --> 00:17:46,310 the current stream length times twice the number of occurrences of a we find in 248 00:17:46,310 --> 00:17:51,420 the stream since the randomly chosen starting point and then minus 1. 249 00:17:51,420 --> 00:17:55,160 Notice that a surely occurs at the time chosen but 250 00:17:55,160 --> 00:17:56,800 may occur many times after that. 251 00:17:58,350 --> 00:18:00,760 Occurrences before the chosen time do not count. 252 00:18:03,490 --> 00:18:06,410 An important point is that even though X is defined this way you do 253 00:18:06,410 --> 00:18:10,370 not have to change the value of X each time n increases by 1. 254 00:18:10,370 --> 00:18:11,790 We store n separately and 255 00:18:11,790 --> 00:18:16,600 it could be used to compute the value of each of the random variables if we needed. 256 00:18:16,600 --> 00:18:19,900 What we actually store for X is the element a, and 257 00:18:19,900 --> 00:18:24,290 the count of occurrences of a since the randomly chosen starting point. 258 00:18:24,290 --> 00:18:27,020 This way when an input arrives at 259 00:18:27,020 --> 00:18:30,270 the stream we can leave almost all the variables unchanged. 260 00:18:30,270 --> 00:18:31,730 We only have to change those for 261 00:18:31,730 --> 00:18:35,070 which the element being counted is the element that just arrived. 262 00:18:39,090 --> 00:18:42,660 On this slide we're going to argue that the expected value of a variable, 263 00:18:42,660 --> 00:18:45,210 considering all the possible starting times, 264 00:18:45,210 --> 00:18:47,810 exactly equals the second moment of the stream. 265 00:18:49,420 --> 00:18:54,040 First, remember that the second moment is the sum over all elements a of 266 00:18:54,040 --> 00:18:56,539 the square of the number of times a occurs. 267 00:18:58,880 --> 00:19:02,030 Now, here's the formula for the expected value of variable X. 268 00:19:03,140 --> 00:19:05,910 There are n possible starting points, each equally likely. 269 00:19:07,370 --> 00:19:13,560 We'll average the value of X that is computed for each of these starting times. 270 00:19:13,560 --> 00:19:20,390 The 1 over n is for taking the average, and everything else is the sum 271 00:19:20,390 --> 00:19:25,410 over all possible times t of the value that is computed when time t is chosen. 272 00:19:26,430 --> 00:19:28,850 Remember that when t is chosen as the start time, 273 00:19:28,850 --> 00:19:35,870 the value of X is n times twice the number of occurrences,, 274 00:19:35,870 --> 00:19:41,720 that of that same element in the stream from then on. 275 00:19:41,720 --> 00:19:43,905 And then minus minus 1. 276 00:19:43,905 --> 00:19:50,630 Okay, here we've rewritten the formula for 277 00:19:50,630 --> 00:19:54,650 the expected value of x, by grouping all the times from want to and 278 00:19:54,650 --> 00:19:57,190 according to the symbol a that is found there. 279 00:19:57,190 --> 00:19:59,290 So we can sum over all symbols a. 280 00:20:06,640 --> 00:20:11,964 Now the 1 over n and the n are constants as far as the summation is concerned, so 281 00:20:11,964 --> 00:20:14,477 we carry them over, and guess what. 282 00:20:14,477 --> 00:20:15,071 They cancel. 283 00:20:20,903 --> 00:20:25,570 Now the term for a given symbol a involves several different times t in this string. 284 00:20:25,570 --> 00:20:29,920 Each time will give a different value for twice the number of a's minus 1. 285 00:20:29,920 --> 00:20:32,950 The first term 1 represents the time when the last a arrives. 286 00:20:33,980 --> 00:20:35,870 Then the count will be 1. 287 00:20:35,870 --> 00:20:40,505 That is twice the count is 2 and then minus 1 leaves us with 1. 288 00:20:43,232 --> 00:20:47,435 The 3 represents the next to last time that a occurs, and 289 00:20:47,435 --> 00:20:49,370 then the count will be 2. 290 00:20:49,370 --> 00:20:54,030 Double it to make 4 and subtrap, trip, subtract 1 to leave 3. 291 00:20:54,030 --> 00:20:55,360 We continue like that for 292 00:20:55,360 --> 00:21:00,090 each possible time an a appears and we get all the odd integers in turn. 293 00:21:02,280 --> 00:21:06,150 Finally, the largest count we can get is when the time, t, 294 00:21:06,150 --> 00:21:07,930 is the first time, a, appears. 295 00:21:09,850 --> 00:21:11,531 Then the count will be m sub a, 296 00:21:11,531 --> 00:21:15,245 the full number of times a appears, we double it and subtract 1. 297 00:21:18,469 --> 00:21:23,564 You can show that the sum of all the odd integers up 298 00:21:23,564 --> 00:21:27,830 to 2m sub i minus 1 is m by squared. 299 00:21:27,830 --> 00:21:32,090 It's an easy induction and I'm not going to do it here but for 300 00:21:32,090 --> 00:21:38,430 example, if m of a is 4, then 301 00:21:38,430 --> 00:21:45,720 1 plus 3 plus 5 plus 7 equals 16 which of course is 4 squared. 302 00:21:47,910 --> 00:21:52,560 As I mentioned, we want not only the correct expected value for a variable. 303 00:21:52,560 --> 00:21:55,750 We want to know that as you use more and more variables the average of 304 00:21:55,750 --> 00:22:00,550 their estimates of the moment will converge to the true value. 305 00:22:00,550 --> 00:22:02,170 I'm just going to tell you that's the case. 306 00:22:02,170 --> 00:22:06,539 You combine them as for Flajolet-Martin estimates group into small groups, 307 00:22:06,539 --> 00:22:10,259 take the average of the groups and then the median of the averages. 308 00:22:14,839 --> 00:22:17,290 There's a small problem we need to fix though. 309 00:22:17,290 --> 00:22:18,890 We treated n as a constant but 310 00:22:18,890 --> 00:22:22,570 in fact the stream is always growing, and n is therefore a variable. 311 00:22:25,470 --> 00:22:30,550 So, one consequence of n being a variable is, is easy to fix. 312 00:22:30,550 --> 00:22:31,990 In fact we mentioned it before, 313 00:22:31,990 --> 00:22:35,110 we store n once an increment that each time a new element arrives. 314 00:22:36,980 --> 00:22:39,020 In the variable X, we store only the count, 315 00:22:39,020 --> 00:22:42,400 if we ever need the value of X, we double the count subtract 1 and 316 00:22:42,400 --> 00:22:44,690 then multiply the result by the current value of n. 317 00:22:47,670 --> 00:22:51,000 However the tricky part is how we manage to keep the fixed number of 318 00:22:51,000 --> 00:22:55,400 variables representing random choices of positions with each position from 319 00:22:55,400 --> 00:22:59,820 one to n equally likely, even as n grows. 320 00:22:59,820 --> 00:23:03,800 That is, if we're keeping k random variables, then whatever n is 321 00:23:03,800 --> 00:23:08,050 we want each starting time to have been selected with probability k over n. 322 00:23:12,580 --> 00:23:16,130 So here's how we make sure that at all times each of the N positions is 323 00:23:16,130 --> 00:23:17,890 chosen with probability K over N. 324 00:23:17,890 --> 00:23:20,910 The technique is called reservoir sampling by the way. 325 00:23:22,450 --> 00:23:26,630 To get started, each of the first k positions in the stream is chosen. 326 00:23:26,630 --> 00:23:30,360 That makes sense because k over n is k over k or 327 00:23:30,360 --> 00:23:34,100 1, before we reach the Kth position we're not 328 00:23:34,100 --> 00:23:37,790 really sampling since the best we can do is to choose each position with certainty. 329 00:23:39,660 --> 00:23:43,880 But now n is bigger than k so not every position can be chosen. 330 00:23:43,880 --> 00:23:46,540 So suppose the nth element arrives. 331 00:23:46,540 --> 00:23:49,400 Prior to this there were n-1 positions in the stream, and 332 00:23:49,400 --> 00:23:56,840 each was chosen with equal probability, and that probability is k over n minus 1. 333 00:23:56,840 --> 00:23:58,400 The nth element arrives. 334 00:23:58,400 --> 00:24:02,680 We know the nth position has to be chosen with probability k over n, so 335 00:24:02,680 --> 00:24:04,820 let's generate a random number. 336 00:24:04,820 --> 00:24:09,870 And do that for the the reason we just arrived the position. 337 00:24:11,120 --> 00:24:13,760 If the decision is not to choose position n, 338 00:24:13,760 --> 00:24:16,720 then no change is made to our selection of k positions. 339 00:24:18,880 --> 00:24:23,970 But, if you decide to pick position n then select one of the current k positions at 340 00:24:23,970 --> 00:24:26,690 random and toss it from the set of positions. 341 00:24:28,720 --> 00:24:33,300 We know the nth position has a k over n chance of being chosen, but 342 00:24:33,300 --> 00:24:35,810 how about the first n minus 1 positions? 343 00:24:35,810 --> 00:24:38,190 Their probability can be calculated as shown. 344 00:24:41,860 --> 00:24:42,360 Okay. 345 00:24:42,360 --> 00:24:43,380 There are two cases. 346 00:24:43,380 --> 00:24:46,930 Either the n position was chosen or not. 347 00:24:46,930 --> 00:24:50,320 If it is not chosen, it is that chosen then with, 348 00:24:50,320 --> 00:24:53,030 with probability n minus k over n. 349 00:24:57,680 --> 00:25:01,730 Each of the first n minus 1 positions as previously chosen with probability k 350 00:25:01,730 --> 00:25:03,240 over n minus 1. 351 00:25:03,240 --> 00:25:06,560 In the case where the nth position is not chosen. 352 00:25:06,560 --> 00:25:08,700 If some previous position had been chosen, 353 00:25:08,700 --> 00:25:11,730 then it will still be chosen, so we multiply by this factor. 354 00:25:15,260 --> 00:25:19,380 But there's another term we have to add to the probability is the product of 355 00:25:19,380 --> 00:25:20,510 three factors. 356 00:25:20,510 --> 00:25:22,200 First is the factor k over n, 357 00:25:22,200 --> 00:25:25,330 representing the probability that the nth position is chosen. 358 00:25:27,990 --> 00:25:32,590 Now, in order for one of the fist n minus 1 positions to remain chosen, 359 00:25:32,590 --> 00:25:35,070 it must have been chosen previously. 360 00:25:35,070 --> 00:25:38,039 That happens with probability k over n minus 1, as we mentioned. 361 00:25:40,900 --> 00:25:42,740 And it must not be thrown out. 362 00:25:42,740 --> 00:25:46,080 It will not be thrown out with probability k minus 1 over k. 363 00:25:47,130 --> 00:25:51,250 Now I'll let you do the math, but the expression does indeed simplify to k 364 00:25:51,250 --> 00:25:56,060 over n so all n positions now have exactly the same probability of being chosen.