Epic Systems Interview Question
This is a Markov Chain problem.
Let j=#tails,
the the probability of j+1 tails at step t is P(N_t=j+1|N_(t-1)=j)=(n-j)/n;
and the probability of j-1 tails at step t is P(N_t=j-1|N_(t-1)=j)=j/(2n).
Hence the probability matrix P is as follows:
1. main diagonal is 0, 1/2n, 2/2n,..., n/2n;
2. upper diagonal is 1, (n-1)/n, ....,1/n;
3. lower diagonal is 1/(2n),2/(2n),...,n/(2n).
If x is the stationary ditribution, then x=x*P.
n+1 equations and n+1 variables, by the Perron–Frobenius theorem, there must be a solution.
So the answer is yes.
In fact we can explicitly solve the distribution.
It is the binomial distribution:
Let x=(x_0,...,x_n) be the stationary distribution, then by expanding the matrix multiplication,
x_0 = 1/(2n)x_1, so x_1 = 2nx_0 = 2(n choose 1)x_0;
x_1 = x_0 + 1/(2n)x_1 + 2/(2n)x_2, so x_2 = 4(n choose 2)x_0;
......
It can be proved by mathematical induction that
x_k = 2^k(n choose k)x_0,
since \sum x_i = 1, we have x_0 = 1/3^n, and x_k = 2^k/3^n(n choose k).
There is a theorem stating that
if a Markov chain is irreducible and aperiodic and a stationary distribution exists, then
it is also a limit distribution. (But that is a lot of theory!)
There are two possible moves by the robot per iteration:
A) Robot picks up a head coin and flips it and we have one less heads and one more tails.
B) Robot picks up a tail coin and tosses it.
B1) Outcome of the toss is head so we have one less tails and one more heads.
B2) Outcome of the toss is tail so we the same number of heads and tails before the toss since tail coin is put back to other coins as tail.
Probability of A move is H / (H + T)
Probability of BX move is T / (H + T) and probability of B1 or B2 is T / (H + T) x 2.
(where H is # of heads and T is # of tails)
Now chance that number of tails is going to be one less than previous iteration is T / (H + T) x 2
Chance that number of heads is going to be one less than previous iteration is H / (H + T)
Number of heads and tails will change until system comes to an equilibrium if there is such point and such equilibrium exists when the probability of one less heads is equal to probability of one less tails:
H / (H + T) = T / (H + T) x 2
If you solve the above equation you'll see that 2H = T is the equilibrium point.
You can do this rigorously without resorting to Markov chain theory:
It is sufficient to focus on just one particular coin and determine its probability of tails in the limit. Let p_n be its tail probability on the nth visit of the robot; the head probability is of course (1-p_n). We can set up the following recurrence relation for p_n:
p_n = [1-p_{n-1}] + 0.5p_{n-1}
which simplifies to
2p_n + p_{n-1} + 2 = 0
The solution of the characteristic polynomial of this relation yields the distinct roots -0.5 and 1. So the solution to the recurrence is of the form
p_n = C.(-0.5)^n + D(1)^n = C.(-0.5)^n + D, where C and D are constants
Obviously then, as n is taken to infinity, the term with coefficient C vanishes and D remains. I won't bother to compute D but others have noted it is 2/3. So it does converge.
Let's say you have N coins, nh heads, and nt tails.
N =nh +nt (1)
In one round, the robot goes through all of them (it is equivalent to saying that the robot randomly goes through coins if N is large). After one round
nt =(1/2) *nh (2)
nh =(1/2)*nh +nt (3)
(2) and (3) follow from the rules of the game. The process converges if there is a solution to the equations (1-3), so that after one round the distribution remains the same. Indeed, the solution is
nt =(1/3)*N
nh =(2/3)*N
#include <iostream>
using namespace std;
int main()
{
float heads = 50;
float tails = 50;
float factor = 0;
float difference = 0;
factor = heads /2;
for (int iCount = 0 ; iCount < 20 ; iCount++ )
{
if (iCount % 2 == 0 )
{
heads = heads + factor;
tails = tails - factor;
}
else
{
heads = heads - factor;
tails = tails + factor;
}
factor = factor/2;
cout << "Iteration: " << iCount << ": Heads = " << heads << " Tails = " << tails << endl;
}
return 0;
}
I am really scared from all these explanations... Markov chain Theory etc.
- Britney February 15, 2010So lets seek the solution in simple terms.
Head:
- due to a head, there is no way we can get a head again, since it will be flipped
- duet to a tail, we may get a head or a tail
thr4, h = 0 * h + (1/2) * t
Tail:
- due to a head, we are 100% sure that we'll get a tail, since it will be flipped
- due to a tail, we may get a head or a tail
thr4, t = 1 * h + (1/2) * t
And, h + t = 1 (obvious.. you can also add both the above equations and see)
so h + t =1
(1/2)t + t = 1
t = 2/3, h = 1/3