An Insight into the Data Structure of the Dynamic Batch Means Algorithm with Binary Tree Code

Abstract

Batching is a well-known method used to estimate the variance of the sample mean in steady-state simulation. Dynamic batching is a novel technique employed to implement traditional batch means estimators without the knowledge of the simulation run length a priori. In this study, we reinvestigated the dynamic batch means (DBM) algorithm with binary tree hierarchy and further proposed a binary coding idea to construct the corresponding data structure. We also present a closed-form expression for the DBM estimator with binary tree coding idea. This closed-form expression implies a mathematical expression that clearly defines itself in an algebraic binary relation. Given that the sample size and storage space are known in advance, we can show that the computation complexity in the closed-form expression for obtaining the indexes c j ( k ) , i.e., the batch mean shifts s , is less than the effort in recursive expression.

Keywords

• estimation
• simulation
• variance of the sample mean
• dynamic batch means
• binary tree code