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.
