Probabilistic sampling of finite renewal processes. (English) Zbl 1229.62111

Antunes, Nelson; Pipiras, Vladas

Bernoulli 17, No. 4, 1285-1326 (2011).

Summary: Consider a finite renewal process in the sense that inter-renewal times are positive i.i.d. variables and the total number of renewals is a random variable, independent of inter-renewal times. A finite point process can be obtained by probabilistic sampling of the finite renewal process, where each renewal is sampled with a fixed probability and independently of other renewals. The problem addressed in this work concerns statistical inference of the original distributions of the total number of renewals and inter-renewal times from a sample of i.i.d. finite point processes obtained by sampling finite renewal processes. This problem is motivated by traffic measurements in the Internet in order to characterize flows of packets (which can be seen as finite renewal processes) and where the use of packet sampling is becoming prevalent due to increasing link speeds and limited storage and processing capacities.

MSC:

62M09	Non-Markovian processes: estimation
60K05	Renewal theory
62M99	Inference from stochastic processes
62G20	Asymptotic properties of nonparametric inference
65C60	Computational problems in statistics (MSC2010)

Keywords:

IP flows; finite renewal process; number of renewals; sampling; thinning; asymptotic normality; decompounding

References:

[1]	Billingsley, P. (1999). Convergence of Probability Measures , 2nd ed. New York: Wiley. · Zbl 0944.60003
[2]	Bingham, N.H., Goldie, C.M. and Teugels, J.L. (1987). Regular variation. Encyclopedia of Mathematics and Its Applications 27 . Cambridge: Cambridge Univ. Press. · Zbl 0617.26001
[3]	Bøgsted, M. and Pitts, S.M. (2010). Decompounding random sums: A nonparametric approach. Ann. Inst. Statist. Math. 62 855-872. · Zbl 1432.60049 · doi:10.1007/s10463-008-0200-6
[4]	Buchmann, B. (2001). Decompounding: An estimation problem for the compound Poisson distribution. Ph.D. thesis, Univ. Hannover.
[5]	Buchmann, B. and Grübel, R. (2003). Decompounding: An estimation problem for Poisson random sums. Ann. Statist. 31 1054-1074. · Zbl 1105.62309 · doi:10.1214/aos/1059655905
[6]	Chabchoub, Y., Fricker, C., Guillemin, F. and Robert, P. (2010). On the statistical characterization of flows in Internet traffic with application to sampling. Comput. Commun. 31 103-112.
[7]	Clegg, R.G., Landa, R., Haddadi, H., Rio, M. and Moore, A.W. (2008). Techniques for flow inversion on sampled data. In 2008 IEEE INFOCOM Workshops 1-6.
[8]	Cox, D.R. and Isham, V. (1980). Point Processes . London: Chapman and Hall. · Zbl 0441.60053
[9]	Daley, D.J. and Vere-Jones, D. (2003). An Introduction to the Theory of Point Processes. Vol. I , 2nd ed. New York: Springer. · Zbl 1026.60061 · doi:10.1007/b97277
[10]	Duffield, N., Lund, C. and Thorup, M. (2002). Properties and prediction of flow statistics from sampled packet streams. In Proc. ACM SIGCOMM Internet Measurement Workshop 159-171.
[11]	Duffield, N., Lund, C. and Thorup, M. (2005). Estimating flow distributions from sampled flow statistics. IEEE/ACM Transactions on Networking 13 933-946.
[12]	Estan, C. and Varghese, G. (2002). New directions in traffic measurement and accounting. In SIGCOMM’02. Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications 323-336.
[13]	Grübel, R. and Pitts, S.M. (1993). Nonparametric estimation in renewal theory. I. The empirical renewal function. Ann. Statist. 21 1431-1451. · Zbl 0818.62037 · doi:10.1214/aos/1176349266
[14]	Hall, P. and Park, J. (2004). Nonparametric inference about service time distribution from indirect measurements. J. R. Stat. Soc. Ser. B. Stat. Methodol. 66 861-875. · Zbl 1059.62029 · doi:10.1111/j.1467-9868.2004.B5725.x
[15]	Hansen, M.B. and Pitts, S.M. (2006). Nonparametric inference from the M / G /1 workload. Bernoulli 12 737-759. · Zbl 1125.62091 · doi:10.3150/bj/1155735934
[16]	Henrici, P. (1974). Applied and Computational Complex Analysis . New York: Wiley. · Zbl 0313.30001
[17]	Hohn, N. and Veitch, D. (2006). Inverting sampled traffic. IEEE/ACM Transactions on Networking 14 68-80.
[18]	Hohn, N., Veitch, D. and Abry, P. (2003). Cluster processes: A natural language for network traffic. IEEE Trans. Signal Process. 51 2229-2244. · doi:10.1109/TSP.2003.814460
[19]	Karr, A.F. (1991). Point Processes and Their Statistical Inference , 2nd ed. Probability: Pure and Applied 7 . New York: Marcel Dekker. · Zbl 0733.62088
[20]	Pollard, D. (1984). Convergence of Stochastic Processes . New York: Springer. · Zbl 0544.60045
[21]	Robert, C.Y. and Segers, J. (2008). Tails of random sums of a heavy-tailed number of light-tailed terms. Insurance Math. Econom. 43 85-92. · Zbl 1154.60032 · doi:10.1016/j.insmatheco.2007.10.001
[22]	Tune, P. and Veitch, D. (2008). Towards optimal sampling for flow size estimation. In ACM SIGCOMM Internet Measurement Conference 243-256.
[23]	Vakhania, N.N., Tarieladze, V.I. and Chobanyan, S.A. (1987). Probability Distributions on Banach Spaces. Mathematics and Its Applications (Soviet Series) 14 . Dordrecht: D. Reidel Publishing. · Zbl 0698.60003
[24]	Yang, L. and Michailidis, G. (2007). Sampled based estimation of network traffic flow characteristics. In INFOCOM 2007. 26th IEEE International Conference on Computer Communications 1775-1783.