Table 1:Symbols used in the paper THEOREM 1.Let St.i be the random variable representing Symbol Description the run size of b starting at location i in a frame of size f. actual tag population size Let a=f-i+1.The expectation and variance of Ssi are: t tm upper bound on of tags (2) tM maximum of tags that can be estimated s小=0- estimated of tags a required reliability Var(5)=B+2a+1g+2-g6)-ga+" (3) B required confidence interval (1-96)2 frame size fop optimal frame size PROOF.To calculate the expected value of S.i,we first j f+3 to include delay between two need its probability density function PiS.=s.The prob- consecutive frames ability that a run starting at location i will be of length s is n of rounds (i.e.,frames) the product of the probability that s consecutive slots are b nop optimal of rounds (i.e..frames) p persistence probability and s+ith slot is B,where 6=1-b.Thus, Pop optimal persistence probability i(1-g)ifs<a R random seed from reader P(Sb.i=s)= if s=a h(f,R,D)unform hash function in 1,f 96 0 if s>a b value of a slot:b=0 or b=1 、6 1-6 where 1≤i≤fand1≤s≤a.To derive the expected 96 probability that a slot is b value and variance of S.,we use the moment generating Sbi random variable for run size of b starting at i function: E. expected value Var(.) variance (r)=Eles1=∑e“PSt=sy Cove)】 covariance = Yi random variable for of b slots in frame element of sample space of Y random variable for of runs of b in frame =(ge')°+1-p)∑(ge') Ro 8=1 T element of sample space of R Xb random variable for average run size of b in Differentiating both side w.r.t.7,we get a frame a-1 4 expected value of Xo standard deviation ofo p'(r)=a(ge'）°+(1-go)ge')∑s(ge')-l o0】 $=1 number of ways in which y occurrences of b ξ{，y,r} and f-y occurrences of b can be arranged d (1-(qoe")a =alge'y°+1-gp)lge)ae可（1-9%er -1 in f slots while ensuring that the number of runs of b are r (1-96)(a-1)(g6e')a+1-a(g%e')°+qg%e alge")a+ (1-9%er)2 111 and 11)is (3+2)/2 =2.5.After n rounds,we obtain n average run sizes of b and then calculate the average of Evaluation of o'(r)at r =0 gives us Equation (2).To find these n values.This final value is then used as the expected Var(S.),we calculate E[S]by taking the second deriva- value of the average run size of b in a frame to estimate the tive of '(r)and setting T=0.Thus, tag population size The probability that a slot in a frame is b.where b=0 or ES,=6+96+2a-19+2-2a+1)g8+1 (1-96)2 1,can be calculated using Lemma 1. Evaluating E[S]-E2[S6.]gives Equation (3). LEMMA 1.Let t be the actual tag population size,f be the frame size,p be the persistence probability (i.e.,the proba- Let Xo be the random variable representing the average run bility that a tag participates in a frame),and go be the prob- size of b in a frame.Next,we calculate the expectation and ability that a slot in a frame is b.Thus: variance of Xo using the expectation and variance of Sa.i ∫(1-)fb=0 from Theorem 1.The expectation of Xo will be used to esti- 9s=1-(-)fb=1 (1) mate the tag population size and the variance of Xo will be used to calculate optimal values for f,p,and n.Let Yo be the random variable representing the number of times b oc- PROOF.The probability that a tag chooses a given slot in a frame is p/f.The probability that it does not choose that ead6 meo爱 slot is 1-2.The probability that none of the tags choose holds for any frame.Next,we first calculate E[Yo],Var(Y), that slot is (1-),which is the value of go.As the tags ER,Var(R),and Cov(Y,R)in Lemmas 2 and 3.Then choose the slots independently,g is the same for each slot of we use them to calculate E[Xo]and Var(X)in Theorem 2. the frame.The probability that a slot is chosen by at least Using Equation (14)in Theorem 2,replacing E[X]by the one tag is 1-go,which is the value of gi. average run size of b from n frames,we obtain an equation with only one variable t.Finally,we use Brent's method to Let S.be the random variable representing the run size obtain the numerical solution of this equation.The result of b starting at location i in a frame.If the i-th slot is not is the estimated tag population size.Since ART uses Xo to the starting point of a run,then S.=0.The expectation estimate the tag population size,we call Xo the estimator and variance of So.i can be calculated using Theorem 1. of ART. 368Table 1: Symbols used in the paper Symbol Description t actual tag population size tm upper bound on # of tags tM maximum # of tags that can be estimated t ˜ estimated # of tags α required reliability β required confidence interval f frame size fop optimal frame size f f + 3 to include delay between two consecutive frames n # of rounds (i.e., frames) nop optimal # of rounds (i.e., frames) p persistence probability pop optimal persistence probability R random seed from reader h(f, R, ID) unform hash function in [1, f] b value of a slot: b = 0 or b = 1 b 1-b qb probability that a slot is b Sb,i random variable for run size of b starting at i E[.] expected value Var(.) variance Cov(.) covariance Yb random variable for # of b slots in frame y element of sample space of Yb Rb random variable for # of runs of b in frame r element of sample space of Rb Xb random variable for average run size of b in a frame μ{.} expected value of Xb σ{.} standard deviation of Xb ξ{f, y, r} number of ways in which y occurrences of b and f − y occurrences of b can be arranged in f slots while ensuring that the number of runs of b are r 111 and 11) is (3 + 2)/2=2.5. After n rounds, we obtain n average run sizes of b and then calculate the average of these n values. This final value is then used as the expected value of the average run size of b in a frame to estimate the tag population size. The probability that a slot in a frame is b, where b = 0 or 1, can be calculated using Lemma 1. Lemma 1. Let t be the actual tag population size, f be the frame size, p be the persistence probability ( i.e., the proba￾bility that a tag participates in a frame), and qb be the prob￾ability that a slot in a frame is b. Thus: qb =  (1 − p f ) t if b = 0 1 − (1 − p f ) t if b = 1 (1) Proof. The probability that a tag chooses a given slot in a frame is p/f. The probability that it does not choose that slot is 1 − p f . The probability that none of the tags choose that slot is (1 − p f ) t , which is the value of q0. As the tags choose the slots independently, qb is the same for each slot of the frame. The probability that a slot is chosen by at least one tag is 1 − q0, which is the value of q1. Let Sb,i be the random variable representing the run size of b starting at location i in a frame. If the i-th slot is not the starting point of a run, then Sb,i = 0. The expectation and variance of Sb,i can be calculated using Theorem 1. Theorem 1. Let Sb,i be the random variable representing the run size of b starting at location i in a frame of size f. Let a = f − i + 1. The expectation and variance of Sb,i are: E[Sb,i] = qb 1 − qb (1 − qa b ) (2) Var(Sb,i) = qb + (2a + 1)(qa+2 b − qa+1 b ) − q 2(a+1) b (1 − qb)2 (3) Proof. To calculate the expected value of Sb,i, we first need its probability density function P{Sb,i = s}. The prob￾ability that a run starting at location i will be of length s is the product of the probability that s consecutive slots are b and s + i th slot is b, where b = 1 − b. Thus, P{Sb,i = s} = ⎧ ⎨ ⎩ qs b (1 − qb) if s<a qs b if s = a 0 if s>a where 1 ≤ i ≤ f and 1 ≤ s ≤ a. To derive the expected value and variance of Sb,i, we use the moment generating function: φ(τ ) = E[e τSb,i ] = a s=1 e τsP{Sb,i = s} = (qbe τ ) a + (1 − qb) a −1 s=1 (qbe τ ) s Differentiating both side w.r.t. τ , we get φ (τ )=a(qbe τ ) a + (1 − qb)(qbe τ ) a −1 s=1 s(qbe τ ) s−1 = a(qbe τ ) a + (1 − qb)(qbe τ ) d d(qbeτ ) 1 − (qbeτ ) a 1 − qbeτ − 1 = a(qbe τ ) a + (1 − qb) (a − 1)(qbeτ ) a+1 − a(qbeτ ) a + qbeτ (1 − qbeτ )2 Evaluation of φ (τ ) at τ = 0 gives us Equation (2). To find Var(Sb,i), we calculate E[S2 b,i] by taking the second deriva￾tive of φ (τ ) and setting τ = 0. Thus, E[S2 b,i] = qb + q2 b + (2a − 1)qa+2 b − (2a + 1)qa+1 b (1 − qb)2 Evaluating E[S2 b,i] − E2[Sb,i] gives Equation (3). Let Xb be the random variable representing the average run size of b in a frame. Next, we calculate the expectation and variance of Xb using the expectation and variance of Sb,i from Theorem 1. The expectation of Xb will be used to esti￾mate the tag population size and the variance of Xb will be used to calculate optimal values for f, p, and n. Let Yb be the random variable representing the number of times b oc￾curs in a frame and Rb be the random variable representing the number of runs of b in a frame. By definition, Xb = Yb Rb holds for any frame. Next, we first calculate E[Yb], Var(Yb), E[Rb], Var(Rb), and Cov(Yb, Rb) in Lemmas 2 and 3. Then, we use them to calculate E[Xb] and Var(Xb) in Theorem 2. Using Equation (14) in Theorem 2, replacing E[Xb] by the average run size of b from n frames, we obtain an equation with only one variable t. Finally, we use Brent’s method to obtain the numerical solution of this equation. The result is the estimated tag population size. Since ART uses Xb to estimate the tag population size, we call Xb the estimator of ART. 368