Results 1 to 2 of 2

Math Help - One More (sry forgot i also skipped this one to hard for me :P)

  1. #1
    Newbie
    Joined
    Apr 2014
    From
    Canada
    Posts
    3

    Angry One More (sry forgot i also skipped this one to hard for me :P)

    You are given an array A[0....n-1] of n numbers. Let d be the number ofdistinct numbers that occur in this array. For each i with 0 <=i <=n-1 let Ni be thenumber of elements in the array that are equal to A[i].  Show that d= summation i=0 n-1 1/NiConsider the following algorithm:Step 1: Choose an integer k in{0,1,2,......n-1} uniformly at random, and let a = A[k].Step 2: Traverse the array and compute the number Nk of times that a occurs.Step 3: Return the value X = n/Nk.Determine the expected value E(X) of the random variable X.

    I'm pretty sure that you are suppose to use the definition of expected value. But not 100% sure :S
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    2,789
    Thanks
    1149

    Re: One More (sry forgot i also skipped this one to hard for me :P)

    for each unique element in the alphabet $\dfrac{1}{N_i}$ appears in the sum $N_i$ times. Thus the sum is equal to the size of the alphabet, i.e. d.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: March 10th 2010, 07:24 AM
  2. I forgot how to do this...help.
    Posted in the Calculus Forum
    Replies: 2
    Last Post: December 16th 2009, 12:29 PM
  3. some how forgot
    Posted in the Calculus Forum
    Replies: 2
    Last Post: February 27th 2009, 04:37 AM
  4. Need help! Forgot how to do this..
    Posted in the Calculus Forum
    Replies: 1
    Last Post: January 1st 2009, 02:18 PM
  5. uhh i forgot how to do this =/..
    Posted in the Algebra Forum
    Replies: 3
    Last Post: March 18th 2008, 03:58 PM

Search Tags


/mathhelpforum @mathhelpforum