LEMMA 2.Let Yi be the random variable representing the Here we used the fact that the frame size is always greater mumber of times b occurs in a frame and Ro be the random than 1 during the estimation process whenever the informa- variable representing the number of runs of b in a frame. tion about runs is used.As I;~Bernoulli(o),its variance Given tag population size t,frame size f,and persistence is that of a bernoulli random variable given by probability p,we have: Var(Ii)=E[Ii](1-E[Ii]) (⑧) E[Yi]=fqb (4) Var(Y)=fqb(1-q6) (5) Note that Ii and I,are dependent on each other if and only if (iff)i=j-1 because Ij-1 and I;can not both be 1 in ER]=(9地+f(1-9B) (6) the same frame.Other than that,Vi <j-1,I;and Ij are Var(Ro)=f(go -4q+6qi -3q6)+(3q6-8q6 +5q6) independent.Thus, (7) 0 ifi<j-1 PROOF.The expected size of a run of b starting at loca- Cov(Ii,Ij)= -EIE[]=-E[(1-B) tion i is E[S..A run of b starting at location i means that if i=j-1 the slot i-1 is b.Thus Hence we have: EYa=ES6,l+∑ES,dl×P{slot i-1is Var(R)=Var(I1)+Var(Ij)+2Cov(I1,I2) i=2 1=2 "0-+-x +2>Cov(Ij-1,Ij) 1=3 =-或+mú-)-*（色二 =qb(1-9B)+(f-1)g(1-9b){1-qB(1-9b)} 1-9%一 -2q6(1-6)-2(J-2)96(1-9%)2 =∫q地 =f(9%-4g6+6g-3q6)+(3q6-8q+5q6)▣ Each slot i of frame f has probability go of being b.So Y~Binom(f,go).Thus,Var(Yo)is simply the variance of LEMMA 3.Given tag population size t,frame size f,and a binomial distribution with parameters f and g: persistence probability p,we have: Var(Y)=fgo(1-gb) 「1 Cov(Y6,R)=yrq%(1-q)/-".{,,r} Let 72,...,Yf represent the sequence of binary random =0r=0 variables representing the value of each slot in a frame of size -E[Y]E[Ru] (9) f.Since each tag randomly and independently picks a slot in the frame,all i are identically distributed.Furthermore. where P=b}=go.Let Ii be the indicator random variable whose value is 1 if a run of b begins at Yi. ()[2)+2")+--] ifr>1∧0<y<fAr≤yAr≤f-y-1 4={0=)v6=6-1=&i>) (-)[2)+-g-] Thus. 5{f,,r}= ifr=1A0<y<fAr≤yAr≤f-y-1 R=I 1 ifr=1Ay=f =1 Because 1 ifr=0Ay=0 P{Y:=b}=9b if i=1 E[= P{-1=b,=b}=9%(1-96)ifi>1 0 otherwise we get PROOF.By definition,we have E=2=+2n1-)=n+-m》 Cov(Yi,R)=>yPYi=y.R.=r}-E[Yi]E[Rs] =2 y=0T=0 (10) As Ro is the sum of f identically distributed random vari- Here P=y,R=r}represents the probability that ex- ables,we use the general expression for the variance of the actly y out of f slots in the frame are b and at the same time sum of identically distributed random variables to obtain the number of runs of b is r.This probability is difficult to the variance of R. evaluate directly,but conditioning on Yo simplifies the task. P{Y=,B=r}=P{R=rY=}×P{=} Var(Rb)=Var(Ii) (11) As Y~Binom(f,)we have: a+2∑cowu. P=}= (12) j=2i< 369Lemma 2. Let Yb be the random variable representing the number of times b occurs in a frame and Rb be the random variable representing the number of runs of b in a frame. Given tag population size t, frame size f, and persistence probability p, we have: E[Yb] = fqb (4) Var(Yb) = fqb(1 − qb) (5) E[Rb] = qb  qb + f(1 − qb)  (6) Var(Rb) = f(qb − 4q2 b + 6q3 b − 3q4 b ) + (3q2 b − 8q3 b + 5q4 b ) (7) Proof. The expected size of a run of b starting at loca￾tion i is E[Sb,i]. A run of b starting at location i means that the slot i − 1 is b. Thus, E[Yb] = E[Sb,1] + f i=2 E[Sb,i] × P slot i − 1 is b = qb 1 − qb (1 − qf b ) + f i=2 qb 1 − qb (1 − qf−i+1 b ) × (1 − qb) = qb 1 − qb (1 − qf b ) + qb (f − 1) − qf+1 b q−2 b − q −(f+1) b 1 − q−1 b  = fqb Each slot i of frame f has probability qb of being b. So Yb ∼ Binom(f, qb). Thus, Var(Yb) is simply the variance of a binomial distribution with parameters f and qb: Var(Yb) = fqb(1 − qb) Let γ1, γ2,..., γf represent the sequence of binary random variables representing the value of each slot in a frame of size f. Since each tag randomly and independently picks a slot in the frame, all γi are identically distributed. Furthermore, P {γi = b} = qb. Let Ii be the indicator random variable whose value is 1 if a run of b begins at γi. Ii =  1 if (γi = b, i = 1) ∨ (γi = b ∧ γi−1 = b, i > 1) 0 otherwise Thus, Rb =  f i=1 Ii Because E[Ii] =  P {γi = b} = qb if i = 1 P γi−1 = b, γi = b = qb(1 − qb) if i > 1 we get E[Rb] =  f i=1 E[Ii] = qb + f i=2 qb(1 − qb) = qb  qb + f(1 − qb)  As Rb is the sum of f identically distributed random vari￾ables, we use the general expression for the variance of the sum of identically distributed random variables to obtain the variance of Rb. Var(Rb) = Var( f i=1 Ii) =  f i=1 Var(Ii)+2 f j=2  ∀i<j Cov(Ii, Ij ) Here we used the fact that the frame size is always greater than 1 during the estimation process whenever the informa￾tion about runs is used. As Ii ∼ Bernoulli(qb), its variance is that of a bernoulli random variable given by Var(Ii) = E[Ii](1 − E[Ii]) (8) Note that Ii and Ij are dependent on each other if and only if (iff) i = j − 1 because Ij−1 and Ij can not both be 1 in the same frame. Other than that, ∀i<j − 1, Ii and Ij are independent. Thus, Cov(Ii, Ij )= ⎧ ⎨ ⎩ 0 if i<j − 1 −E[Ii]E[Ij ] = −E[Ii]qb(1 − qb) if i = j − 1 Hence we have: Var(Rb) = Var(I1) + f j=2 Var(Ij ) + 2Cov(I1, I2) +2 f j=3 Cov(Ij−1, Ij ) = qb(1 − qb)+(f − 1)qb(1 − qb) {1 − qb(1 − qb)} −2q2 b (1 − qb) − 2(f − 2)q2 b (1 − qb) 2 = f(qb − 4q2 b + 6q3 b − 3q4 b ) + (3q2 b − 8q3 b + 5q4 b ) Lemma 3. Given tag population size t, frame size f, and persistence probability p, we have: Cov(Yb, Rb) =  f y=0  f 2  r=0 yrqy b (1 − qb) f−y.ξ {f, y, r} −E[Yb]E[Rb] (9) where ξ {f, y, r}= ⎧ ⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨ ⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎩ y−1 r−1  f−y−1 r−2  + 2f−y−1 r−1  + f−y−1 r  if r > 1 ∧ 0 <y<f ∧ r ≤ y ∧ r ≤ f − y − 1 y−1 r−1  2 f−y−1 r−1  + f−y−1 r  if r = 1 ∧ 0 <y<f ∧ r ≤ y ∧ r ≤ f − y − 1 1 if r = 1 ∧ y = f 1 if r = 0 ∧ y = 0 0 otherwise Proof. By definition, we have Cov(Yb, Rb) =  f y=0  f r=0 yrP {Yb = y, Rb = r} − E[Yb]E[Rb] (10) Here P {Yb = y, Rb = r} represents the probability that ex￾actly y out of f slots in the frame are b and at the same time the number of runs of b is r. This probability is difficult to evaluate directly, but conditioning on Yb simplifies the task. P {Yb = y, Rb = r} = P {Rb = r|Yb = y} × P {Yb = y} (11) As Yb ∼ Binom(f, qb), we have: P {Yb = y} =  f y  qy b (1 − qb) f−y (12) 369