1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Hash Tables + probability question

  1. Nov 16, 2007 #1
    Now before I'll post the question , I want to be clear. Technically , this WAS a homework question. BUT since I don't have to submit it (because I finished with the homework submitting process , and now studying for the test), I think it is legitimate to post here the homework file + I am doing it because I couldn't really solve it. (and there is no official solutions cuz our lecturers and his assistance are pretty god damn lazy:( )

    now this is question 6 (with the hash table of size 2n to store n elements).
    I've solved the first three sub-questions:

    the first one is upper bounded by p=1/2 and it distributes as geometric random variable.
    the second one is just substituting in the first sub question.
    the third one is basically the sum of all n Xi insertions with the answer of sub question b.

    Now, the forth questions deals somehow with Markov's inequality and about to prove that the expected length of probes is O(logn).

    So I know that Markov's inequality means :
    P(x>=t)<= E(X)/t

    and although i tried to used this fact to get an upper bound , I couldn't find any solution or a lead.

    Note: This is a new question which didn't appear on previous years assignments. If you have a reason to believe this question was made inappropriately or maybe even some mistakes.

    Looking forward for your help
    and thank you,

    Attached Files:

    • ex8.pdf
      File size:
      45.8 KB
  2. jcsd
  3. Nov 16, 2007 #2


    User Avatar
    Science Advisor
    Homework Helper

    Rewrite P(x>t) < E(X)/t as t*P(x>t) < E(X), or E(X) = t*P(x>t) + v for some v > 0. Show that t*P(x>=t) + v is O(Log n).
  4. Nov 16, 2007 #3
    It was the first thing i have done, obviously. yet couldn't get any results.

    according to the questions P(X>=t)<= n/2^t (according to question 6.1 the probability to probe more then k times is 2^-k , sum it n times and you will get n/2^t).

    So that leads us to nt/2^t<=E(X).

    after doing log on both sides (log2) i get logn+logt-t<=log (E(X)). since t can be any number, I can't block it or take it out. I lack insights about that situation. But even if I do manage to get E(X)>={log expression}. All I get is a lower bound. then I will have to show an upper bound.

    Thanks in advance
    Last edited: Nov 17, 2007
  5. Nov 17, 2007 #4


    User Avatar
    Science Advisor
    Homework Helper

    If t [itex]\approx[/itex] 1, then log t [itex]\approx[/itex] t - 1.
  6. Nov 17, 2007 #5
    I don't think t has any estimations, why would t[tex]\approx[/tex]1 . t is the number of probes
    but even if it had anything like it i would get that E(X)=[tex]\Omega[/tex](n), which is the complete contrary.
  7. Nov 18, 2007 #6


    User Avatar
    Science Advisor
    Homework Helper

    Are you saying that what you have does not work for t = 1?
  8. Nov 19, 2007 #7
    Yes, I think at least. t is the number of probes on the array. and the question says "use markov's inequality to prove that the longest probe sequence is E(X)=O(logn)".

    there is no reason to believe that t = 1 (it should even be much bigger to my opinion), and even if it were true, i would still get the wrong answer.
    Last edited: Nov 19, 2007
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Hash Tables + probability question
  1. Probability question (Replies: 4)

  2. Probability Question (Replies: 21)

  3. Probability Question (Replies: 3)

  4. Probability questions (Replies: 1)