TransWikia.com

How to program combinatorics problems about randomly moving cards from $A$ to $B$ to $C$ to $A$?

Mathematica Asked by Kim Jong Un on May 15, 2021

I have a lot of problems with the following scenario, for example,

Given 3 boxes $A$, $B$ and $C$.

  • The box $A$ contains 2 identical cards $x$, 4 identical cards $y$ and 1 card $z$.
  • The box $B$ contains 2 identical cards $x$, 3 identical cards $y$ and 1 card $z$.
  • The box $C$ contains 4 identical cards $x$, 4 identical cards $y$ and no card $z$.

The following actions are performed in the following order

  • Randomly move 2 cards from $A$ to $B$.
  • Randomly move 2 cards from $B$ to $C$.
  • Randomly move 3 cards from $C$ to $A$.

Find the probability for the events in which the boxes $A$ and $B$ each still has one card $z$ after performing the three actions above. The cards $z$ are also identical. More precisely, the cards $z$ may move or may not move.

Solving a lot of problems of this kind with bare hands is really error prone.

Attempt

I have no idea how to program this. Does it need graph representations?

There are only two possible disjoint cases:

  • Case 1: The $z$ cards never move.
  • Case 2: A single $z$ card moves from $A$ to $B$ to $C$ and returns to $A$.

Without loss of generality, the $x$ and $y$ cards can actually be considered as $star$ cards for example.

The initial states for these boxes are

  • $A={6star, 1m}$
  • $B={5star, 1m}$
  • $C={8star, 0m}$

Now calculate the probability for each case.

  • Case 1:

    • When moving 2 $star$ cards from $A={6star,1m}$, the probability is $frac{{6 choose 2}}{{7choose 2}}=frac{5}{7}$. The current state of the involved boxes are $A={4star,1m}$ and $B={7star,1m}$.
    • When moving 2 $star$ cards from $B={7star,1m}$, the probability is $frac{{7 choose 2}}{{8choose 2}}=frac{3}{4}$. The current state of the involved boxes are $B={5star,1m}$ and $C={10star,0m}$.
    • When moving 3 $star$ cards from $C={10star,0m}$, the probability is $frac{{10 choose 3}}{{10choose 3}}=1$. The current state of the involved boxes are $C={7star,0m}$ and $A={7star,1m}$.

    The probability for the first case is $frac{5}{7}times frac{3}{4}=frac{15}{28}$.

  • Case 2:

    • When moving 1 $star$ card and 1 $z$ card from $A={6star,1m}$, the probability is $frac{{6 choose 1}{1 choose 1}}{{7choose 2}}=frac{2}{7}$. The current state of the involved boxes are $A={5star,0m}$ and $B={6star,2m}$.
    • When moving 1 $star$ card and 1 $z$ card from $B={6star,2m}$, the probability is $frac{{6 choose 1}{2choose 1}}{{8choose 2}}=frac{3}{7}$. The current state of the involved boxes are $B={5star,1m}$ and $C={9star,1m}$.
    • When moving 1 $star$ card and 1 $z$ card from $C={9star,1m}$, the probability is $frac{{9 choose 2}{1choose 1}}{{10choose 3}}=frac{3}{10}$. The current state of the involved boxes are $C={7star,0m}$ and $A={7star,1m}$.

    The probability for the second case is $frac{2}{7}times frac{3}{7} times frac{3}{10}=frac{9}{245}$.

The total probability is $frac{15}{28}+frac{9}{245}=frac{561}{980}$.

2 Answers

Just a very quick-n-dirty. The correct route is to investigate the appropriate multi-urn distributions, which when/if time permits I will do so and update.

A move/result function:

domoves[boxes_, from_, to_, count_] := 
  Module[{moves = 
     Join @@ Permutations /@ 
       IntegerPartitions[count, {Length@boxes[[1]]}, Range[0, count]],
     pmf},
   Table[pmf = 
     PDF[MultivariateHypergeometricDistribution[count, boxes[[from]]],
       mv];
    If[pmf == 0, Nothing[],
     ReplacePart[
      boxes, {from -> boxes[[from]] - mv, 
       to -> boxes[[to]] + mv, -1 -> boxes[[-1]]*pmf}]], {mv, 
     moves}]];

Starting boxes specification:

boxes={{2, 4, 1}, {2, 3, 1}, {4, 4, 0},1};

Do the three rounds of moves:

round1 = domoves[boxes, 1, 2, 2];
round2 = Flatten[domoves[#, 2, 3, 2] & /@ round1, 1];
round3 = Flatten[domoves[#, 3, 1, 3] & /@ round2, 1];

Select results with desired characteristics from final round, total probabilities:

Select[round3, #[[1, -1]] == 1 && #[[2, -1]] == 1 &][[All, -1]] // Tr

561/980

Since the last round contains all possible results, you can reuse it with differing selects to query other result probabilities.

You can polish this framework into a generalized function to take starting state, sequence of moves, and characteristics to get desired probability.

Correct answer by ciao on May 15, 2021

I solved this numerically by simulation as follows:

SeedRandom[1];

draw[list_, n_] := TakeDrop[RandomSample[list], n];
simulate[] := Module[{
   a = {x, x, y, y, y, y, z},
   b = {x, x, y, y, y, z},
   c = {x, x, x, x, y, y, y, y}, t},
  {t, a} = draw[a, 2]; b = Join[b, t];
  {t, b} = draw[b, 2]; c = Join[c, t];
  {t, c} = draw[c, 3]; a = Join[a, t];
  Return[{a, b, c}];
]

count = 0;
Do[
 count += Boole[AllTrue[simulate[][[1 ;; 2]], MemberQ[#, z] &]];
 , {1000000}
 ]
count/1000000

(* result: 571612 / 1000000 *)

This value 0.571612 is very close to your answer of 561/980 (0.572449).

Answered by flinty on May 15, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP