Afişează mesaje

Pagini: 1 2 [3] 4 5 ... 57

56

Comunitate  feedback, proiecte si distractie / Blog / Răspuns: Probability shortlist

: Iunie 20, 2014, 22:47:34

Good question. Probability is pretty tricky to get right. The algorithm you mention doesn't work. Try running it 1000 times and see how frequent are the 7 results. I've implemented the algorithm you mention and the algorithm described in the previous comments in python. Here's how they compare: import random
def rand5(): return random.randint(1, 5)
def badfunction(): f = [0] * 8 for i in xrange(0, 1000): f[rand5() + rand5() % 3] += 1 print 'badfunction' print f
def rand0_24(): return (rand5()  1) * 5 + rand5()  1
def rand7(): r = rand0_24() while r >= 21: r = rand0_24() return r % 7 + 1
def goodfunction(): f = [0] * 8 for i in xrange(0, 1000): f[rand7()] += 1 print 'goodfunction' print f
badfunction() goodfunction()
the results are badfunction [0, 46, 108, 199, 195, 206, 165, 81] goodfunction [0, 144, 162, 142, 140, 131, 149, 132] So you can see the function you mentioned returns 1 much less frequently than it returns 3. Having a good random generator is important. Here's an example where not caring about the random function went wrong http://www.cigital.com/papers/download/developer_gambling.php



58

Comunitate  feedback, proiecte si distractie / Blog / Răspuns: Probability shortlist

: Iunie 20, 2014, 20:54:51

@Darius 4) Good job. This is called the "Reservoir Sampling" algorithm.
There's a interesting weighted version of the problem where the algorithm gets more complex.
5) I think this is ok, but the Knuth shuffle algorithm mentioned above is O(n).
To shuffle an array a of n elements (indices 0..n1): for i from n − 1 downto 1 do j ← random integer with 0 ≤ j ≤ i exchange a[j] and a[ i]



62

Comunitate  feedback, proiecte si distractie / Blog / Răspuns: Probability shortlist

: Iunie 18, 2014, 20:32:31

Cool, plenty of comments. I'll go through them one by one.
@ DanAlexandru 2. 5^6 % 7 = 1 so one of the 7 results is sightly more frequent than the others.
3. using this method a point has 1/2 probability of being in the 1/2 r radius circle. this circle has 1/4th of the area of the entire circle. so the points are not evenly distributed.
4. this works! one caveat is that as n grows you start needing big number operations and the algorithm starts being somewhat slow.
@ vali_MIT 7. good job. this works.
@ DanAlexandru 1. you don't know p.
5. yes
6. average time
7. formula. you can see vali's solution.
@ Aurelian 6. Yes. This works.
I would do it slightly different: the probability of seeing a new after already having i toys is (n  i) / n. The expected number of steps for an event that happens with probability p to happen is 1/p. So the expected number of steps for seeing a new toy after already seeing i toys is n/(ni). Thus the total number of steps is n / n + n / (n  1) + ... + n/(ni) + ... + n / 1 = n Hn
8. This works as well. How I would solve it: the probability of line 4 being executed at step i is 1/i (the probability of the maximum number in a sequence of i numbers being in the last position of the sequence is 1/i). so the expected number of times step 4 is executed is 1/1 + 1/2 + ... + 1/n = Hn.
@ Mihai Ciucu 2. good job. the key insight is that you have to ignore a few numbers to get uniform results. (now the algorithm is non deterministic but has a short expected execution time)
3. yup. using a random number between 0 and r*r then doing sqrt gives us a good distribution.
To sum up we don't have a good solution for 1. We don't have an efficient solution for 4. We don't have any solution for 5.



