I simplified the expression but didn't change the comment. It should include
...i/k is 1 for only i=k. On May 23, 2013, at 4:31 PM, Dar Scott wrote: > I did a math. > > The probability of the first element not moving for a k item list named > myList that is sorted by > > sort items of myList by random( the number of items of myList ) > > is p(k) where > > p(k) = sum with i from 1 to k of 1/k * ( i/k ) ^ (k-1) > > That power increasing with k tends to make numbers less than one smaller, but > 1 stays the same, so p(k) approaches 1/k as k goes up since (k+1-i)/k is 1 > for only i=1. > > This essentially looks at the probability of the first element not moving for > each case of its assignment by random (the sum) and each of those depends on > the rest of the assignments being the same or higher. > > That seems to work for 1, 2 and 3. > > (This hasn't been blessed by Geoff yet, so don't file this as True, yet.) > > Dar > > > > > On May 23, 2013, at 2:43 PM, Alex Tweedly wrote: > >> Indeed you are correct. The maths is simple (even if not very obvious or >> intuitive). >> >> Sorting N lines by random(K) >> >> The likelihood of swapping any two lines *should* be 1/2, but (because the >> sort is stable, and because they are random *integers*), there is a 1/K >> chance of the two random values rounding to the same integer, and hence the >> actual probability is (1-1/K)/2 and the probability of not swapping is >> (1+1/K)/2 >> >> So in Geoff's example (N=2, K=2) gives probabilities of (1-0.5)/2 i.e. 1/4 >> and 3/4 >> >> Changing K to 3 would make a slight improvement - 1/3 and 2/3 >> at K=4 we get 3/8 and 5/8, etc. >> so by the time K=1000 >> >> Interestingly, the poor performance for low values of K is completely >> independent of N - it's just easier to see it for very small values of N. >> >> If you set N to 5, you want to get an even spread of results, each with a >> probability of 8.333/1000 >> In fact with K=2 you get a range from 0 to 180/1000 >> >> So - random() works just fine - but using it correctly is harder than you >> might expect. I think it would be worth a feature request to make it much >> less likely that the innocent will fall into the many pitfalls. >> >> -- Alex. >> >> On 23/05/2013 20:30, Geoff Canyon wrote: >>> There is, indeed much confusion here. I, of course, am correct ;-) >>> >>> I simplified the problem to a list of two items: >>> >>> 1,2 >>> >>> That way the sort command has exactly two outcomes. It either reverses the >>> list, or it doesn't. The two outcomes should happen roughly 50% of the >>> time. This script demonstrates that sorting by a large random number works, >>> and sorting by a random number up to the number of items (2) does not. >>> >>> on mouseUp >>> put "1,2" into originalList >>> repeat 10000 >>> put originalList into newList >>> sort items of newList by random(2) >>> if newList is originalList then add 1 to sameCount1 >>> end repeat >>> repeat 10000 >>> put originalList into newList >>> sort items of newList by random(999999999) >>> if newList is originalList then add 1 to sameCount2 >>> end repeat >>> put "Sorting by random(2) kept the same order" && sameCount1 && "out of >>> 10000 times." & cr & \ >>> "Sorting by random(999999999) kept the same order" && sameCount2 >>> && "out of 10000 times." >>> end mouseUp >>> >>> For anyone interested in the math, as you would expect, the random numbers >>> for the sort come out 2,1 roughly 1/4 of the time, so the result is that >>> the list is in the same order roughly 75% of the time when using random(2). >>> Here's one result I got: >>> >>> Sorting by random(2) kept the same order 7514 out of 10000 times. >>> Sorting by random(999999999) kept the same order 5014 out of 10000 times. >>> >>> If anyone disagrees, come at me, bro. ;-) >>> _______________________________________________ >>> use-livecode mailing list >>> use-livecode@lists.runrev.com >>> Please visit this url to subscribe, unsubscribe and manage your >>> subscription preferences: >>> http://lists.runrev.com/mailman/listinfo/use-livecode >> >> >> _______________________________________________ >> use-livecode mailing list >> use-livecode@lists.runrev.com >> Please visit this url to subscribe, unsubscribe and manage your subscription >> preferences: >> http://lists.runrev.com/mailman/listinfo/use-livecode > > > _______________________________________________ > use-livecode mailing list > use-livecode@lists.runrev.com > Please visit this url to subscribe, unsubscribe and manage your subscription > preferences: > http://lists.runrev.com/mailman/listinfo/use-livecode _______________________________________________ use-livecode mailing list use-livecode@lists.runrev.com Please visit this url to subscribe, unsubscribe and manage your subscription preferences: http://lists.runrev.com/mailman/listinfo/use-livecode
