Outputs in random \(f\)-ary recursive circuits

Mehri Javanian
Department of Statistics, Zanjan University, Zanjan, Iran.
Mohammad Q. Vahidi-Asl
Department of Statistics, Shahid Beheshti University, Tehran, Iran.

\(^{1}\)Corresponding Author: javanian− m@yahoo.com

Copyright © 2011 Mehri Javanian, Mohammad Q. Vahidi-Asl. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Published: December, 2011.

Abstract

This paper extends the study of outputs for random recursive binary circuits in Tsukiji and Mahmoud (Algorithmica 31(2001), 403). We show via martingales that a suitably normalized version of the number of outputs in random f-ary recursive circuits converges in distribution to a normal random variate.

Keywords:

Analysis of algorithm, recursive circuit, martingale central limit theorem.