1
$\begingroup$

I'm a noob in randomized algorithm and ran into a problem(definitely not home work. I'm doing a self study out of my interest with help of my friends. I'm pursuing research career in a machine learning and large scale optimization and found randomized algorithm is being used heavily in this field. In fact in my course of study I encountered a problem, a part of which can be boiled down to this problem) stated below. I tried to form a Markov chain/random walk like formulations but failed.

A master and his student is playing a game as follows: Suppose there is a machine generating random number , which outputs a number $x \in [0,1]$ from some fixed distribution $f(x)$ if the button is pressed. Also the machine can be set with a parameter $\rho$ such that it will give a beep sound if the appeared number is greater than or equal to the $(1-\rho)^{th}$-quantile of $f(x)$

At first the master press the button and gets a number . Next student keeps on pressing until he gets a number which is bigger than the master's number. Then the master keeps on pressing until his number is bigger than the student's number. The game goes on like this until the machine gives a beep sound.

What is the expected number of switch over between the student and the master ?

Improve this question
$\endgroup$
9
  • $\begingroup$ Whether this was assigned to you or not doesn't matter. $\endgroup$
    – Douglas Zare
    Commented Feb 27, 2016 at 14:43
  • $\begingroup$ (1) The distribution might as well be Unif[0,1] since you only care about quantiles. (2) Each time we switch, the new "current max" is distributed independently conditioned on exceeding the old current max. (3) In expectation, each switch cuts the interval in half (first number averages $0.5$, etc), so $\log_2(1/\rho)$ should be the right ballpark. $\endgroup$
    – usul
    Commented Feb 27, 2016 at 14:50
  • $\begingroup$ @usul: You are assuming that the distribution is continuous. If so, this problem is an easy exercise if you add up the probabilities of changes on each step. $\endgroup$
    – Douglas Zare
    Commented Feb 27, 2016 at 14:59
  • $\begingroup$ @DouglasZare, good point about the assumption! But I don't understand your hint. $\endgroup$
    – usul
    Commented Feb 27, 2016 at 22:08
  • $\begingroup$ The expected number is a sum of probabilities, each of which is easy to compute if the distribution is continuous. $\endgroup$
    – Douglas Zare
    Commented Feb 28, 2016 at 3:34

0

Reset to default

Browse other questions tagged .