다음과 같은 기능을 한번의 로그인으로 사용 할 수 있습니다.
NTIS 바로가기
韓國컴퓨터情報學會論文誌 = Journal of the Korea Society of Computer and Information, v.18 no.2, 2013년, pp.19 - 30
AI-Helper
We study sub-Peres functions that are defined recursively as Peres function for random number generation. Instead of using two parameter functions as in Peres function, the sub-Peres functions uses only one parameter function. Naturally, these functions produce less random bits, hence are not asympt...
| 핵심어 | 질문 | 논문에서 추출한 답변 |
|---|---|---|
| 폰 노이만에 의해 제안된 편향이 있는 무작위 수를 보정하는 방법은? | 편향이 있는 무작위수를 보정하는 가장 오래되고 유명한 방법은 폰 노이만(von Neumann)에 의해 제안된 다음의 방법이다[3]. 앞면이 나올 사건을 H라 하고 그 확률이 p이고, 뒷면이 나올 사건을 T라 하고 확률이 q = 1-p인 동전을 생각하자. 이때 동전을 두 번 던져서 생기는 확률적 사건들은, 앞면이 두 번 연속으로 나오는 HH, 앞면과 뒷면이 이어 나오는 HT, 뒷면과앞면이 이어 나오는 TH 그리고 뒷면이 두번 연속으로 나오는 TT로 네 가지가 있다. 이 중 HH나 TT의경우 이 사건들을 무시하고 다시 동전을 두번 던지고, HT인 경우 이를 0으로 간주하고, TH가 나오는 경우 1로 간주하자. 이를 사상으로 표현하면, 출력이 없는 경우를 λ로 표현할 때, HH↦λ, HT↦0, TH↦1, TT↦λ, 로 나타낼 수 있다. 그러면 Pr[0이 나올사건] = Pr[HT] = pq, Pr[1이 나올사건] = Pr[TH] = pq 이 되어, 위 방법이 0을 출력할 확률과 1을 출력할 확률이 pq로 같음을 알 수 있다. 따라서 주어진 동전의 편향 p의 값에 상관없이 이 방법에 의해 출력되는 0과 1은 항상 같은 확률로 나타난다. | |
| 무작위수는 생성의 관점에 따라 어떻게 나뉘는가? | 무작위수는 그 생성(generation)의 관점에서 크게 유사무작위수(pseudorandom number)와 진성무작위수(true random number)로 나눈다. 유사무작위수는 정해진 알고리즘에 의해 생성되어, 그 통계적 성질이 미리 잘 연구되어져서 그 쓰임새에 적합하도록 설계할 수 있고, 또한 컴퓨터의 속도만큼 빠르게 대량으로 생성할 수 있고, 무엇보다도 재생성(reproduce)할 수 있다는 것이 장점이다. | |
| 메모리 측면에서 부 페레즈 함수가 페레즈함수보다 좋은 점은? | 그러나, O(n logn)의 시간복잡도를 갖는 페레즈 함수에 비하여, 부 페레즈 함수들은 선형시간, 즉 O(n)의 시간에 실행된다. 더구나, 이 함수들은 하나의 인자함수를 쓰기 때문만이 아니라 꼬리재귀함수로서 간단한 반복수행에 의해 구현되어 페레즈 함수보다 더 적은 메모리로 구현될 수 있다. 그럼에도, 이 함수들은 널리 알려진 선형시간 알고리즘인 폰 노이만 방법보다 출력효율이 최대 두 배 이상 높다. |
P. Diaconis. The search for randomness. at American Association for the Advancement of Science annual meeting. Feb. 14, 2004. Seattle.P. Diaconis, S. Holmes, and R. Montgomery.
P. Diaconis, S. Holmes, and R. Montgomery, Dynamical bias in the coin toss. SIAM Review, Vol. 49, No. 2, p.211, 2007.
John von Neumann. Various techniques for use in connection with random digits. Notes by G. E. Forsythe. In Monte Carlo Method, Applied Mathematics Series, volume 12, pages 36-38. U.S. National Bureau of Standards, Washington D.C., 1951. Reprinted in von Neumann's Collected Works 5 (Pergammon Press, 1963), 768-770.
B. Jun and P. Kocher. The Intel random number generator. White paper prepared for Intel Corporation, 1999. Cryptography Research, Inc.
C. E. Shannon and W. Weaver. The Mathematical Theory of Communication. The University of Illinois Press, Urbana, 1964.
T. M. Cover and J. A. Thomas. Elements of Information Theory. Wiley Series in Telecommunications. John Wiley & Sons, New York, NY, USA, 1991.
Peter Elias. The efficient construction of an unbiased random sequence. The Annals of Mathematical Statistics, Vol. 43, No.3, pp. 865-870, 1972.
Yuval Peres. Iterating von Neumann's procedure for extracting random bits. Annals of Statistics, Vol. 20, No. 1, pp. 590-597, 1992.
Sung-il Pae and Michael C. Loui. Optimal random number generation from a biased coin. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1079-1088, January 2005.
Sung-il Pae and Michael C. Loui. Randomizing functions: Simulation of discrete probability distribution using a source of unknown distribution. IEEE Transactions on Information Theory, Vol. 52, No. 11, pp. 4965-4976, November 2006.
Sung-il Pae. Exact Computation of Output Rate of Peres's Algorithm for Random Number Generation, Information Processing Letters, 2013, to appear.
Min-su Kim, A Hybrid Randomizing Function Using Peres-Elias Method for Efficient Generation of Random Bits, Master's thesis, Hongik University, 2012.
*원문 PDF 파일 및 링크정보가 존재하지 않을 경우 KISTI DDS 시스템에서 제공하는 원문복사서비스를 사용할 수 있습니다.
Free Access. 출판사/학술단체 등이 허락한 무료 공개 사이트를 통해 자유로운 이용이 가능한 논문
Copyright KISTI. All Rights Reserved.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.