Probabilistic counting With a b-bit counter, we can ordinarily only count up to 2b 1. With R. Morriss probabilistic counting, we can count up to a much larger value at the expense of some loss of precision. We let a counter value of i represent a count of ni for i D 0; 1; : : : ; 2b 1, where the ni form an increasing sequence of nonnegative values. We assume that the initial value of the counter is 0, representing a count of n0 D 0. The INCREMENT operation works on a counter containing the value i in a probabilistic manner. If i D 2b 1, then the operation reports an overflow error. Otherwise, the INCREMENT operation increases the counter by 1 with probability 1=.niC1 ni/, and it leaves the counter unchanged with probability 1 1=.niC1 ni/. If we select ni D i for all i 0, then the counter is an ordinary one. More interesting situations arise if we select, say, ni D 2i1 for i>0 or ni D Fi (the ith Fibonacci numbersee Section 3.2). For this problem, assume that n2b1 is large enough that the probability of an overflow error is negligible. a. Show that the expected value represented by the counter after n INCREMENT operations have been performed is exactly n. b. The analysis of the variance of the count represented by the counter depends on the sequence of the ni. Let us consider a simple case: ni D 100i for all i 0. Estimate the variance in the value represented by the register after n INCREMENT operations have been performed.

Zane Ghali Calculus 1 Antiderivatives and Indefinite Integration Notes Antiderivatives and Indefinite Integration Notes ● A function labeled “F(x)” is an antiderivative of f(x), assuming F’(x) = f(x) for all x in the domain of f. ● The group of all antiderivatives of a function f(x) is the “indefinite integral” of f with respect to x. ● The indefinite...