Problem:
We have a random generator generating uniformly distributed numbers in the range 1..10 . How many times in average one can apply the random generator to get a sequence of three mutually different numbers?
Solution [The problem is similar to the well-known Collecting Coupons Problem]
Let’s suppose that the random generator is a sampling with replacement, i.e. if a number X is taken in k-th trial then this number can appear in (k+1)-th trial and in further trials.
The first number is obtained by a single call of the random generator. However, the second call can supply the same number. The probability to obtain the second number different from the first one is p1 = 9/10. The average amount of attempts M1 until the second number gets different from the first one is equal to the mean of the geometric distribution with the success probability 9/10, i.e. M1 = 1/p = 10/9. The probability of getting the third number which is different from the preceding two figures is p2 = 8/10. The average amount of attempts M2 until the third number is obtained is 10/8.
So, the expected number of calls the random generators: 1 + M1 + M2 = 1 + 10/9 + 10/8 = 3.361
How many times in average one can apply the random generator producing numbers in the range 1..10 to get a sequence of five mutually different numbers?
1 + 10/9 + 10/8 + 10/7 + 10/6 = 6.45
Alternative solution based on the birthday problem:
You take ‘r’ random numbers from 1..N (r << N), the probability of no-duplicates in a random sample of the size ‘r’:
P(no-duplicates) = N(N-1)..(N-r+1)/Nr since r<<N we have 1 – 1/N ≈ e-1 , 1 – 2/N ≈ e-2 , … .
Thus, the expression N(N-1)..(N-r+1)/Nr equals approximately to e -r(r-1)/2N .
Problem: for what value of ‘r’ the probability of non-duplicates = 0.5?
r(r-1) ≈ 0.693*2*N or r = (1 + sqrt(1 + 8*0.693*N))/2
For N=100 the sample size with the probability of no-duplicates equal to 0.5 is 13!!!
23+ years’ programming and theoretical experience in the computer science fields such as video compression, media streaming and artificial intelligence (co-author of several papers and patents).
the author is looking for new job, my resume
Related posts:
Probability Theory and SW Verification
SW Testing and Population Statistics
Use Case from Video Compression: Significance Testing of Pearson Correlation Coefficient
Detection Anomalies (Outliers) in Data
Exercise in Combinatorics for Team Leader
What’s the probability for two randomly selected integers to be relatively prime?
Awsome website! I am loving it!! Will be back later to read some more. I am taking your feeds also.
Hiya, I’m really glad I have found this info. Nowadays bloggers publish only about gossips and internet and this is actually irritating. A good website with exciting content, that’s what I need. Thanks for keeping this web site, I will be visiting it. Do you do newsletters? Can’t find it.
Magnificent beat ! I wish to apprentice at the same time as you amend your web site, how can i subscribe for a blog site? The account aided me a acceptable deal. I were tiny bit acquainted of this your broadcast offered bright transparent concept
pls. look for the word Newsletter in the main page
Very good website you have here but I was curious if you knew of any forums that cover the same topics talked about in this article? I’d really like to be a part of community where I can get feedback from other knowledgeable people that share the same interest. If you have any recommendations, please let me know. Kudos!
Greetings! This is my 1st comment here so I just wanted to give a quick shout out and tell you I genuinely enjoy reading your articles. Can you suggest any other blogs/websites/forums that deal with the same topics? Thanks for your time!
search combinatorics problem in https://www.quora.com/
Would you be excited by exchanging hyperlinks?
i prefer to exchange money
Do you have a spam issue on this blog; I also am a blogger, and I was curious about your situation; we have developed some nice methods and we are looking to exchange methods with others, please shoot me an e-mail if interested.
yes, i have spam comments, but not so much to annoy. The blog is technically narrow and number of visitors is limited.
I do consider all of the ideas you have offered in your post. They are really convincing and will definitely work. Still, the posts are very brief for newbies. Could you please lengthen them a little from subsequent time? Thank you for the post.
i have been constantly updating all topics in the site
I’m extremely impressed with your writing skills as well as with the layout on your blog. Is this a paid theme or did you customize it yourself? Anyway keep up the excellent quality writing, it is rare to see a nice blog like this one these days..
You can definitely see your skills in the paintings you write. The sector hopes for even more passionate writers such as you who are not afraid to mention how they believe. All the time follow your heart.
Very interesting points you have noted, appreciate it for posting.
After study a few of the blog posts on your website now, and I truly like your way of blogging. I bookmarked it to my bookmark website list and will be checking back soon. Pls check out my web site as well and let me know what you think.
Glad to be one of many visitants on this awe inspiring web site : D.
Hello my friend! I want to say that this article is amazing, nice written and include approximately all significant infos. I’d like to see more posts like this.