اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدEntropy of Mersenne-Twisters
37
0
0.0
(
0
)
تأليف
Fabien Le Floch
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
The Mersenne-Twister is one of the most popular generators of uniform pseudo-random numbers. It is used in many numerical libraries and software. In this paper, we look at the Komolgorov entropy of the original Mersenne-Twister, as well as of more modern variations such as the 64-bit Mersenne-Twisters, the Well generators, and the Melg generators.
قيم البحث
اقرأ أيضاً
When the Mersenne Twister made his first appearance in 1997 it was a powerful example of how linear maps on $mathbf F_2$ could be used to generate pseudorandom numbers. In particular, the easiness with which generators with long periods could be defi
ned gave the Mersenne Twister a large following, in spite of the fact that such long periods are not a measure of quality, and they require a large amount of memory. Even at the time of its publication, several defects of the Mersenne Twister were predictable, but they were somewhat obscured by other interesting properties. Today the Mersenne Twister is the default generator in C compilers, the Python language, the Maple mathematical computation system, and in many other environments. Nonetheless, knowledge accumulated in the last $20$ years suggests that the Mersenne Twister has, in fact, severe defects, and should never be used as a general-purpose pseudorandom number generator. Many of these results are folklore, or are scattered through very specialized literature. This paper surveys these results for the non-specialist, providing new, simple, understandable examples, and it is intended as a guide for the final user, or for language implementors, so that they can take an informed decision about whether to use the Mersenne Twister or not.
In this research paper, relationship between every Mersenne prime and certain Natural numbers is explored. We begin by proving that every Mersenne prime is of the form {4n + 3,for some integer n} and generalize the result to all powers of 2. We also
tabulate and show their relationship with other whole numbers up to 10. A number of minor results are also proved. Based on these results, approaches to determine the cardinality of Mersenne primes are discussed.
We investigate various questions concerning the reciprocal sum of divisors, or prime divisors, of the Mersenne numbers $2^n-1$. Conditional on the Elliott-Halberstam Conjecture and the Generalized Riemann Hypothesis, we determine $max_{nle x} sum_{p
mid 2^n-1} 1/p$ to within $o(1)$ and $max_{nle x} sum_{dmid 2^n-1}1/d$ to within a factor of $1+o(1)$, as $xtoinfty$. This refines, conditionally, earlier estimates of ErdH{o}s and ErdH{o}s-Kiss-Pomerance. Conditionally (only) on GRH, we also determine $sum 1/d$ to within a factor of $1+o(1)$ where $d$ runs over all numbers dividing $2^n-1$ for some $nle x$. This conditionally confirms a conjecture of Pomerance and answers a question of Murty-Rosen-Silverman. Finally, we show that both $sum_{pmid 2^n-1} 1/p$ and $sum_{dmid 2^n-1}1/d$ admit continuous distribution functions in the sense of probabilistic number theory.
Compressed Counting (CC)} was recently proposed for approximating the $alpha$th frequency moments of data streams, for $0<alpha leq 2$. Under the relaxed strict-Turnstile model, CC dramatically improves the standard algorithm based on symmetric stabl
e random projections}, especially as $alphato 1$. A direct application of CC is to estimate the entropy, which is an important summary statistic in Web/network measurement and often serves a crucial feature for data mining. The Renyi entropy and the Tsallis entropy are functions of the $alpha$th frequency moments; and both approach the Shannon entropy as $alphato 1$. A recent theoretical work suggested using the $alpha$th frequency moment to approximate the Shannon entropy with $alpha=1+delta$ and very small $|delta|$ (e.g., $<10^{-4}$). In this study, we experiment using CC to estimate frequency moments, Renyi entropy, Tsallis entropy, and Shannon entropy, on real Web crawl data. We demonstrate the variance-bias trade-off in estimating Shannon entropy and provide practical recommendations. In particular, our experiments enable us to draw some important conclusions: (1) As $alphato 1$, CC dramatically improves {em symmetric stable random projections} in estimating frequency moments, Renyi entropy, Tsallis entropy, and Shannon entropy. The improvements appear to approach infinity. (2) Using {em symmetric stable random projections} and $alpha = 1+delta$ with very small $|delta|$ does not provide a practical algorithm because the required sample size is enormous.
The property of Tsallis entropy is examined when considering tow systems with different temperatures to be in contact with each other and to reach the thermal equilibrium. It is verified that the total Tsallis entropy of the two systems cannot decrea
se after the contact of the systems. We derived an inequality for the change of Tsallis entropy in such an example, which leads to a generalization of the principle of entropy increase in the framework of nonextensive statistical mechanics.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
