Hash Tables + probability question

[FlashStorm]

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 because 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,
Aviv

 

[EnumaElish]

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).

 

[FlashStorm]

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

 

[EnumaElish]

If t \approx 1, then log t \approx t - 1.

 

[FlashStorm]

I don't think t has any estimations, why would t\approx1 . t is the number of probes
but even if it had anything like it i would get that E(X)=\Omega(n), which is the complete contrary.

 

[EnumaElish]

Are you saying that what you have does not work for t = 1?

 

[FlashStorm]

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.