# Message Boards

Answer
(Unmark)

GROUPS:

8

# Pluses versus minuses: probabilistic analysis of the multiway system

Posted 4 months ago

At middle school, we’ve all learned the rules of multiplication of signs. Have you ever wondered which sign, + or -, would win in a “multiplication battle”? On the one hand, minuses can “infect” the pluses and turn them into minuses, but on the other hand, there can’t be too many minuses because they reduce each other to pluses. The current essay is about a simple mathematical game, where pluses and minuses are randomly multiplied between each other. The game starts with a list of numbers, each one either +1 or -1. During each turn, two numbers are chosen at random from the list and multiplied, and the result is written in place of the original numbers. Soon after the game is started, it tends to go into a state where the numbers of pluses and minuses are approximately equal, and remains there for a long time. In this mode, the probability distribution of the number of minuses is approximately normal with mean n/2 n 2O[n] n n
Introduction
Rules of the game We want to come up with the simplest possible rules that somehow facilitate the multiplications of pluses and minuses and lead to interesting behaviors. The game will involve a collection of + and - signs, so we will need a list of numbers, +1 or -1, for example, {-1,+1,-1,-1,+1} 1 .Prepare a list L n {-1,+1,-1,-1,+1,+1,+1,-1} 2 .Randomly select a pair of integers i j i≠j 3 .Compute the product of the i j L i j L L[[i]]=L[[j]]=L[[i]]*L[[j]] 4 .Return to step 2. In[]:= ClearAll[pmSystemSimulate];pmSystemSimulate[initState_, tmax_] := Block[{state = initState, i, j, val}, Prepend[Table[ (* step 2 *) i = RandomInteger[{1, Length[state]}]; (* choose a random number i *) While[!SameQ[i ≠ j, True], j = RandomInteger[{1, Length[state]}]]; (* choose a radom number j such that i ≠ j *) (* step 3 *) state[[i]] = state[[j]] = state[[i]] * state[[j]]; state, {t, 1, tmax}], initState]]; Here is an example of how the first 10 turns of this game might look like: In[]:= With[{tmax=10},Column@Table[Row[{"t = ",t," ",#[[t+1]]/.{-1->"-",+1->"+"}}],{t,0,tmax}]&@pmSystemSimulate[{-1,+1,-1,-1,+1,+1,+1,-1},tmax]] Out[]=
Because the rules are probabilistic, the same initial conditions can give rise to many different outcomes. To make the output easier to read, it can be helpful to colorize it. In the figure below, yellow represents +1 and blue represents -1. The time axis goes from top to bottom, with the t t In[]:= With[{n=Length[{-1,+1,-1,-1,+1,+1,+1,-1}],tmax=10},Graphics@Join[Flatten[Table[{If[#[[i,j]]1,Lighter@Blend[{Yellow,Orange}],Lighter@Blue],Rectangle[{j,tmax+1-i}]},{i,tmax},{j,n}]&@pmSystemSimulate[{-1,+1,-1,-1,+1,+1,+1,-1},tmax],1],Table[{Line[{{1,i},{n+1,i}}]},{i,tmax+1}],Table[{Line[{{j,1},{j,tmax+1}}]},{j,n+1}]]] Out[]= If two pluses are drawn, nothing changes because +1*+1=+1 -1*-1=+1 -1*+1=-1 In[]:= With[{n=12,tmax=80,repetitions=11},Table[Graphics[Join[Flatten[Table[{If[#[[i,j]]1,Lighter@Blend[{Yellow,Orange}],Lighter@Blue],Rectangle[{j,tmax+1-i}]},{i,tmax},{j,n}]&@pmSystemSimulate[ConstantArray[-1,n],tmax],1],Table[{Line[{{1,i},{n+1,i}}]},{i,tmax+1}],Table[{Line[{{j,1},{j,tmax+1}}]},{j,n+1}]],ImageSizeMedium],repetitions]] Out[]= , , , , , , , , , ,
Overview of the basic behaviors The game is in constant change. Nevertheless, a common pattern is that the numbers of pluses and minuses tend to stay approximately equal. If there are too many minuses, the probability of drawing two minuses increases, and so the number of minuses starts to drop; if there are too many pluses, then minuses start multiplying exponentially according to -1*+1=-1 In[]:= With[{n=Length[{-1,+1,-1,-1,+1,+1,+1,-1}],tmax=40,repetitions=8},Table[Graphics[Join[Flatten[Table[{If[#[[i,j]]1,Lighter@Blend[{Yellow,Orange}],Lighter@Blue],Rectangle[{j,tmax+1-i}]},{i,tmax},{j,n}]&@pmSystemSimulate[{-1,+1,-1,-1,+1,+1,+1,-1},tmax],1],Table[{Line[{{1,i},{n+1,i}}]},{i,tmax+1}],Table[{Line[{{j,1},{j,tmax+1}}]},{j,n+1}]],ImageSize->Medium],repetitions]] Out[]= , , , , , , , Sometimes, however, the game manages to reach a state where all the signs are pluses, the all-pluses state. And when it does reach this state, it never escapes because there are no pluses left to initiate the process, as in the example below: In[]:= With[{n=Length[{-1,+1,-1,-1,+1,+1,+1,-1}],tmax=100},Graphics@Join[Flatten[Table[{If[#[[i,j]]1,Lighter@Blend[{Yellow,Orange}],Lighter@Blue],Rectangle[{j,tmax+1-i}]},{i,tmax},{j,n}]&@pmSystemSimulate[{-1,+1,-1,-1,+1,+1,+1,-1},tmax],1],Table[{Line[{{1,i},{n+1,i}}]},{i,tmax+1}],Table[{Line[{{j,1},{j,tmax+1}}]},{j,n+1}]]] Out[]= These are the basic behaviors of the game, and this is what the rest of the essay will mostly be about. At first, the numbers of pluses and minuses tend to be approximately equal. The more signs are in the game, the more accurately is this rule satisfied. For example, the figure below shows one run of the game with 50 signs. It can be seen that the amount of blue and yellow are approximately the same; the rule seems to hold with more accuracy than in the case n=8 5.4× 147 10 In[]:= With[{n=50,tmax=100},Graphics@Join[Flatten[Table[{If[#[[i,j]]1,Lighter@Blend[{Yellow,Orange}],Lighter@Blue],Rectangle[{j,tmax+1-i}]},{i,tmax},{j,n}]&@pmSystemSimulate[Table[RandomChoice[{-1,1}],n],tmax],1],Table[{Line[{{1,i},{n+1,i}}]},{i,tmax+1}],Table[{Line[{{j,1},{j,tmax+1}}]},{j,n+1}]]] Out[]=
Connection to the Wolfram Physics Project The game is a so-called multiway system, which is basically a system that can evolve in multiple ways. The rules of evolution of the game can be formulated as {a___,x_,b___,y_,c___}{a,x*y,b,x*y,c} The function MultiwaySystem can be used to model the evolution of the game: In[]:= ResourceFunction["MultiwaySystem"][{a___,x_,b___,y_,c___}{a,x*y,b,x*y,c},{1,-1,-1,1},2,"StatesGraph"] Out[]= Very quickly, the states graph gets complicated: In[]:= ResourceFunction["MultiwaySystem"][{a___,x_,b___,y_,c___}{a,x*y,b,x*y,c},{1,-1,-1,1},#,"StatesGraph"]&/@Range[0,3] Out[]= , , , {+1,+1,+1,+1}
Simplifying the problem Because numbers are chosen from the list at random, the probabilities of drawing a +1 or a -1 are determined only by the numbers of pluses and minuses in the list, not their relative order. For this reason, all the necessary information about a state can be compressed to a tuple of the form { n + n - n + n - n + n - P[+]= n + n= n + n - P[-]= n - P[+|+]= n + n-1 P[-|+]= n - n P[-|-]= n - n-1 P[+|-]= n + n-1 p ++ n + n + n(n-1) p -- n - n - n(n-1) p +- 2 n + n - n(n-1) p ++ n + n + n(n-1) p -- n + n + n(n-1) p +- 2 n + n - n(n-1) ( 1 ) The ability to distill the information about a state to a pair of numbers greatly simplifies the problem. In the old picture, there could be O[ 2 n n { n + n - { n + n - { n + n - { n + n - Out[]= , Because the total number of signs n= n + n - n - n + n + n - p ++ p -- p +- n n - p ++ (n- n - n - n(n-1) p -- n - n - n(n-1) p +- 2(n- n - n - n(n-1) ( 2 ) The function pmNumbersSimulate uses the formula (1) to simulate the game (different runs can give different results because of the game’s randomness) with initial conditions { n + n - nsteps In[]:= ClearAll[pmNumbersSimulate];pmNumbersSimulate[npInit_, nmInit_, nsteps_] := Block[{n = npInit + nmInit, np = npInit, nm = nmInit}, Prepend[Table[ Switch[RandomInteger[{1, n(n-1)}], x_/;0 < x ≤ nm(nm-1), np += 2; nm -= 2, (* -- collision *) x_/;nm(nm-1) < x ≤ nm(nm-1) + 2np nm, np -= 1; nm += 1, (* +- collision *) _, Null(* a ++ coll |