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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook