Coprime Scoreboard and Probability

Question

In a more Intuitional Description:

My friends and I were working on a problem of a scoreboard problem. It's a scoreboard that automatically "simplifies" itself (we tend to read $7:2$ as "7 to 2", which makes people think of fractions). Simplified fractions and the original ones are the same, so we want to know what will happen if the scoreboard does the same thing.

Hence, if the current score is $19:15$ and the left team wins a point, it becomes $4:3$ (divided by $5$ on both sides), and if the right-hand side gets a point it goes to $1:1$ (divided by $4$ on both sides). We consider both sides to have an equal chance of winning a point.

Notice, the order of the points matters, if we switch the scoring order from the case above, $19:15$ will firstly become $19:16$, and then $5:4$ (divided by $4$).

The following gives the problem written in a formalized language.

---

In Formalized Language:

In an experiment, we let the $0\,$th state be $(0,0)$. For $k\,$th state $(a,b)$, $(k+1)\,$th state has equal probabilities, $50\%$ each, to become $$\left(\frac{a+1}{\gcd(a+1,b)},\frac{b}{\gcd(a+1,b)}\right)$$ or $$\left(\frac{a}{\gcd(a,b+1)},\frac{b+1}{\gcd(a,b+1)}\right)$$ where we define $\gcd(0,a)=\gcd(a,0)=a$ for all $a\in\mathbb{N}$.

We use $f_n(a,b)$ to denote the probability that the $n\,$th state is $(a,b)$, and define $f(a,b)$ by $$f(a,b)=\lim_{n\to\infty}f_n(a,b).$$ Based on the definitions above, we want to know

• If $\lim_{n\to\infty}f_n(a,b)$ exists.
• For all $p$ and $q$ satisifying $\gcd\left(p,q\right)=1$, $f\left(p,q\right)=0$ only when $p\cdot q=0$.
• The value of $f\left(1,1\right)$.
• The value of $f\left(p,q\right)$ for all $\gcd\left(p,q\right)=1$, in terms of $p$ and $q$.

---

Our Current Process:

Trivially, $$f\left(0,0\right)=f\left(0,1\right)=f\left(1,0\right)=0.$$

And numerically, $$f_{10}\left(1,1\right)=0.2128906250,$$ $$f_{20}\left(1,1\right)=0.1955623627,$$ $$f_{30}\left(1,1\right)=0.1951741818,$$ $$f_{40}\left(1,1\right)=0.1951625187,$$ $$f_{50}\left(1,1\right)=0.1951622049,$$ $$f_{60}\left(1,1\right)=0.1951621955\cdots$$

which does not seem to converge to $0$.

Answer 1

Not an answer but some data: I iterated a run of $10$ million states and tallied the data. The limiting distribution looks plausibly close to whatever the actual limiting distribution is:

Here's some raw data from this run for those interested:

{1, 1}: 1952843 ... {2, 1}: 1471915 ... {1, 2}: 1469527 ... {3, 1}: 864595 ... {1, 3}: 862256 ... {4, 1}: 463755 ... {1, 4}: 461918 ... {3, 2}: 448044 ... {2, 3}: 446685 ... {5, 1}: 239977 ... {1, 5}: 238090 ... {6, 1}: 121992 ... {1, 6}: 120799 ... {5, 2}: 119944 ... {2, 5}: 119157 ... {7, 1}: 61556 ... {5, 3}: 61143 ... {3, 5}: 60688 ... {1, 7}: 60614 ... {8, 1}: 31070 ... {7, 2}: 30736 ... {1, 8}: 30612 ... {5, 4}: 30391 ... {4, 5}: 30347 ... {2, 7}: 30269 ... {9, 1}: 15528 ... {1, 9}: 15388 ... {7, 3}: 15380 ... {3, 7}: 15261 ... {10, 1}: 7843 ... {7, 4}: 7810 ... {4, 7}: 7777 ... {2, 9}: 7762 ... {9, 2}: 7691 ... {1, 10}: 7635 ... {8, 3}: 7583 ... {3, 8}: 7499 ... {7, 5}: 3943 ... {11, 1}: 3903 ... {5, 7}: 3894 ... {1, 11}: 3774 ... {7, 6}: 2004 ... {12, 1}: 1969 ... {6, 7}: 1965 ... {3, 4}: 1965 ... {8, 5}: 1942 ... {11, 2}: 1934 ... {1, 12}: 1933 ... {5, 8}: 1929 ... {4, 3}: 1929 ... {2, 11}: 1841 ... {9, 5}: 997 ... {1, 13}: 992 ... {13, 1}: 990 ... {5, 9}: 976 ... {11, 3}: 961 ... {3, 11}: 923 ... {2, 13}: 523 ... {14, 1}: 510 ... {13, 2}: 480 ... {4, 11}: 470 ... {1, 14}: 469 ... {11, 4}: 465 ... {3, 13}: 274 ... {5, 11}: 268 ... {15, 1}: 252 ... {1, 15}: 235 ... {11, 5}: 225 ... {13, 3}: 224 ... {5, 12}: 148 ... {3, 14}: 143 ... {5, 13}: 136 ... {16, 1}: 134 ... {4, 13}: 131 ... {6, 11}: 120 ... {15, 2}: 118 ... {1, 16}: 118 ... {2, 15}: 117 ... {13, 5}: 116 ... {14, 3}: 114 ... {11, 6}: 114 ... {12, 5}: 111 ... {13, 4}: 110 ... {6, 13}: 69 ... {5, 14}: 67 ... {13, 6}: 61 ... {7, 11}: 59 ... {11, 7}: 58 ... {17, 1}: 57 ... {7, 13}: 56 ... {14, 5}: 55 ... {1, 17}: 51 ... {13, 7}: 35 ... {7, 12}: 34 ... {11, 8}: 30 ... {18, 1}: 29 ... {17, 2}: 28 ... {12, 7}: 28 ... {2, 17}: 27 ... {8, 11}: 25

Answer 2

Author's Process Update

This is not an answer, and the reason I didn't edit my question is because this is a data-based approach, and is too long for a neat description.

By enumeration, we've coded a C++ program that covered all $2^{60}$ cases with a length of $60$ steps. Here's what we've got.

$p$	$q$	$f_{60}\left(p,q\right)$ or $f_{60}\left(q,p\right)$
$1$	$ 1$	$ 0.1951621955$
$1$	$ 2$	$ 0.1469828235$
$1$	$ 3$	$ 0.0863545239$
$1$	$ 4$	$ 0.0463021500$
$2$	$ 3$	$ 0.0447490581$
$1$	$ 5$	$ 0.0239345435$
$1$	$ 6$	$ 0.0121609998$
$2$	$ 5$	$ 0.0119673542$
$1$	$ 7$	$ 0.0061289452$
$3$	$ 5$	$ 0.0060812358$
$1$	$ 8$	$ 0.0030765491$
$2$	$ 7$	$ 0.0030765369$
$4$	$ 5$	$ 0.0030406561$
$3$	$ 7$	$ 0.0015443045$
$1$	$ 9$	$ 0.0015412937$
$4$	$ 7$	$ 0.0007732846$
$3$	$ 8$	$ 0.0007721524$
$1$	$ 10$	$0.0007714011$
$2$	$ 9$	$ 0.0007710239$
$5$	$ 7$	$ 0.0003873967$
$1$	$ 11$	$0.0003858891$
$3$	$ 4$	$ 0.0001945414$
$6$	$ 7$	$ 0.0001938398$
$5$	$ 8$	$ 0.0001936984$
$1$	$ 12$	$0.0001929917$
$2$	$ 11$	$0.0001929446$
$5$	$ 9$	$ 0.0000968787$
$1$	$ 13$	$0.0000965076$
$3$	$ 11$	$0.0000964958$
$1$	$ 14$	$0.0000482568$
$2$	$ 13$	$0.0000482568$
$4$	$ 11$	$0.0000482479$
$1$	$ 15$	$0.0000241291$
$3$	$ 13$	$0.0000241284$
$5$	$ 11$	$0.0000241240$
$1$	$ 16$	$0.0000120647$
$2$	$ 15$	$0.0000120646$
$4$	$ 13$	$0.0000120644$
$3$	$ 14$	$0.0000120642$
$5$	$ 13$	$0.0000120632$
$5$	$ 12$	$0.0000120621$
$6$	$ 11$	$0.0000120620$
$7$	$ 11$	$0.0000060330$
$1$	$ 17$	$0.0000060324$
$5$	$ 14$	$0.0000060316$
$6$	$ 13$	$0.0000060316$
$7$	$ 13$	$0.0000045242$
$7$	$ 12$	$0.0000030166$
$8$	$ 11$	$0.0000030165$
$1$	$ 18$	$0.0000030162$
$2$	$ 17$	$0.0000030162$
$8$	$ 13$	$0.0000022621$
$9$	$ 11$	$0.0000015083$
$1$	$ 19$	$0.0000015081$
$3$	$ 17$	$0.0000015081$
$9$	$ 13$	$0.0000011310$
$10$	$11$	$0.0000007542$
$1$	$ 20$	$0.0000007541$
$2$	$ 19$	$0.0000007541$
$4$	$ 17$	$0.0000007541$
$9$	$ 14$	$0.0000005655$
$10$	$13$	$0.0000005655$
$5$	$ 6$	$ 0.0000003778$
$1$	$ 21$	$0.0000003770$
$3$	$ 19$	$0.0000003770$
$5$	$ 17$	$0.0000003770$
$11$	$13$	$0.0000002828$
$1$	$ 22$	$0.0000001885$
$2$	$ 21$	$0.0000001885$
$3$	$ 20$	$0.0000001885$
$4$	$ 19$	$0.0000001885$
$5$	$ 18$	$0.0000001885$
$5$	$ 19$	$0.0000001885$
$6$	$ 17$	$0.0000001885$
$11$	$14$	$0.0000001414$
$12$	$13$	$0.0000001414$
$1$	$ 23$	$0.0000000943$
$6$	$ 19$	$0.0000000943$
$7$	$ 17$	$0.0000000943$
$7$	$ 19$	$0.0000000707$
$11$	$15$	$0.0000000707$
$1$	$ 24$	$0.0000000471$
$2$	$ 23$	$0.0000000471$
$3$	$ 10$	$0.0000000471$
$4$	$ 9$	$ 0.0000000471$
$7$	$ 18$	$0.0000000471$
$8$	$ 17$	$0.0000000471$
$7$	$ 20$	$0.0000000353$
$8$	$ 19$	$0.0000000353$
$11$	$16$	$0.0000000353$
$1$	$ 25$	$0.0000000236$
$3$	$ 23$	$0.0000000236$
$9$	$ 17$	$0.0000000236$
$11$	$17$	$0.0000000236$
$9$	$ 19$	$0.0000000177$
$1$	$ 26$	$0.0000000118$
$2$	$ 25$	$0.0000000118$
$4$	$ 23$	$0.0000000118$
$10$	$17$	$0.0000000118$
$11$	$18$	$0.0000000118$
$12$	$17$	$0.0000000118$
$11$	$19$	$0.0000000103$
$9$	$ 20$	$0.0000000088$
$10$	$19$	$0.0000000088$
$1$	$ 27$	$0.0000000059$
$3$	$ 25$	$0.0000000059$
$5$	$ 23$	$0.0000000059$
$13$	$17$	$0.0000000059$
$11$	$20$	$0.0000000052$
$12$	$19$	$0.0000000052$
$13$	$19$	$0.0000000041$
$7$	$ 10$	$0.0000000035$
$1$	$ 28$	$0.0000000029$
$2$	$ 27$	$0.0000000029$
$3$	$ 26$	$0.0000000029$
$4$	$ 25$	$0.0000000029$
$5$	$ 24$	$0.0000000029$
$6$	$ 23$	$0.0000000029$
$7$	$ 9$	$ 0.0000000029$
$13$	$18$	$0.0000000029$
$14$	$17$	$0.0000000029$
$11$	$21$	$0.0000000026$
$13$	$20$	$0.0000000020$
$14$	$19$	$0.0000000020$
$8$	$ 9$	$ 0.0000000018$
$1$	$ 29$	$0.0000000015$
$7$	$ 23$	$0.0000000015$
$15$	$17$	$0.0000000015$
$13$	$21$	$0.0000000010$
$15$	$19$	$0.0000000010$
$1$	$ 30$	$0.0000000007$
$2$	$ 29$	$0.0000000007$
$7$	$ 24$	$0.0000000007$
$8$	$ 23$	$0.0000000007$
$16$	$17$	$0.0000000007$
$13$	$22$	$0.0000000005$
$16$	$19$	$0.0000000005$
$1$	$ 31$	$0.0000000004$
$3$	$ 29$	$0.0000000004$
$7$	$ 25$	$0.0000000004$
$9$	$ 23$	$0.0000000004$
$13$	$23$	$0.0000000003$
$17$	$19$	$0.0000000003$
$1$	$ 32$	$0.0000000002$
$2$	$ 31$	$0.0000000002$
$4$	$ 29$	$0.0000000002$
$7$	$ 26$	$0.0000000002$
$8$	$ 25$	$0.0000000002$
$10$	$23$	$0.0000000002$
$1$	$ 33$	$0.0000000001$
$3$	$ 31$	$0.0000000001$
$5$	$ 29$	$0.0000000001$
$7$	$ 27$	$0.0000000001$
$9$	$ 10$	$0.0000000001$
$9$	$ 25$	$0.0000000001$
$11$	$23$	$0.0000000001$
$13$	$24$	$0.0000000001$
$13$	$25$	$0.0000000001$
$14$	$23$	$0.0000000001$
$15$	$23$	$0.0000000001$
$17$	$20$	$0.0000000001$
$17$	$21$	$0.0000000001$
$18$	$19$	$0.0000000001$

And all the other terms that are not mentioned above have a $f_{60}\left(p,q\right)<0.0000000001$.

---

And here's the code.

#include<bits/stdc++.h>
using namespace std;
struct score{
    int a;
    int b;
    long long v;
}s[105][10000];
int cnt[105];
long long mp[105][105];
int main(){
    cnt[0]=1;
    s[0][1]=(score){0,0,1};
    for(int i=1;i<=60;i++){  
        memset(mp,0,sizeof(mp));
        for(int j=1;j<=cnt[i-1];j++){
            int d=__gcd(s[i-1][j].a+1,s[i-1][j].b);
            int x=(s[i-1][j].a+1)/d,y=s[i-1][j].b/d;
            if(!mp[x][y]){
                s[i][++cnt[i]]=(score){x,y,0};
            }
            mp[x][y]+=s[i-1][j].v;
        }
        for(int j=1;j<=cnt[i-1];j++){
            int d=__gcd(s[i-1][j].a,s[i-1][j].b+1);
            int x=(s[i-1][j].a)/d,y=(s[i-1][j].b+1)/d;
            if(!mp[x][y]){
                s[i][++cnt[i]]=(score){x,y,0};
            }
            mp[x][y]+=s[i-1][j].v;
        }
        for(int j=1;j<=cnt[i];j++){
            s[i][j].v=mp[s[i][j].a][s[i][j].b];
        }
    }
    for(int i=0;i<34;i++){
        for(int j=0;j<34;j++){
            cout<<"("<<i<<","<<j<<"): ";
            cout<<fixed<<setprecision(10)<<(long double)mp[i][j]/(long double)(pow(2,60))<<endl;
        }
    }
    return 0;
}