@Bharath > Another way to look at this is, if you are uncomfortable multiplying > with a 0, No, I am not uncomfortable about about mathematical process of multiplying by zero; I am uncomfortable with loosing the significance of effect of some cases. If somebody asks me, how many hits are required to bring one element/ number in its correct position for N=3, sample space being 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 I would like to answer that on an average 2 hits are required (3 out of 6 cases/events have one number at its correct position; probability 1/2). This is where I become uncomfortable.
Eagle On May 16, 1:19 am, 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 > > athttp://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.
