We first take logarithm on both sides of(20) 20000 In(L:)= 1 (1+e)z-Np)2 15000 =l+1 /2πNp(1-p5) 2Np5(1-p5) (22) 10000 We then differentiate both sides. 5000 = 1 (1+e)2x号-(Np)2 =141 2N2p5(1-P） 2004006008001000 number of pollings (1+e)2x号-(Np)2i-l = 2N (23) Fig.4.The middle curve shows the estimated number of tags with respect =l41 2N2p5(1-P5) to the number of pollings.The upper and lower curves show the confidence interval.The straightline shows the true number of tags. Finally we set the right side to be zero and numerically compute the value of Ni. 2)Termination Condition:The fisher information2 I(Ni) TABLE I of Li is defined as follows NUMBER OF RESPONSES WHEN a =90%,B=5% I(Ni)=-E 「a21n(L) (24) Total number of responses N ON2 MLEAT ASEA I EMLEAT UPE-OT UPE-M EZB 5000 2669S 1083S 768S 783L 2415 1030S According to (23),we have 10000 2659S 1083S 763S 13498L 2432L 20261S 200002654S1081S 775S24455L2431L 40521S Z)=E∑ (1+e)2x号 i-1 TABLE II =1+1 N3p1-p5)-2N2 NUMBER OF RESPONSES WHEN Q =95%,B=5% N Total number of responses (Npj)2+Npi(1-Pi)i-l MLEA ASEA EMLEA UPE-O UPE-M EZB 2N2 25 N3p5(1-pj） 5000 3798S 1543S 1083S 8740L 3437L 14472S 1I0000 3776S 1543S 1101S 14573L 3507L 28944S 200003789S 1545S■ 1099S25515L3450L 57888S 盆”+ Pi i-l TABLEⅢI NUMBER OF RESPONSES WHEN =99%.B=5% Above,we applied E((1+)2)=(Npj)2+Npj(1-Pi)in N Total number of responses MLEA ASEAI EMLEAI UPE-O UPE-MI EZB (25)since(1+s)zj~Norm(Npj;Npj(1-pj))and E(z2)= 5D0 6542S 2658S 1857S 11262L 5885L 24602S (E(z))2+Var(z). 10000 6546S 2654S 1862S 16969L 5935L 49205S Following the classical theory for MLE,when i is suffi- 20000 6543S 2655S I887S 28379L5939L 98409S ciently large,the distribution of Ni is approximated by 1 Norm(N, (26) TABLE IV I(Ni) NUMBER OF RESPONSES WHEN Q =99%,B=9% Hence,the confidence interval is Total number of responses N MLEA ASEA EMLEA UPE-M EZB 1 5000 2005S 815S 557S 1802L 7236S N:±Za (27 I00002083S 839S 551s 1929L 14472S I(Ni) 200002027S 819S■ 556S 1755L 28944S Note that we use N;as an approximation for N in the com- TABLE V NUMBER OF RESPONSES WHEN Q =99%,B=6% putation when necessary since N is unknown.The termination condition for EMLEA to achieve the required accurary is N Total number of responses MLEA ASEA EMLEA UPE-M EZB 5000 4766S1835S 1260S 3942L 17366S 1 ≤N· (28) 10000 4756S1833S 240S 4063L0 34733S I(Ni) 200004775S■1852S1227S 3993L 69465S TABLE VI Fig.4 shows the simulation result of EMLEA when N NUMBER OF RESPONSES WHEN Q =99%,B=3% 10,000,a 95%and B =5%.The middle curve is the value of Ni,which converges to the value of N represented by N Total number of responses MLEAT ASEAT EMLEAT UPE-M EZB the central straight line.The upper and lower curves represent 5000 16263S 7308S 5014S 15924L 65124S the 95%confidence interval,which shrinks as the number 10000 16211S 7345S 4942S 16830L 130247S of pollings increases.The algorithm terminates after 1081 2000016291S7376S 5055S 16647L 260495S pollings.We first take logarithm on both sides of (20). ln(Li) = Xi j=l+1 · ln 1 p 2πN pj (1 − pj ) − ((1 + ε)xj − N pj ) 2 2N pj (1 − pj ) ¸ . (22) We then differentiate both sides. ∂ln(Li) ∂N = Xi j=l+1 · − 1 2N + (1 + ε) 2x 2 j − (N pj ) 2 2N2pj (1 − pj ) ¸ = Xi j=l+1 (1 + ε) 2x 2 j − (N pj ) 2 2N2pj (1 − pj ) − i − l 2N . (23) Finally we set the right side to be zero and numerically compute the value of Nˆ i . 2) Termination Condition: The fisher information2 I(Nˆ i) of Li is defined as follows I(Nˆ i) = −E · ∂ 2 ln(Li) ∂N2 ¸ . (24) According to (23), we have I(Nˆ i) = E · X i j=l+1 (1 + ε) 2x 2 j N3pj (1 − pj ) − i − l 2N2 ¸ = X i j=l+1 (N pj ) 2 + N pj (1 − pj ) N3pj (1 − pj ) − i − l 2N2 (25) = X i j=l+1 pj N(1 − pj ) + i − l 2N2 . Above, we applied E((1+ε) 2x 2 j ) = (N pj ) 2+N pj (1−pj ) in (25) since (1+ε)xj ∼ Norm(N pj , N pj (1−pj )) and E(x 2 ) = (E(x))2 + V ar(x). Following the classical theory for MLE, when i is suffi- ciently large, the distribution of Nˆ i is approximated by Norm(N, 1 I(Nˆ i) ). (26) Hence, the confidence interval is Nˆ i ± Zα · s 1 I(Nˆ i) . (27) Note that we use Nˆ i as an approximation for N in the com￾putation when necessary since N is unknown. The termination condition for EMLEA to achieve the required accurary is Zα · s 1 I(Nˆ i) ≤ Nˆ i · β. (28) Fig. 4 shows the simulation result of EMLEA when N = 10, 000, α = 95% and β = 5%. The middle curve is the value of Nˆ i , which converges to the value of N represented by the central straight line. The upper and lower curves represent the 95% confidence interval, which shrinks as the number of pollings increases. The algorithm terminates after 1081 pollings. 0 5000 10000 15000 20000 0 200 400 600 800 1000 number of pollings Fig. 4. The middle curve shows the estimated number of tags with respect to the number of pollings. The upper and lower curves show the confidence interval. The straightline shows the true number of tags. TABLE I NUMBER OF RESPONSES WHEN α = 90%, β = 5% N Total number of responses MLEA ASEA EMLEA UPE-O UPE-M EZB 5000 2669 S 1083 S 768 S 7833 L 2415 L 10130 S 10000 2659 S 1083 S 763 S 13498 L 2432 L 20261 S 20000 2654 S 1081 S 775 S 24455 L 2431 L 40521 S TABLE II NUMBER OF RESPONSES WHEN α = 95%, β = 5% N Total number of responses MLEA ASEA EMLEA UPE-O UPE-M EZB 5000 3798 S 1543 S 1083 S 8740 L 3437 L 14472 S 10000 3776 S 1543 S 1101 S 14573 L 3507 L 28944 S 20000 3789 S 1545 S 1099 S 25515 L 3450 L 57888 S TABLE III NUMBER OF RESPONSES WHEN α = 99%, β = 5% N Total number of responses MLEA ASEA EMLEA UPE-O UPE-M EZB 5000 6542 S 2658 S 1857 S 11262 L 5885 L 24602 S 10000 6546 S 2654 S 1862 S 16969 L 5935 L 49205 S 20000 6543 S 2655 S 1887 S 28379 L 5939 L 98409 S TABLE IV NUMBER OF RESPONSES WHEN α = 99%, β = 9% N Total number of responses MLEA ASEA EMLEA UPE-M EZB 5000 2005 S 815 S 557 S 1802 L 7236 S 10000 2083 S 839 S 551 S 1929 L 14472 S 20000 2027 S 819 S 556 S 1755 L 28944 S TABLE V NUMBER OF RESPONSES WHEN α = 99%, β = 6% N Total number of responses MLEA ASEA EMLEA UPE-M EZB 5000 4766 S 1835 S 1260 S 3942 L 17366 S 10000 4756 S 1833 S 1240 S 4063 L 34733 S 20000 4775 S 1852 S 1227 S 3993 L 69465 S TABLE VI NUMBER OF RESPONSES WHEN α = 99%, β = 3% N Total number of responses MLEA ASEA EMLEA UPE-M EZB 5000 16263 S 7308 S 5014 S 15924 L 65124 S 10000 16211 S 7345 S 4942 S 16830 L 130247 S 20000 16291 S 7376 S 5055 S 16647 L 260495 S