blocks|key|154146|text|对于黑盒测试(你不能访问源代码)，你不能证明它是均匀分布的(UD)。但是，您可以执行统计测试来发现它是UD的可能性。运行生成器多次(例如，N*X次)，0到N之间的每个数字应该出现X次左右。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|154147|这完全忽略了它是否是随机数，它只关注一致性。但是，如果您要运行无限测试，它只会证明生成器是均匀分布的。在最好的情况下，生成器在最初的N*X次迭代中是一致的，但它很简单，很容易实现。|154148|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

For black-box testing (you dont have access to the source code), you can't prove it is uniformly distributed (UD). You can, however, perform statistical tests to find the likelihood of it being UD. Run the generator many times (say, N*X times) and each number between 0 and N should have appeared around X times. 

This completely ignores whether it's random numbers or not, it just focuses on uniformity. However, it would only prove that the generator was uniformly distributed if you were to run infinite tests. At best, you have a probability of the generator being uniform during the first N*X iterations, but it is simple and easy to implement.

blocks|key|2737946|text|没有办法证明这一点，因为生成器可能首先生成均匀分布，然后偏离到非均匀分布。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2737947|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

There is no way to prove it, because the generator might first generate a uniform distribution and later deviate into a non-uniform one.

blocks|key|2737963|text|生成器中只有一个数字，或者想要多少就有多少？如果只有一个，你不能说任何关于一致性的话。只要0≤number+<+N，就可以了。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2737964|假设面试官的意思是“大量结果的一致性”，你需要同时查看结果的分布和结果中的模式。第一种方法是对结果进行排序和装箱，并查看结果直方图。对于大量的值，它应该是合理的“平坦”(例如，不是高斯曲线)。|2737965|第二个测试有点困难，因为您可能会得到2个、3个、甚至4个或更多数字长度的模式。对于三元组，我看到的一个测试是在球面坐标(第一个是方位角，第二个是高度，第三个是半径)中以三个一组绘制结果。我不记得细节了，但是IIRC，你应该看到一个均匀填充的球体，或者类似的东西。这个测试可能有一个正式的术语，但底线是有许多测试来查看RNG正在做什么，因此很难从最后一个数字预测下一个数字(没有明显的模式)。|2737966|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|H|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|I|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|J|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|G|$]]

Just one number from the generator, or as many as you want? If just one, you can't say anything about uniformity. So long as 0 &le; number &lt; N, it's OK.

Assuming the interviewer meant "[the uniformity of] a large number of results", you need to look at both the resulting distribution, and for patterns in the results. The first would be to sort and bin the results and look at the resulting histogram. It should be reasonably "flat" (e.g., not a Gaussian curve) for a large number of values.

The second test is a bit more difficult, as you could be getting patterns 2, 3, or even 4 or more numbers long. One test I saw, for triplets, is to plot the results in groups of three, in spherical coordinates (first is the azimuth, second is the altitude, and the third is the radius). I don't remember the details, but IIRC you should be seeing a uniformly filled sphere, or something like that. There's probably a formal term for this test, but the bottom line is there are a number of tests to see what a RNG is doing, so that the next number out is difficult to predict from the last number out (no apparent pattern to it).

blocks|key|155643|text|我会先问他们什么时候会想要答案，以及一旦你有了生成器，他们会想要多好的答案。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|155644|是的，如果你想进行全面的统计测试，运行一套全面的统计测试是很好的。但这可能需要几天或几周的时间。在某些情况下，这个问题可能是在一群人想要立即回答的会议上提出的，而最好的答案可能就是在会议中使用google，看看其他用户认为生成器是否“足够好”。在“快速谷歌”和“综合测试”之间有一系列的答案。|155645|在现实中，你不能证明生成器在所有情况下都是100%25一致的，这是加分。这些案例包括：|155646|1)不能查看源码。因此，即使您生成N个看起来一致的随机数，也无法在不生成更多数字的情况下知道从N%2B1开始的每个数字都是10+(例如)。无论您停在哪里，您都不能对尚未生成的数字做出任何声明|155647|2)您可以查看源码。它可能太难看了，很难理解，除非它是一个非常简单的线性同余生成器。如果它太难看了，我会说，除了欣赏代码之外，你可能无法得出任何可靠的结论。|155648|尽管有风险，但值得一提的是，如果应用程序对随机数生成器的调用次数是可预测的，那么您可以测试该生成器的调用次数。然而，我见过一些面试官会误解这一点，并认为你不知道如何制作健壮和可伸缩性好的算法。|155649|entityMap^0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|O|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|P|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|Q|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|R|8|@]|9|@]|A|$]]|$1|J|3|K|5|6|7|S|8|@]|9|@]|A|$]]|$1|L|3|-4|5|6|7|T|8|@]|9|@]|A|$]]]|M|$]]

I'd start by asking how soon they would want an answer, and how good an answer they would want once you had the generator.

Yes, running a comprehensive set of statistical tests is nice if you want to be thorough. But that may take days or weeks. In some situations, the question may be asked in a meeting with a bunch of people wanting an answer right away, and the best answer may just be to use google right there in the meeting to see if the generator is 'good enough' according to other users. There is a whole spectrum of answers between 'quick google' and 'comprehensive tests'.

Bonus points for mentioning that in REALISTICALLY you cannot prove the generator is 100% uniform in all situations. The cases are:

1) You cannot look at the source code. So even if you generate N random numbers that look uniform, there is no way to know that every number from N+1 on is 10 (for example) without generating more numbers. No matter where you stop, you cannot make any claims about the numbers you have not yet generated

2) You can look at the source code. It's probably too ugly to understand, unless it's a very simple Linear Congruential Generator. If it's too ugly, I'd say that besides admiring the code you probably could not make any solid conclusions.

Although risky, it may be worth mentioning that if the application has a predictable number of calls to the random number generator, then you could test that generator for that many calls. However, I've seen some interviewers who would misinterpret this and assume that you don't know how to make algorithms that are robust and scale well.

blocks|key|155678|text|在Princeton+Companion+to+Mathematics中有一个关于这方面的讨论|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|155679|155680|，然而，人们如何使用确定性计算机来选择1030到1031之间的10000个随机数呢？答案是，人们实际上不需要这样做:做一个伪随机选择几乎总是足够好的。..。|blockquote|155681|155682|我们什么时候应该把这样的序列看作是“随机的”呢？再说一遍，已经有很多不同的答案。一种想法是考虑简单的统计测试:我们期望从长远来看，0的频率应该与1的频率大致相同，更普遍的是，任何像00110这样的小的子序列都应该以“正确”的频率出现(对于这个序列来说是1/32，因为它的长度是5)。|style|BOLD|155683|然而，序列完全有可能通过这些简单的测试，但由确定性过程生成。如果有人试图确定一个由0和1组成的序列是否真的是随机的-也就是说，通过某种方式产生，比如扔硬币-那么我们将非常怀疑一个序列，如果我们能识别出一个产生相同序列的算法。例如，我们将拒绝以简单方式从π数字派生的序列，即使它通过了统计测试。然而，仅仅要求递归过程不能产生序列并不能很好地测试随机性:例如，如果取任何这样的序列，并将该序列的项替换为零，那么就会获得一个远不是随机的新序列，但仍然不能递归产生。|155684|出于这个原因，冯米塞斯在1919年建议，如果一个由0和1组成的序列不仅是1的频率限制是1/2的情况，而且对于可以“通过合理的程序”提取的任何子序列也是如此，则应该将0和1的序列称为随机序列。1940年，丘奇将“通过合理的程序”翻译为“通过递归函数”，从而使这一点更加准确。然而，即使是这个条件也太弱了:有这样的序列不满足“重对数律”(随机序列会满足的东西)。目前，1966年提出的所谓的Martin-Löf命题是随机性最常用的定义之一:随机序列是满足所有“有效统计序列检验”的序列，我们在这里无法精确地阐述这个概念，但它以一种基本的方式使用了递归函数的概念。与丘奇的论点形成鲜明对比的是，几乎每个数学家都同意这一论点，而马丁-洛夫的论点仍在讨论中。|155685|entityMap|0|LINK|mutability|MUTABLE|url|http://books.google.co.uk/books?id=ZOfUsvemJDMC&lpg=PA116&dq=%2522when%2520should%2520we%2520regard%2520such%2520a%2520sequence%2520as%2520random%253F%2522&pg=PA116#v=onepage&q=%2522when%2520should%2520we%2520regard%2520such%2520a%2520sequence%2520as%2520random?%2522&f=false^0|1|Y|0|0|0|0|0|0|O|0|0|0^^$0|@$1|2|3|4|5|6|7|Y|8|@]|9|@$A|Z|B|10|1|11]]|C|$]]|$1|D|3|-4|5|6|7|12|8|@]|9|@]|C|$]]|$1|E|3|F|5|G|7|13|8|@]|9|@]|C|$]]|$1|H|3|-4|5|6|7|14|8|@]|9|@]|C|$]]|$1|I|3|J|5|6|7|15|8|@$A|16|B|17|K|L]]|9|@]|C|$]]|$1|M|3|N|5|6|7|18|8|@]|9|@]|C|$]]|$1|O|3|P|5|6|7|19|8|@]|9|@]|C|$]]|$1|Q|3|-4|5|6|7|1A|8|@]|9|@]|C|$]]]|R|$S|$5|T|U|V|C|$W|X]]]]

There's an accessible discussion of this in the <a href="http://books.google.co.uk/books?id=ZOfUsvemJDMC&amp;lpg=PA116&amp;dq=%22when%20should%20we%20regard%20such%20a%20sequence%20as%20random%3F%22&amp;pg=PA116#v=onepage&amp;q=%22when%20should%20we%20regard%20such%20a%20sequence%20as%20random?%22&amp;f=false" rel="nofollow">Princeton Companion to Mathematics</a>

<blockquote>
 How, though, does one use a deterministic computer to
 select ten thousand random numbers between 10 30 and
 10 31 ? The answer is that one does not in fact need to: it is almost always good enough to make a pseudorandom selection instead. ...
 
 When should we regard such a sequence as “random”? Again, many different answers have been suggested. One idea is to consider simple statistical tests: we
 would expect that in the long run the frequency of zeros
 should be roughly the same as that of ones, and more
 generally that any small subsequence such as 00110
 should appear with the “right” frequency (which for
 this sequence 1/32 would be since it has length 5).
 
 It is perfectly possible, however, for a sequence to
 pass these simple tests but to be generated by a deterministic procedure. If one is trying to decide whether
 a sequence of zeros and ones is actually random—
 that is, produced by some means such as tossing a
 coin—then we will be very suspicious of a sequence if
 we can identify an algorithm that produces the same
 sequence. For example, we would reject a sequence that
 was derived in a simple way from the digits of π, even
 if it passed the statistical tests. However, merely to ask that a sequence cannot be produced by a recursive procedure does not give a good test for randomness: for
 example, if one takes any such sequence and alternates
 the terms of that sequence with zeros, one then obtains
 a new sequence that is far from random, but which still
 cannot be produced recursively.
 
 For this reason, von Mises suggested in 1919 that a
 sequence of zeros and ones should be called random if
 it is not only the case that the limit of the frequency of ones is 1/2, but also that the same is true for any subsequence that can be extracted “by means of a reasonable procedure.” In 1940 Church made this more precise by translating “by means of a reasonable procedure” into
 “by means of a recursive function.” However, even this
 condition is too weak: there are such sequences that
 do not satisfy the “law of the iterated logarithm” (something that a random sequence would satisfy). Currently,
 the so-called Martin–Löf thesis, formulated in 1966, is
 one of the most commonly used definitions of random-
 ness: a random sequence is a sequence that satisfies all
 the “effective statistical sequential tests,” a notion that we cannot formulate precisely here, but which uses in
 an essential manner the notion of recursive function. By
 contrast with Church’s thesis, with which almost every
 mathematician agrees, the Martin–Löf thesis is still very much under discussion.
</blockquote>

blocks|key|152952|text|对于面试来说，这是一个有点残酷的问题(除非这是一个研究职位)，但对于论坛来说，这是一个有趣的问题。20年前，在完成我的数学学位后，我会很高兴地展示一个我自己编写的随机生成器，并用数学证明它是随机的。现在看着这些代码，我发现很难相信是我写的。这些天，我做任何实际程序员都会做的事情，使用由NAG、numpy、matlab或其他受人尊敬的软件包(我信任NAG)实现的算法，也许还会做一些简单的统计分析来验证分布是否因为某种原因而是关键的。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|152953|不过，面试中最重要的是要诚实。如果你不知道，那就告诉他们你必须去查一查。如果你不知道，也没有兴趣去查，也可以告诉他们。做一项需要不断研究的具有挑战性的工作，必须是雇主通过提供良好的工作环境来满足的。挑战是好的，但对抗和竞争是适得其反的(太多的C)。|152954|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

This is a bit of a cruel question for an interview (unless this was a research position), but a fun one for a forum. 20 years ago after finishing my maths degree, I would have gaily presented a random generator written by myself with the mathematical proof that it was random. Looking at that code now, I find it hard to believe that I wrote it. These days, I do what any practical programmer would do, and use an algorithm implemented by NAG, numpy, matlab or some other well respected package (I trust NAG), and perhaps do some simple statistical analysis to verify, if the distribution were critical for some reason or another.

The important thing in an interview is to be honest though. If you don't know, then tell them you have to look it up. If you don't know and it doesn't interest you to look it up, it is okay to tell them that too. Doing a challenging job that requires constant research has to be something the employer caters for by providing a good working environment. Challenging is good, but confrontational and competitive is counter productive (too many 'C's).

blocks|key|2738179|text|由于这是一次面试，真正的问题不是证明均匀分布，真正的问题是被选中。我建议采用一种方法，让你快速判断面试官是在寻找关于高等数学的有趣讨论，还是在测试你的实际思维。我的猜测是，面试官很有可能会寻找后者。一个好的面试答案可能是这样的：“这完全取决于需要随机数生成器做什么。如果它在音乐播放器上起到了混洗功能，我会让它生成100个数字，检查平均值是否大致等于N/2，然后简单地看一下这些数字，然后就可以满意了。如果目的与加密有关，那就是另一回事了，我会开始研究，但最终可能不会自己证明，而是依靠现有的独立证据。”|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2738180|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

Since this is an interview, the real problem is not to prove uniform distribution, the real problem is to get selected for the job. I'd suggest an approach where you quickly decide whether the interviewer is looking for an interesting discussion on advanced mathematics or is testing for your practical thinking. My guess would be that there is a good chance that the interviewer would be looking for the latter. 
A good interview answer could be like this : "It all depends what the random number generator is needed for. If it serves a shuffle function on a music player, I would let it generate 100 numbers, check if the average roughly equals N/2, next have a brief look through the numbers and could be satisfied at that point. If the purpose would be related to encryption, it would be a different story, I would start doing research, but would probably end up not proving it myself but rely on existing, independent proof".

I was asked this question in an interview.

<blockquote>
 Given a random number generator to generate a number between [0,N), how
 to prove this number is uniform distributed.
</blockquote>

I am not sure how to approach this problem, any suggestion?

Prove a random generated number is uniform distributed

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋 

腾讯云代码助手

CODING DevOps

Cloud Studio

SDK中心

API中心

命令行工具

我在一次面试中被问到了这个问题。给定一个随机数生成器生成一个介于[0，N)之间的数，如何证明这个数是均匀分布的。我不知道如何处理这个问题，有什么建议吗？

问证明随机生成的数是均匀分布的
EN

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问证明随机生成的数是均匀分布的EN

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问证明随机生成的数是均匀分布的
EN