sundries

  1At any point, the probability I eat a chocolate of the same type is m/n +
  2(n-m)/n*m/n, where m is the number of chocolates of the current type and n is
  3the total number of chocolates. This means that either we pick the chocolate
  4the first time or we don't and then we pick it the second time.
  5
  6For the non-current type, the probability is ((n-m)m/n)^2, since we'd have to
  7pick the same type twice.
  8
  9For example, if I have 9 chocolates, 7 dark and 2 milk (having just eaten a
 10dark), then the probability of eating a dark is 7/9 + (2/9 * (7/9)) ~= 95%.
 11
 12The probability of picking a given color after clearing the current color
 13(either the first choice or by picking a different color) is just m/n.
 14
 15It should be possible to programmatically generate all of the possible choices.
 16
 17There is a way to categorize all possible scenarios. The product of:
 18
 19- By number of each type (D, M) starting at (8, 2)
 20- By last picked type (D, M, N)
 21
 22Naively, that 81 possible states. However, the (8,2,X) state is only valid for X=N, so we can eliminate X=D and X=M.
 23
 24Now, we only care about the probability that the last chocolate we eat is milk, so the final state is anything where M=0, so we can delete all of those and have a single END state.
 25
 26We can also eliminate all states where D=0 since when that happens we know that the last chocolate we eat will be milk
 27
 28That brings the number of states to 53.
 29
 30D m D m D m D m D m D m D m D m M M
 31
 32D M L
 338 2 N
 348 1 D
 358 1 M
 368 1 N
 377 2 D
 387 2 M
 397 2 N
 407 1 D
 417 1 M
 427 1 N
 436 2 D
 446 2 M
 456 2 N
 466 1 D
 476 1 M
 486 1 N
 495 2 D
 505 2 M
 515 2 N
 525 1 D
 535 1 M
 545 1 N
 554 2 D
 564 2 M
 574 2 N
 584 1 D
 594 1 M
 604 1 N
 613 2 D
 623 2 M
 633 2 N
 643 1 D
 653 1 M
 663 1 N
 672 2 D
 682 2 M
 692 2 N
 702 1 D
 712 1 M
 722 1 N
 731 2 D
 741 2 M
 751 2 N
 761 1 D
 771 1 M
 781 1 N
 79END
 80
 81These nodes form a DAG, where:
 82  (D,M,L=D)
 83    (D-1,M,L=D)
 84    (D,M,L=N)
 85  (D,M,L=M)
 86    (D,M-1,L=M)
 87    (D,M,L=N)
 88  (D,M,L=N)
 89    (D-1,M,L=D)
 90    (D,M-1,L=M)
 91
 92Didn't follow this line of reasoning. Decided instead to brute-force the
 93solution. I tried a couple ways but messed up the first time (didn't print
 94enough digits). Figured out the problem by comparing to a second solution I
 95wrote.
 96
 97Let's see if we can get the proof:
 98
 99The simplest case is D=1,M=1, where you eat the first one you pick, so it's
100obviously P=1/2.
101
102Let's look at the case where D=2,M=1.
103
1041/3 chance M => B
1052/3 chance D
106    1/2 chance D => G
107    1/2 chance m
108        1/2 chance D => G
109        1/2 chance M => B
110
111So the probability of ending with M is 2/3 * (1/2+1/2*1/2) = 1/2
112
113So, how does this generalize?