for someone who wants complication :-P
let
P(M,N) = among M numbers, N numbers are sorted in one hits. that
probability. so, for example,
P(3,3)=1/3!
P(3,0)=1 - P(3,1) - P(3,2) - P(3,3) = 1 - sigma(k:1~M){P(M,k)}
and
P(3,2)=0. you know. it's impossible. for every n, P(n,n-1)=0.
and
P(m,n) = ( mCn / m! ) * ( P(m-n, 0) * (m-n)! )
(among m, only n is right. so at first, you choose n elements(=mCn). and
divide this by m! (it became probability. not 'number of cases'), and the
rest(=m-n) must be in incorrect position(=P(m-n, 0)), and multiply factorial
of m-n, because P(m-n,0) is a probability, so by multiplying this, we get
'number of cases'. finally we get P(m,n))
and let
F(M,N) = among M numbers, we can get a sorted list in N hits. that
probability.
for example,
F(3,1) = 1/3! (for any number A, F(A,1) = 1/A! = P(A,A) )
and,
F(5,2) = P(5,0)F(4,1) + P(5,1)F(4,1) + P(5,2)F(3,1) + P(5,3)F(2,1)
and so on.
so expected value E (for N elements)
= sigma(k: 1~inf.){ k * F(N, k) }
as you all know.
E(n) = n
2011/5/8 Alfonso J. Ramos <[email protected]>
> ...
>
> If you have 2 elements, then there is 1/2 chance of getting them right
> [in one hit], and 1/2 of not. Of those last 1/2 you have 1/2 (that is
> a 1/4 of the whole) to get it right [in two hits] and 1/2 (that's the
> other 1/4 of the whole) not. Of that 1/4 you have 1/2 (that is a 1/8
> of the whole) to get it right [in three hits] and the other 1/2 (that
> is 1/8 of the whole) not.
>
> So, you do the pondered sum of the N first iterations and you will see
> that it converges to 2 (that's the average number of hits).
> See:
> first iteration = 1/2 * 1 hit = 1/2 hits
> second iteration = 1/2 * 1 hit + 1/4 * 2 hits = 1 hit
> third iteration = 1/2 * 1 hit + 1/4 * 2 hits + 1/8 * 3 hits = 1 hit + 3/8
> hits
> fourth iteration = 1/2 * 1 hit + 1/4 * 2 hits + 1/8 * 3 hits + 1/16 *
> 4 hits = 1 hit + 5/8 hits
>
> No finite number of iterations is right because they only get as close
> to cover all the posibilities, but you see the form: sum (i/2^i), you
> may find that it converges to 2. I did ask wolfram alpha.
>
> Now...
>
> if you have 3 elements, then there is a 1/6 chance of getting them
> right [in one hit], 3/6 of getting one element right, since Goro holds
> those that are right, you can take this as a two element escenario so
> it becomes a 3/6 chance of getting it right in three hits (the one he
> did to the three elements plus the two average for the two element
> case). And lastly the other 2/6 you get nothing right. Of those 2/6...
> well you get the idea, when you do the pondered sum of the N first
> iterations and you will see that it converges to 3 (that's the average
> number of hits). I had to use excel for that.
>
> I did trust that that would work for the rest of cases, it took me a
> long time... bad for me.
>
> You may be wondering, how comes the pondered sum is the average? well,
> the classic average is the sum of the values over the total: [(A + B +
> C) / Total], you can also express it like this: [(A / Total) + (B /
> Total) + (C / Total)]. In a grouped average you multiply the values by
> the number of times they appear [(A * timesA / Total) + (B * timesB /
> Total) + (C * timesC / Total)].
>
> In our case the total is 1 (that is the 100% of cases) the number of
> times it appears is the probability and the value is the number of
> cases. So you see that I don't need to divide by 1 as it gives me the
> same value... so as it turns out the pondered sum of the number of
> hits by it's probability is the group average of the number of hits.
>
> 2011/5/8 Lei Huang <[email protected]>:
> > Including the 2-elements array.
> > There is 50% possibility that no elements will land in its position,
> > and 50% possibility both of the elements are in the right position.
> > So the expected is 50% * 2 + 50% * 0 = 1
> >
> > 2011/5/8 Jin Mingjian <[email protected]>:
> >> "So we can expect that in any random permutation, one element will land
> in
> >> its correct sorted pos." except for the 2-elements array?
> >>
> >>
> >> On Sun, May 8, 2011 at 3:20 PM, rajatag12 <[email protected]> wrote:
> >>>
> >>> Yes. First thing to see is that Goro would never hit the table with
> open
> >>> elements that *could not* land in their correct position for any
> >>> permutation. Once it is understood, it will be easy to see that solving
> the
> >>> prob for each permutation cycle is an independent one. Answering the
> main
> >>> question, observe that each element in a sequence of N elements appears
> in
> >>> its correct place (N-1)! times out of the N! permutations. So we can
> expect
> >>> that in any random permutation, one element will land in its correct
> sorted
> >>> pos. So after each hit, Goro should include the last element placed
> >>> correctly in his set of elements to hold before he hits. Hence,
> expected
> >>> number of hits = n.
> >>> Formal proof has already been provided above.
> >>>
> >>> On Sunday, May 8, 2011 7:22:39 AM UTC+5:30, Balajiganapathi wrote:
> >>>>
> >>>> I meant: Is n the expected number of hits to sort a n-element *cycle*.
> >>>
> >>> --
> >>> 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.
> >>
> >
> > --
> > 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.
>
>
--
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.
