1

Five cards labeled 1, 3, 5, 7, 9 are laid in a row in that order, forming the five-digit number 13579 when read from left to right. A swap consists of picking two distinct cards, and then swapping them. After three swaps, the cards form a new five-digit number n when read from left to right. Compute the expected value of n.

I have shown my attempt to solve the problem in an answer. Could someone vet the solution.

Satish Ramanathan
  • 11,984

2 Answers2

1

Here's a slightly simpler way of calculating the exact expected value of $\ n\ $. After the OP's correction to my original calculation (in which I made an arithmetical error), it gives the same answer as his.

After $3$ swaps, there will be a probability $\ p\ \ \big($which turns out to be $\ \frac{3}{10}\ \big) $ that the digit in any given place will be the same as it was at the start, and a probability of $ \frac{1-p}{4}\ \left(=\frac{7}{40}\right)\ $ that it will be any one of the other $4$ digits. The expected value of $\ n\ $ is therefore \begin{align} 10^4\Big(&p\cdot1+\frac{(1-p)(25-1)}{4}\Big)+10^3\left(p\cdot3+\frac{(1-p)(25-3)}{4}\right)\\ &+10^2\Big(p\cdot5+\frac{(1-p)(25-5)}{4}\Big)+10\left(p\cdot7+\frac{(1-p)(25-7)}{4}\right)\\ &\hspace{1.5em}+p\cdot9+\frac{(1-p)(25-9)}{4}\\ &\hspace{3em}=\left(\frac{5p-1}{4}\right)13579+\left(\frac{25(1-p)}{4}\right)11111\\ &\hspace{3em}=\frac{13579+35\cdot11111}{8}\\ &\hspace{3em}=50308 \end{align} You can calculate the value of $\ p\ $ by treating the presence or absence of the original digit in any place as a two-state Markov chain with transition matrix $$ \pmatrix{\frac{3}{5}&\frac{2}{5}\\\frac{1}{10}&\frac{9}{10}}\ , $$ since the probability is $\ \frac{1}{10}\ $ that a single swap will return any given digit back to its original place once it has been swapped out of it. The initial state of the chain is $1$, and there are $4$ sequences of states that end with with the digit originally in the place being back there after $3$ swaps. Those sequences and their probabilities are: $$ \begin{array}{cc} \text{state sequence}&\text{probability}\\ 1111&\left(\frac{3}{5}\right)^3=\frac{27}{125}\\ 1121&\left(\frac{3}{5}\right)\left(\frac{2}{5}\right)\left(\frac{1}{10}\right)=\frac{3}{125}\\ 1211&\left(\frac{2}{5}\right)\left(\frac{1}{10}\right)\left(\frac{3}{5}\right)=\frac{3}{125}\\ 1221&\ \left(\frac{2}{5}\right)\left(\frac{9}{10}\right)\left(\frac{1}{10}\right)=\frac{9}{250}\ , \end{array} $$ and the sum of these probabilities is $\ \frac{3}{10}\ $, as stated above.

lonza leggiera
  • 28,646
  • 2
  • 12
  • 33
  • You had made calculation mistake and I had corrected and now you are correct. I took the liberty to correct it – Satish Ramanathan Apr 03 '22 at 17:56
  • Thank you. Like Jean Marie, I didn't understand your own solution until I saw that your correction to mine gave the same answer. It didn't occur to me that lulu might have been pointing out that your solution is correct, and I'm still not sure whether that's the case or not. However, I do think the exposition of your solution could have been made clearer by noting more explicitly that your $5$-state Markov chain was really $5$ separate Markov chains with initial states $1$ for position $1$, $3$ for position $2$, and so on. – lonza leggiera Apr 04 '22 at 00:27
0

Let there be five states 1, 3, 5, 7 and 9. The probability that 1 will be swapped with 3 is $\frac{1}{10}$. Similarly the probabiilty that 1 will be swapped with other numbers will be the same. Proability that 1 will not be swapped is $\frac{6}{10}$ The first matrix is the transition matrix and it is exponentiate three times to signify the three swaps and the last matrix is the probability weighted sum of all instances. The prob that 1 would remain 1 is $0.3$ after three swaps times the value of the digit times the place of the digit 10^4 = 3000.

Thus it is a markov chain with the transition matrix as shown in the excel image and the expected $n = 50308$ enter image description here

Satish Ramanathan
  • 11,984
  • I don't understand how you can associate a "state" to one of the numbers $1,3,5,7,9$... For example, which would be the active state if, on the second step you have for example a permutation between $7$ and $9$ ? Managing things from the point of view of an element, here $1$ is hopefully not good. Besides, "The prob that 1 would remain 1 is 0.2031110^4 = 2031." Where does this assertion comes from ? Do you realize that exchanging for example $1$ and $2$ and then again $1$ and $2$ will leave $1$ in the same position ? – Jean Marie Mar 12 '22 at 17:21
  • Let us see where my reasoning goes wrong or right. IN the first swap, 1 will remain in 1 ( 1 is associated to the starting digit) with prob 0.6 ( In other words 1 is not one of the two numbers picked ( ${5\choose2} 10$. In the second swap, 1 remains 1 not with the same probability that that governed by the chain. After the third swap, the prob is 0.203125 ( it factors the prior probability leading to the third swap). – Satish Ramanathan Mar 12 '22 at 17:34
  • I realise that excahgning 1 and 2 and then again 1 and 2 will leave in the same posiiton and we are in the process of determining what that probability is, are we not? Let me know if I fail to understand. I am just trying this strategy – Satish Ramanathan Mar 12 '22 at 17:34
  • Intuittivley, the answer is moving toward the middle ground – Satish Ramanathan Mar 12 '22 at 17:36
  • You definitively cannot have a Markov chain with 5 states only for the reason I have given in my first sentence. – Jean Marie Mar 12 '22 at 17:37
  • Could you suggest a solution in the same line – Satish Ramanathan Mar 12 '22 at 17:41
  • @JeanMarie By Linearity, we can work one place at a time. Each place has $5$ states (according to which digit occupies that at that instant). Each state transitions either back to itself ($\frac 35$) or to any other state uniformly. Once you know the expected value of each place, you can get the expected value of the answer. – lulu Mar 12 '22 at 17:57
  • As a possibly useful approximation: if we did thousands of swaps then surely each place has an equal chance of being in any state. Thus the expected value of each place (in the limit) is $5$, so $55555$ would be the expected value. Not sure how helpful this is, as any "mixing" algorithm is likely to yield this limit. – lulu Mar 12 '22 at 18:01
  • @LuLU, yes you are correct. After many swaps, it will average out to 55555. My answer is approaching that. The solution for this problem has not been released yet by HMMT. WOndering how to solve it analytically – Satish Ramanathan Mar 12 '22 at 18:04
  • As I say though, this would be true for just about any mixing rule. Not sure if it provides a useful guide for testing any particular computation. Good for testing a simulator though. – lulu Mar 12 '22 at 18:05
  • @lulu You are right. I hadn't thought to linearity. Thank you very much. – Jean Marie Mar 13 '22 at 08:09