A and B play ping pong game multiple times. The person serving first has a probability p of winning that game. A serves the first game and thereafter

A and B play ping pong game multiple times. The person serving first has a probability p of winning that game. A serves the first game and thereafter the loser serves first. What is the Probability that A wins the nth game?
double p;
double f(int n)
{
if(n==1)
return p;
else
{
double d = f(n-1);
return d*(1-p)+(1-d)*p;
}
}
where the d is the prob. of A win the (n-1)th game, so d*(1-p) means if A wins n-1 th game, what is the prob. for A wins nth game, (1-d)*p means if A loses n-1th game, what is the prob. for A wins nth game.

Given an integer n. Create an array of elements between 1..n in random order in the array. The probability of choosing a number for any position in th

Given an integer n. Create an array of elements between 1..n in random order in the array. The probability of choosing a number for any position in the array should be the same.
shuffling

Use 1-5 random generator to generate 1-7 random number

Use 1-5 random generator to generate 1-7 random number
Hint: How to do it with bit level
Roll the dice twice: and simply take XOR of result1 and ~result2, reject 7, keep 0~6.
explanation:
result1 is: 001 010 011 100 101
~result2 is: 110 101 100 011 010
You can see for each bit position the prob. of 1 bits is equal to prob. of 0 bits, and xor is also uniform distribution, thus result1 xor ~result2 is uniform distribution

Use 1-6 random generator to generate 1-7 random number

Use 1-6 random generator to generate 1-7 random number

int foo()
{
do
{
int x=rand6-1;//0~5
int y=rand6-1;
}
while((x*6+y)==35); //0~34 is valid
return (x*6+y)%7+1;//1~7
}

Generate m random numbers from n numbers

Generate m random numbers from n numbers

The prob. of first number is chosen is m/n
If the first number is not chosen, the prob. of second number is m/(n-1);
Otherwise the prob. of second number is m-1/(n-1)
……

{{{
for(int i=0;i<n;i++)
{
if(rand()%(n-i)<m)
{
cout<<i<<endl;
m--;
}
}
}}}

how to select M numbers from N existing numbers randomly and fairly (N>M). Example, assume that there are 10 numbers, you need to select 3 numbers fro

how to select M numbers from N existing numbers randomly and fairly (N>M). Example, assume that there are 10 numbers, you need to select 3 numbers from them randomly.

take 8 numbers, select one number from these 8 numbers, but not take away this number
add one number to the set, select one number from set, if the number is the selected number, just select the new added number.
add one number to the set, select one number from set, if the number is the selected number, just select the new added number

for the 8 numbers the probability of not chosen is 7/8 * 8/9 * 9/10=7/10
for the 9th number, the probability of not chosen is 7/9*9/10=7/10
for the 10th number, the probability of not chosen is 7/10
A={}
for(int i=n-m+1;i<=n;++i)
{
int a=rand()%i+1;
if(a is not in A)
A=A+{a};
else A=A+{i};
}

Take s numbers from n numbers with equal probability, n is unlimited

Take s numbers from n numbers with equal probability, n is unlimited

we can use reservoir sampling to solve this problem
-Store first s elements into R.
-for each element in position k = s+1 to n ,
--accept it with probability s/k
--if accepted, choose a random element from R to replace.

Simple example:
Suppose we take 2 numbers from 3 numbers
First, put first 2 numbers in R
Second, the prob. for the 3rd number to be taken is 2/3
Third, if 3rd number is taken, choose a number from R replaced by 3rd number.
The prob. for 3rd number to be taken is: 2/3
The prob. for 1st and 2nd number to drop is: (1/2)*(2/3)=1/3
So the prob. for 1st and 2nd number to take is: (1-(1/2)*(2/3))*1=2/3

for choose the 4th num(2/4), the prob. for 1st, 2nd and 3rd is (1-(1/2)*(2/4))*2/3=2/4

distributed system can speed up this sampling
http://blogs.msdn.com/spt/archive/2008/02/05/reservoir-sampling.aspx