Coins with values 1 through N (inclusive) are placed into a bag. All the coins from the bag are iteratively drawn (without replacement) at random. For the first coin, you are paid the value of the coin. For subsequent coins, you are paid the absolute difference between the drawn coin and the previously drawn coin. For example, if you drew 5,3,2,4,1, your payments would be 5,2,1,2,3 for a total payment of 13.
Please provide 5 digits of precision for all answers.
What is the mean of your total payment for N=10?
What is the standard deviation of your total payment for N=10?
What is the probability that your total payment is greater than or equal to 45 for N=10?
Answers
Coins with values 1 through N (inclusive) are placed into a bag. All the coins from the bag are iteratively drawn (without replacement) at random. For the first coin, you are paid the value of the coin. For subsequent coins, you are paid the absolute difference between the drawn coin and the previously drawn coin. For example, if you drew 5,3,2,4,1, your payments would be 5,2,1,2,3 for a total payment of 13.
Please provide 5 digits of precision for all answers.
What is the mean of your total payment for N=10?
What is the standard deviation of your total payment for N=10?
What is the probability that your total payment is greater than or equal to 45 for N=10?
Step-by-step explanation:
(n+1)(2n+1)/6
σ=E[X2]−(E[X])2−−
S=X1+∑Nk=2|Xk−Xk−1|
E(S)==E(X1+∑k=2N|Xk−Xk−1|)E(X1)+∑k=2NE(|Xk−Xk−1|).
The expected value of the first coin is 12(N+1). There are N−j pairs at distance j from each other, with 1≤j≤N−1, and all pairs are equally likely, so
E(|Xk−Xk−1|)===∑N−1j=1(N−j)j∑N−1j=1(N−j)16(N−1)N(N+1)12(N−1)N13(N+1).
Thus, in total
E(S)==12(N+1)+(N−1)⋅13(N+1)16(N+1)(2N+1).
he expected value of the square of S is
E(S2)==E⎛⎝(X1+∑k=2N|Xk−Xk−1|)2⎞⎠E(X21)+2∑k=2NE(X1⋅|Xk−Xk−1|)+E⎛⎝(∑k=2N|Xk−Xk−1|)2⎞⎠.
Let’s go through the terms one by one. The first one is
E(X21)==1N∑k=1Nk216(N+1)(2N+1).
X1≠Xk for k≠1. Then
∑x1=1N∑xk−1<xkx1(xk−xk−1)=N(N+1)2⋅(N−1)N(N+1)6,
This accounts for N2(N−1)2 triples; from this we have to subtract a contribution where X1=Xk−1<Xk:
∑x1=1N∑xk=x1+1Nx1(xk−x1)==∑x1=1Nx1(N−x1)(x1+1+N2−x1)(N−1)N(N+1)(N+2)24
and a contribution where Xk−1<Xk=X1:
∑x1=1N∑xk−1=1x1−1x1(x1−xk−1)==∑x1=1Nx1(x1−1)(x1−x12)(N−1)N(N+1)(3N+2)24,
which together account for N(N−1) triples. ∴ we have
E(X1⋅|X2−X1|)==(N−1)N(N+1)((N+2)+(3N+2))24N(N−1)16(N+1)2
and
∑k=3NE(X1⋅|Xk−Xk−1|)==(N−2)112(N−1)N2(N+1)2−16(N−1)N(N+1)212N2(N−1)−N(N−1)16(N−2)(N+1)2,
We get a total of:
∑k=2NE(X1⋅|Xk−Xk−1|)=16(N−1)(N+1)2.
∑k=2NE((Xk−Xk−1)2)===(N−1)∑N−1j=1(N−j)j2∑N−1j=1(N−j)(N−1)112(N−1)N2(N+1)12(N−1)N16(N−1)N(N+1).
N−1E(|Xk−Xk−1|⋅|Xk+1−Xk|)===(N−2)∑N−2i=1∑N−1−ij=113(i2+j2+3ij)(N−i−j)∑N−2i=1∑N−1−ij=1(N−i−j)(N−2)1360(N−2)(N−1)N(N+1)(7N+4)16(N−2)(N−1)N160(N−2)(N+1)(7N+4).
E(|X4−X3|⋅|X2−X1|)===∑N−3i=1∑N−2−ij=1∑N−1−i−jk=113(ik+(i+j)(j+k)+(i+j+k)j)(N−i−j−k)∑N−3i=1∑N−2−ij=1∑N−1−i−jk=1(N−i−j−k)11080(N−3)(N−2)(N−1)N(N+1)(5N+4)124(N−3)(N−2)(N−1)N145(N+1)(5N+4).
E(S2)==16(N+1)(2N+1)+13(N−1)(N+1)2+16(N−1)N(N+1)+130(N−2)(N+1)(7N+4)+145(N−3)(N−2)(N+1)(5N+4)190(N+1)(10N3+24N2+5N+9).
variance of the sum is
E(S2)−E(S)2==190(N+1)(10N3+24N2+5N+9)−(16(N+1)(2N+1))21180(N+1)(8N2−15N+13).