Also E(X) = 1, Hence, E(n=a+1) = 1 + E(n=a) ^^ This statement is wrong. It just turns out to be coincidence for this problem.
E(X) = 1 <some complex mathematics here for n>= 2 .. see contest analysis> Hence, E(n=a) = a for a>= 2 ^^ This is the correct way. Pedro, correct me if I am wrong. Thought I would point this out as I feel you are thinking that the calculation is being done the incorrect way. For example, take a problem where goro need not sort the numbers but can stop when there are atmost 2 elements out of place. In this case, E(n=2) = 0 E(X) is still 1. (expected number of elements to fall in place). So, saying that E(n=3) = 1 + 0 = 1 is incorrect. If you try to calculate, you will see that n=3 is a simple success-failure event with probability 2/3. Hence, E(n=3) = 1.5 and not 1. On 16 May 2011 10:49, Bharath Raghavendran <[email protected]> wrote: > 1. > You aren't omitting the case where none are sorted. Its just that when > none are sorted, the value of the random variable is 0. > > For example, if you are finding average of 0 and 10, you do (1/2)*0 + > (1/2)*10. Even though you are multiplying by 0, you arent omitting it, > and getting the right answer. > If probability for 0 is 3/4 and probability for 10 is 1/4, you find > the average (or expected value) as (3/4)*0 + (1/4)*10 = 2.5. See that > even though the value of random variable is 0, it affects the final > output for expected value. > If probability of 0 is ~1 and probability of 10 is ~0, you will have > expected value as 0. > > Another way to look at this is, if you are uncomfortable multiplying > with a 0, You can find E(1+X) instead of E(X) and then subtract 1. > For n=3, E(1+X) will be (1/6)*4 + (1/2)*2 + (1/3)*1 = 2. > So, E(X) = 2-1 = 1. > > 2. >> There, we did not say, that in one hit one number is expected to >> come at appropriate position, and because the remaining number does >> not require any hit (it gets automatically sorted) > > This statement is wrong. If we say 1 element has come in the > appropriate place, we mean that exactly 1 element has come in its > place and rest of the elements are not in the appropriate place. Note > that this outcome is not possible for n=2, because either 0 elements > can fall in place or 2 elements can fall in place. No other outcome is > possible. However, from calculations, you will see that the expected > value for number of elements to fall in place is still 1 (by > calculations). For n=2, you can calculate expected number of hits as > E(n=2) = (1/2)*(1 + expected number of hits when none of them fell in > place) + (1/2)*(1 + expected number of hits when both of them fell in > place) > = (1/2)*(1 + E(n=2)) + (1/2)*(1+0) > = 1/2 * E(n=2) + 1 > So, E(n=2) = 2. > > On 16 May 2011 10:24, Eagle <[email protected]> wrote: >> Thanks Pedro, Bharath, & others; finally I have fully >> understood how the calculation of expected number of numbers that land >> in the correct position after X hits, is done. Comments by John & Paul >> Smith also helped in filling the communication gaps, Thanks! I think, >> I have also understood the logic of your method. It goes something >> like this (correct me, if I am wrong)- >> The expected value of the numbers that fall in correct position after >> a hit is 1. If we have problem of sorting, say, 5 numbers, i.e., N=5, >> then after first hit, one of the five numbers gets sorted; Goro now >> puts a finger on it, and the problem is reduced to N=4. By similar >> process, in second hit we come to N=3, in third hit we come to N=2. >> For N=2, the solution is already given in the problem statement >> itself, and that is 2 hits. So, total 5 hits are required for sorting >> N=5 numbers. >> >> For the sake of science, please ponder over the following >> points- >> >> 1) Is 'expected value' which is average (albeit weighted) value, >> appropriate in the present problem? The way we are calculating this >> value, it so happens that the effect of cases where none of the >> numbers is sorted, becomes zero. >> For N=3, E(sorted numbers) = (1/6)*3 + (1/2)*1 + (1/3)*0 = 1 >> For N=4, E(sorted numbers) = (1/24)*4 + (1/4)*2 + (1/3)*1 + (9/24)*0 = >> 1 >> We are ignoring the significance of 2 out of 6 events of the sample >> space for N=3, and 9 out of 24 for N=4, because of the way we are >> doing calculation. I have not checked, but I think this ratio must be >> increasing for N=5, 6, etc. The omission of these cases makes me >> uncomfortable. Can we afford to take such a risk? >> >> 2) We have not omitted the significance of unsorted numbers case for >> N=2. There, we did not say, that in one hit one number is expected to >> come at appropriate position, and because the remaining number does >> not require any hit (it gets automatically sorted), the expected >> number of hits (for N=2) is one. We appropriately took the number of >> required hits for N=2 as two. >> >> Thanking you in advance for your learned and thoughtful >> comments, >> >> Eagle >> >> >> On May 14, 11:18 pm, Pedro Osório <[email protected]> wrote: >>> I am not offended at all. I'm however starting to get a bit annoyed that you >>> don't pay attention to what I write. >>> >>> I have explicitly defined X in that post as "elements that go into the right >>> position after one hit for the array [2 1]" (because that's what you were >>> asking about in your last question " the expected number of elements that >>> are put into position by the first hit is exactly 1") >>> >>> Meanwhile, whenever I wrote E[n=whatever], I was talking about the expected >>> number of hits required to sort an array that has "whatever" elements out of >>> position. >>> >>> E[n=2] - expected number of *hits* required to sort an array that has 2 >>> elements out of place >>> X - expected number of *elements* that go into the right position >>> after one hit for the array [2 1] >>> >>> As you can see, the random variables whose expected values we are computing, >>> don't even refer to the same kind of object. I don't see how you could >>> confuse them. Please pay more attention before complaining. >> >> -- >> You received this message because you are subscribed to the Google Groups >> "google-codejam" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> For more options, visit this group at >> http://groups.google.com/group/google-code?hl=en. >> >> > -- You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
