b. Remove any number that does not have the highest score from the game.
XHTML:These are some of the tags you can use:a href= b blockquote code em i strike strong
k1 = 0,1,2,3,4 each with equal probability.
Here is my result after running thousands, millions
The algorithm I posted that uses the random numbers from 1-5 to determine the winner of a game between the numbers from 1-7 has an interesting property: Suppose you find that the randoms from 1-5 that your are getting are not actually evenly distributed as long as they are independent and identically distributed, the game algorithm gives evenly distributed answers. Suppose your purchasing team finds another cheaper source of random numbers, but it does not give randoms from 1-5, it gives hex digits or hypergeometric or binomials or log normals or whatever, you can plug it into the game algorithm and you will still get uniformly distributed answers from 1-7 out, no change in the client algorithm.
Write a method to generate a random number between 1 and 7, given a method that generates a random number between 1 and 5. The distribution between each of the numbers must be uniform.
You are right. I missed a -1 in the code. Updated now
6124993,6124855,6118048,6103199,6110062,6118427,6123416
System.out.print(count[j] + ,);
That was fun, right? Anyone up for another challenge? Watch out for it next tuesday (March 1st).
var second = (assemb assemb % 10) / 10;
int rand_any_number_using_rand5(int new_base)
(rand5()+rand5()+rand5()+rand5()+rand5()+rand5()+rand5()-7)%7
* (num 22) gives the range 6..21 . This is a range of 16 values. How is the modulo 7 of this be an even distribution?
That will give you a random number from 0 to 34 with an equal probability that it is any one of those numbers and then modulo 7 an equal probability that it is a number from 0 to 6
Lets think of this like a decision tree. Each rand5() will be a decision. After 2 tries, we have 25 possible solutions. We try to get maximum bunches of 7 as we can (1 21, 3 sets of 7). If we get any of the other values, we just try again. Since the probability of getting each of 21 values are the same every time, trying again wont affect their probabilities.
k2 = 0,0,0,0,0, 0,1,2,3,4, 0,2,4,6,8, 0,3,6,9,12, 0,4,8,12,16 each with equal probability.
How about (rand5() + (rand5() %4) -1)
var assemb = 10 * (rand5()-1) + (rand5()-1)
Reading your explanation, you mentioned replacing every 6th number repeated with a 5. How times do you have run this? If you have to run it until a number appears the 6th time, that would be too many tries. Under what situation will you return one of the other numbers?
if ( testIt 22 ) return ( testIt % 7 + 1 )
I am not sure how k2 &(k2-1) == k2 is checking for perfect square. 9 is a perfect square. ( 9 & 8 ) != 9.
After getting one random value (x) between 1 to 5, we need a random value between 0 to 2 with equal probability. So we get modulus by 3. But since between 1 and 5 probability of getting 1 and 2 is 2/5 each and getting 0 is 1/5 so we fetch random number (y1,y2,y3) 3 times and add them and finally mod by 3 so we get 0,1,2 with equal probability. We add these random value between 0 to 2 with another random number (x) between 1 to 5 which we found separately.
UsingGravatarsin the comments – get your own and be recognized!
var first = assemb (second * 10);
Challenge:Do you know the answer to this question? Post in the comments. Lets see who isup for the challenge. Answers will be postedFebruary 26th.
If trying again is an option, then why not just tries twice rand5() as below
Calculate the chance of each of the values happening and see.
(rand5()+rand5()+rand5()+rand5()+rand5() 5)%7 ??
How about two tries of rand5() into a base-5 number, which will return 1 25 evenly distributed.
First I would implement rand6 and then rand7
but if you want to extend it for any number :
Adding up 7 of the 1..5 variables makes the distribution of the distribution of the total mod 7 flat to about 3 decimal places, adding up 11 gives 4 places, and so on, up to about 50, which gives around 21 decimal place equality.
var rand25 = 5 * second + first + 1;
Even if we replace that with a proper check for perfect square, I dont think your function provides proper rand6().
for (int j = 0; j count.length; j++)
In your case, if we divide by 2, we wont have an int always and that throws things off.
If youre looking for some serious preparation for your interviews, Id recommendthis book written by a lead Google interviewer. It has 189 programming questions and solutions:
You are right it generating all the numbers but there are NOT the same probability of occurring
The short answer is, if you want a program that is guaranteed to halt, it is not possible. You can only get sample spaces with 5^n outcomes, which is never divisible by 7 exactly (prime factorization), so the best you can do is an approximation.
Thus for every 6th repetition of a number by rand5() I force the function to return 5.
Then multiply this float number by 7 which makes it between 1 and 7.
so every 6th time a number, say 4, is repeated i replace it with 5.
use the same logic and implement rand7 using ran6.
k = rand5() + rand5() + rand5() + rand5() + rand5() + rand5() + rand5();
This make it a random float between 1/5 to 1.
c. If there is only one number with the highest score, that is your random number.
Posted solution is equivalent to mine and the other that I have identified as correct.
I dont see how the posted solution is correct.
572537,571818,571256,570103,569654,571263,571369,
The problem with some of the solutions is I dont think there is an equal probability the number will be 0 to 6
We have R5() method which returns randomly between 1 to 5 so we can make use of it such that the probability remains equal for all 1 to 7.
public static void main(String[] args)
The question of how many randoms from 1..7 one must add up before mod(total, 7) is close enough to uniformly distributed to work is one that I would like to figure out. I wonder if using 10 or 20 or so would get the probabilities essentially equal as close as we could tell from a few billion tests. Anyone know? I may try to work that out.
Oops, meant 7 is a prime number and 35 is a multiple of 7, not 35 is prime.
shouldve used the word integer in the question somewhere.
Am I missing something? Why cant you just multiply rand5() * 7/5? I just Monte Carloed this and each value [1,7] was 20000+/- 300
Simply divide the random number between 1 to 5, by 5.
Heres another approach that is also unbiased:
proof: use probability and you will find probability of 5 is same as probability of either of 0 1 2 3 4.
This answer here is wrong. when you perform a non random operation on any random generator, it will not remain random. Some of the comment answer are more correct than the one provided. In the provided example you will never receive a 1. Though I am just using my slow brain calculation. basically you can use the random function any number of times but you cant use arithmetic.Now try to answer it correctly
k2 is a perfect square 15 out of 25 times (0,1,4,9,16). Your function will return 5, 60% of the time.
rand5() * 7 generates random number between 0 and 35 with equal probability (assuming infinite precision). Since there is equal probability of any number between 0 and 35, and because 35 is both a prime number and a multiple of 7, taking the modulo with the prime number (7) generates a random number between 0 and 7 with equal probability.
another approach could be to convert down your random 5 into random binary. 3 random binary and you can convert into a 0 to 7 value. then if you have zero re-run, otherwise return the 1 to 7 value.
This is my method written in Java. I assume 7 times of rand5() invoking will get a even distribution of 35. then mod 7.
rand5 generates 0 1 2 3 4 equally likely.
* num will always be in the range 6..30 .
Anyone else with proof, empirical or otherwise, for their algorithms?
The algorithm by Chris Lomont and the one by me obviously give equal probability to each of the seven results when they return, and repeat the same process until they do return, so it is pretty hard to see how they could not be fair. The more interesting question is whether or not my recursive function guarantees that it will return before time runs out or the stack overflows, or whatever. There is some small probability of that, with a recursion happening about once in each 6 calls. Even python, which I wrote mine in (v 2.6), and which does not do tail call optimization, will let one recurse a little function like that for hundreds of levels on typical computers. That puts the probability of the stack crashing down around the probability of not finishing the computation because a meteorite hits your computer, which I suppose any algorithm must bear as an acceptable risk.
a. Add a random base 5 digit to each numbers score.
77858,77310,77523,76907,76496,76458,76448,
Whats the point? If you really want the result to be truly random between 1 and 7, why not just use rand7. Rand5 is really irrelevant.
Zhiming, we are not talking about rand in terms for float here. We are only looking at integers. Maybe the question is a little unclear about that.
this is when you want to make random between 1 7 :
for(int i = 1; i new_base; i++)
Start a game between the seven numbers and start each number with a score of zero.
This takes at least seven calls to rand 1..5 to finish, so it is not so efficient, but it has a great
d. If more than one number is still in the game,