Skip to main content
MathOverflow

Return to Question

explanation added to make clear it's connection with my research
Source Link
aroyc
aroyc
  • 221
  • 1
  • 4

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 ?

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

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 ?

Post Closed as "Not suitable for this site" by Douglas Zare, Wolfgang, Stefan Kohl♦, Ryan Budney, Myshkin
Source Link
aroyc
aroyc
  • 221
  • 1
  • 4

Expected number of forward jumps to reach a given quantile of a rv

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