1

Let us say we have 10 placards with numbers from (-5 to 5 excluding zero) laid in a circular fashion. In each round, you perform a swap such that you switch the position of two adjacent placards . Find the expected number of swaps such that no two adjacent placards sum to zero.

I am looking for translating this into a markov chain, could someone give me an idea?

Arctic Char
  • 16,007
Satish Ramanathan
  • 11,984
  • What is the starting position? Is it $-5, -4, -3, -2, -1, 1, 2, 3, 4, 5$ or $-5, 5, -4, 4, -3, 3, -2, 2, -1, 1$? – Calvin Lin Mar 17 '23 at 17:50
  • It is randomly arranged at the beginning – Satish Ramanathan Mar 17 '23 at 17:52
  • I presume the swaps are also uniformly random? This looks pretty complicated; the chain will have lots of inequivalent states. Where did you encounter this problem? Is it perhaps meant to be solved with a computer? – joriki Mar 17 '23 at 20:24
  • This problem was inspired to mimic an contest problem from HMMT 2023 Feb. I wanted to reframe the ask in the question into something measurable. https://hmmt-archive.s3.amazonaws.com/tournaments/2023/feb/guts/problems.pdf - Problem 30 – Satish Ramanathan Mar 18 '23 at 12:17
  • @Satish Ramanathan I'm sure the swaps in that HMMT problem are not intended to be random. If $\ S(C)\ $ is the minimum number of swaps needed to separate all the adjacent pairs of twins in a given configuration $\ C\ $, there's a nifty way of determining the value of $\ S(C)\ $ for any $\ C\ $. The question is asking for the expected value of $\ S(C)\ $ when $\ C\ $ is chosen uniformly at random. Determining it is an exercise in the use of linearity of expectations. – lonza leggiera Mar 20 '23 at 14:45
  • @lonzaleggiera, I agree that i might have not understood the "minimum number of swaps" into the reading of the ask in the problem. – Satish Ramanathan Mar 21 '23 at 07:23
  • Given a sequence of coin flips, such as ‘HTTHTHT...’, we define an inversion as a switch from H to T or T to H. For instance, the sequence ‘HTTHT’ has 3 inversions. Harrison has a weighted coin that lands on heads 2/3 of the time and tails 1/3 of the time. If Harrison flips the coin 10 times, what is the expected number of inversions in the sequence of flips - Answer: $\sum_{p=1}^{9}\sum_{i=0}^{10} p(2/3)^i (1/3)^(10-i)(\binom{i-1} {p})(\binom {11-i} {(i-p)})=4$ – Satish Ramanathan Nov 16 '23 at 06:52

0 Answers0