You are given a minimum heap, with probability going to left is 50% and going to right is 50%. What is the probability that You will land up on a maximum element in the heap? For this scenario since going to right and left have equal probabilities we can state the answer to be $(1/2)^{O(\log n)}$ . As at each step we have two possible decisions and we can choose the correct path with a probability of 1/2. We have to make this decision $\log n$ number of times (height of the heap). It doesn't matter whether we take a left or a right from the present node as both are equally probable. But if the probabilities are not equal for left and right is this model still valid?

The Question

How can we model the above situation where the probability of going to right is $x$ and to the left is $1-x$, where $0<x<1 $

Is the concept of random walks on graphs involved?

Assumptions : There exists a unique maximum element which by the definition of heaps exists at some leaf node.

  • $\begingroup$ 3. What exactly is your question? You say "How can we model..." but it seems like you have already described a model, so I'm not sure what you are looking for. What is the purpose of such a model? How do you want to use it? Can you edit to clarify what kind of answer you are seeking, why you aren't satisfied with what you already have, and how you plan to evaluate candidate answers (e.g., what criteria/requirements they must satisfy)? There might be multiple reasonable models. $\endgroup$ – D.W. May 17 '17 at 16:50
  • $\begingroup$ I am not sure my current model is accurate to describe the situation that is why i am not satisfies with it. I am saying it can have flaws i will be more than happy if someone points them out. @D.W. $\endgroup$ – Shubham Singh rawat May 17 '17 at 17:15
  • $\begingroup$ I guess I don't understand what you are looking for. What would count as a "model"? It sounds like your question already describes a model. What specifically are you unsure about? What aspect of the situation do you think might not be covered? Why have you rejected your existing answer? Have you tried working through some examples to see if your approach gives the right answer? Have you tried proving it correct? $\endgroup$ – D.W. May 17 '17 at 18:31
  • $\begingroup$ Is this a binary heap? Is it complete or full? If it is a binary & full heap, then a random walk from the root would yield $\frac{1}{(n + 1)/2}$ because there would be $(n+1)/2$ leaf nodes and equal probability of hitting any one of them. To get $x$ probability of hitting the max on a traversal of the tree, it seems like you either need to contrive the walk (by giving certain probabilities to certain paths) or contrive the heap (by inserting into the heap in a particular way that yields this new probability or maybe even exploring different types of heaps). $\endgroup$ – ryan May 17 '17 at 18:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.