Introduction

As a rhythm game player, I often wonder what my max combo will be in my next play. This is a rather unpredictable outcome, and what I can do is to try to conclude a probability distribution of my max combo.

For those who are not familiar with rhythm games and also to make the question clearer, I state the problem in a more mathematical setting.

Consider a random bit string of length nNn\in\mathbb N, where each bit is independent and has probability Y[0,1]Y\in[0,1] of being 11. Let Pn,k(Y)P_{n,k}(Y) be the probability that the length of the longest all-11 substring of the bit string is kNk\in\mathbb N (where obviously Pn,k(Y)P_{n,k}(Y) is nonzero only when knk\le n). What is the expression of Pn,k(Y)P_{n,k}(Y)?

A more interesting problem to consider is what the probability distribution tends to be when nn\to\infty. Define the random variable κk/n\kappa\coloneqq k/n where kk is the length of the longest all-11 substring. Define a parameter yYny\coloneqq Y^n (this parameter is held constant while nn\to\infty). Define the probability distribution function of κ\kappa as f(y,κ)limn(n+1)Pn,κn ⁣(y1n).f(y,\kappa)\coloneqq\lim_{n\to\infty}\left(n+1\right)P_{n,\kappa n}\!\left(y^{\frac1n}\right).(1)\p{1} What is the expression of f(y,κ)f(y,\kappa)?

Notation

Notation for integer range: aba\ldots b denotes the integer range defined by the ends aa (inclusive) and bb (exclusive), or in other words {a,a+1,,b1}\left\{a,a+1,\ldots,b-1\right\}. It is defined to be empty if aba\ge b. The operator \ldots has a lower precedence than ++ and - but a higher precedence than \in.

The notation a..ba\,..b denotes the inclusive integer range {a,a+1,,b}\left\{a,a+1,\ldots,b\right\}. It is defined to be empty if a>ba>b.

The case for finite nn

A natural approach to find Pn,kP_{n,k} is to try to find a recurrence relation of Pn,kP_{n,k} for different nn and kk, and then use a dynamic programming (DP) algorithm to compute Pn,kP_{n,k} for any given nn and kk.

The first DP approach

For a rhythm game player, the most straightforward way of finding kk for a given bit string is to track the current combo, and update the max combo when the current combo is greater than the previous max combo.

To give the current combo a formal definition, denote each bit in the bit string as bib_i, where i0ni\in0\ldots n. Define the current combo rir_i as the length of the longest all-11 substring of the bit string ending before (exclusive) ii (so ri=0r_i=0 if bi1=0b_{i-1}=0, which is callled a combo break): rimax{r0..i|jiri:bj=1},r_i\coloneqq\max\left\{r\in0\,..i\,\middle|\,\forall j\in i-r\ldots i:b_j=1\right\}, where i0..ni\in0\,..n.

Now, use three numbers (n,k,r)(n,k,r) to define a DP state. Denote Pn,k,rP_{n,k,r} to be the probability that the max combo is kk and the final combo (rnr_n) is rr. Then, consider a transition from state (n,k,r)(n,k,r) to state (n+1,k,r)(n+1,k',r') by adding a new bit bnb_n to the bit string. There are two cases:

  • If bn=0b_n=0 (has 1Y1-Y probability), then this means a combo break, so we have r=0r'=0 and k=kk'=k.
  • If bn=1b_n=1 (has YY probability), then the combo continues, so we have r=r+1r'=r+1. The max combo needs to be updated if needed, so we have k=max(k,r)k'=\max(k,r').

However, in actual implementation of the DP algorithm, we need to reverse this transition by considering what state can lead to the current state (n,k,r)(n,k,r) (to use the bottom-up approach).

First, obviously in any possible case r0..kr\in0\,..k (currently we only consider the cases where n>k>0n>k>0). Divide all those cases into three groups:

  1. If r=0r=0, this is means a combo break, so the last bit is 00, and the previous state can have any possible final combo rr'. Therefore, it can be transitioned from any (n1,k,r)(n-1,k,r') where r0..kr'\in0\,..k. For each possible previous state, the probability of the transition to this new state is 1Y1-Y.
  2. If r1..k1r\in1\,..k-1, this means the last bit is 11, the previous final combo is r1r-1, and the previous max combo is already kk. Therefore, the previous state is (n1,k,r1)(n-1,k,r-1), and the probability of the transition is YY.
  3. If r=kr=k, this means the max combo may (or may not) have been updated. In either case, the previous final combo is r1=k1r-1=k-1.
  • If the max combo is updated, the previous max combo must be k1k-1 because it must not be less than the previous final combo k1k-1 and must be less than the new max combo kk. Therefore, the previous state is (n1,k1,k1)(n-1,k-1,k-1), and the probability of the transition is YY.
  • If the max combo is not updated, the previous max combo is the same as the new one, which is kk. Therefore, the previous state is (n1,k,k1)(n-1,k,k-1), and the probability of the transition is YY.

Therefore, we can write a recurrence relation that is valid when n>k>0n>k>0: Pn,k,r={(1Y)r=0kPn1,k,r,r=0YPn1,k,r1,r1..k1Y(Pn1,k1,k1+Pn1,k,k1),r=k.P_{n,k,r}=\begin{cases} \left(1-Y\right)\sum_{r'=0}^kP_{n-1,k,r'},&r=0\\ YP_{n-1,k,r-1},&r\in1\,..k-1\\ Y\left(P_{n-1,k-1,k-1}+P_{n-1,k,k-1}\right),&r=k. \end{cases}

However, there are also other cases (mostly edge cases) because we assumed n>k>0n>k>0. Actually, in the meaningfulness condition nkr0n\ge k\ge r\ge0 (necessary condition for Pn,k,rP_{n,k,r} to be nonzero), there are three inequality that can be altered between a less-than sign or an equal sign, so there are totally 23=82^3=8 cases. Considering all those cases (omitted in this article because of the triviality), we can write a recurrence relation that is valid for all n,k,rn,k,r, covering all the edge cases: Pn,k,r={1,n=k=r=0,YPn1,n1,n1,n=k=r>0,0,n=k>r>0,0,n=k>r=0,Y(Pn1,k1,k1+Pn1,k,k1),n>k=r>0,YPn1,k,r1,n>k>r>0,(1Y)r=0kPn1,k,r,n>k>r=0,(1Y)Pn1,0,0,n>k=r=0.P_{n,k,r}=\begin{cases} 1,& n=k=r=0,\\ YP_{n-1,n-1,n-1},& n=k=r>0,\\ 0,& n=k>r>0,\\ 0,& n=k>r=0,\\ Y\left(P_{n-1,k-1,k-1}+P_{n-1,k,k-1}\right),& n>k=r>0,\\ YP_{n-1,k,r-1},& n>k>r>0,\\ \left(1-Y\right)\sum_{r'=0}^kP_{n-1,k,r'},& n>k>r=0,\\ \left(1-Y\right)P_{n-1,0,0},& n>k=r=0. \end{cases}(2)\p{2}

Note that the probabilities related to note count nn only depend on those related to note count n1n-1 and that the probabilities related to max combo kk and final combo rr only depend on those related to either less max combo than kk or less final combo than rr (except for the case n>k>r=0n>k>r=0, which can be specially treated before the current iteration of kk actually starts), so for the bottom-up DP we can reduce the spatial complexity from O ⁣(n3)O\!\left(n^3\right) to O ⁣(n2)O\!\left(n^2\right) by reducing the 3-dimensional DP to a 2-dimensional one. What needs to be taken care of is that the DP table needs to be updated from larger kk and rr to smaller kk and rr instead of the other way so that the numbers in the last iteration in nn are left untouched while we need to use them in the current iteration.

After the final iteration in nn finishes, we need to sum over the index rr to get the final answer: Pn,k=r=0kPn,k,r.P_{n,k}=\sum_{r=0}^kP_{n,k,r}.

Writing the code for the DP algorithm is then straightforward. Here is an implementation in Ruby. In the code, dp[k][r] means Pn,k,rP_{n,k,r} in the nnth iteration.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
## Returns an array of size m+1,
## with the k-th element being the probability P_{m,k}.
def combo m
	(1..m).each_with_object [[1]] do |n, dp|
		dp[n] = [0]*n + [Y * dp[n-1][n-1]] # n = k > 0
		(n-1).downto 1 do |k| # n > k > 0
			dpk0 = (1-Y) * dp[k].sum
			dp[k][k] = Y * (dp[k-1][k-1] + dp[k][k-1])        # n > k = r > 0
			(k-1).downto(1) { |r| dp[k][r] = Y * dp[k][r-1] } # n > k > r > 0
			dp[k][0] = dpk0                                   # n > k > r = 0
		end
		dp[0][0] *= 1-Y # n > k = r = 0
	end.map &:sum
end

Because of the three nested loops, the time complexity of the DP algorithm is O ⁣(n3)O\!\left(n^3\right).

The second DP approach

Here is an alternative way to use DP to solve the problem. Instead of building a DP table with the k,rk,r indices, we can build a DP table with the n,kn,k indices.

First, we need to rewrite the recurrence relation of Pn,kP_{n,k} instead of that of Pn,k,rP_{n,k,r}. We then need to try to express Pn,k,rP_{n,k,r} in terms of Pn,kP_{n,k} terms. The easiest part is the case where nk=r=0n\ge k=r=0. By recursively applying Equation 2 to Pn,0,0P_{n,0,0}, we have Pn,0,0=(1Y)Pn1,0,0=(1Y)2Pn2,0,0==(1Y)nP0,0,0.\begin{align*} P_{n,0,0}&=\left(1-Y\right)P_{n-1,0,0}\\ &=\left(1-Y\right)^2P_{n-2,0,0}\\ &=\cdots\\ &=\left(1-Y\right)^nP_{0,0,0}. \end{align*} Because P0,0,0=1P_{0,0,0}=1, we have Pn,0,0=(1Y)n.P_{n,0,0}=\left(1-Y\right)^n.(3)\p{3}


For n>k>r>0n>k>r>0, we can recursively apply Equation 2 to get Pn,k,r=YPn1,k,r1=Y2Pn2,k,r2=\begin{align*} P_{n,k,r}&=YP_{n-1,k,r-1}\\ &=Y^2P_{n-2,k,r-2}\\ &=\cdots \end{align*} This will finally either decend the note count to kk or decend the final combo to 00, determined by which comes first.

  • If nrkn-r\le k, we will decend to the term Pk,k,r(nk)P_{k,k,r-(n-k)}, which must be zero according to the case n=k>r=0n=k>r=0 and the case n=k>r>0n=k>r>0 in Equation 2, so Pn,k,r=0P_{n,k,r}=0.
  • If nr>kn-r>k, then we will decend to the term Pnr,k,0P_{n-r,k,0}, which is equal to (1Y)Pnr1,k\left(1-Y\right)P_{n-r-1,k} according to the case n>k>r=0n>k>r=0 in Equation 2.

Therefore, for n>k>r>0n>k>r>0, we have Pn,k,r={0,nrk,Yr(1Y)Pnr1,k,nr>k.P_{n,k,r}=\begin{cases} 0,&n-r\le k,\\ Y^r\left(1-Y\right)P_{n-r-1,k},&n-r>k. \end{cases}(4)\p{4}


For the case n>k=r>0n>k=r>0, we can also recursively apply Equation 2 to get Pn,k,k=Y(Pn1,k1,k1+Pn1,k,k1)=Y(Y(Pn2,k2,k2+Pn2,k1,k2)+Pn1,k,k1)==Y(Y(Y(Pnk,0,0+Pnk,1,0)+)+Pn1,k,k1)=YkPnk,0,0+j=1kYjPnj,kj+1,kj.\begin{align*} P_{n,k,k}&=Y\left(P_{n-1,k-1,k-1}+P_{n-1,k,k-1}\right)\\ &=Y\left(Y\left(P_{n-2,k-2,k-2}+P_{n-2,k-1,k-2}\right)+P_{n-1,k,k-1}\right)\\ &=\cdots\\ &=Y\left(Y\left(\cdots Y\left(P_{n-k,0,0}+P_{n-k,1,0}\right)+\cdots\right)+P_{n-1,k,k-1}\right)\\ &=Y^kP_{n-k,0,0}+\sum_{j=1}^kY^jP_{n-j,k-j+1,k-j}. \end{align*} We can then substitute Equation 3 and 4 into the above equation. The substitution of Equation 3 can be done without a problem, but the substitution of Equation 4 requires some care because of the different cases.

  • If nk>kn-k>k, then only the case nr>kn-r>k in Equation 4 will be involved in the summation.
  • If nkkn-k\le k, then both cases in Equation 4 will be involved in the summation. To be specific, for j1..2kn+1j\in1\,..\,2k-n+1, we need the case nrkn-r\le k in Equation 4 (where the summed terms are just zero and can be omitted); for other terms in the summation, we need the other case.

Considering both cases, we may realize that we can just modify the range of the summation to jmax(1,2kn+1)..kj\in\max(1,2k-n+1)\,..k and adopt the case nr>kn-r>k in Equation 4 for all terms in the summation. Therefore, we have Pn,k,k=Yk(1Y)nk+j=max(1,2kn+1)kYjYkj(1Y)Pnj(kj)1,kj+1=Yk(1Y)nk+Yk(1Y)k=1min(k,nk1)Pnk1,k,\begin{align*} P_{n,k,k}&=Y^k\left(1-Y\right)^{n-k}+\sum_{j=\max(1,2k-n+1)}^{k}Y^jY^{k-j}\left(1-Y\right)P_{n-j-(k-j)-1,k-j+1}\\ &=Y^k\left(1-Y\right)^{n-k}+Y^k\left(1-Y\right)\sum_{k'=1}^{\min(k,n-k-1)}P_{n-k-1,k'}, \end{align*} where in the last line we changed the summation index to kkj+1k'\coloneqq k-j+1 to simplify it. Because Pnk1,0=Pnk1,0,0=(1Y)nk1P_{n-k-1,0}=P_{n-k-1,0,0}=\left(1-Y\right)^{n-k-1} according to Equation 3, we can combine the two terms into one summation to get the final result for n>k=r>0n>k=r>0: Pn,k,k=Yk(1Y)k=0min(k,nk1)Pnk1,k.P_{n,k,k}=Y^k\left(1-Y\right)\sum_{k'=0}^{\min(k,n-k-1)}P_{n-k-1,k'}.(5)\p{5} Noticing the obvious fact that k=0nPn,k=1\sum_{k=0}^nP_{n,k}=1, the above equation can be simplified, when knk1k\ge n-k-1, to Pn,k,k=Yk(1Y).P_{n,k,k}=Y^k\left(1-Y\right).(6)\p{6} This simplification is not specially useful, but it can be used to simplify the calculation in the program.


Then, for n>k>0n>k>0, express Pn,kP_{n,k} in terms of Pn,k,rP_{n,k,r} by summing over rr, and substitute previous results: Pn,k=r=0kPn,k,r=Pn,k,0+Pn,k,k+r=1k1Pn,k,r=(1Y)Pn1,k+Yk(1Y)k=0min(k,nk1)Pnk1,k= +r=1min(k1,nk1)Yr(1Y)Pnr1,k=(1Y)(Ykk=0min(k,nk1)Pnk1,k+r=0min(k1,nk1)YrPnr1,k)\begin{align*} P_{n,k}&=\sum_{r=0}^kP_{n,k,r}\\ &=P_{n,k,0}+P_{n,k,k}+\sum_{r=1}^{k-1}P_{n,k,r}\\ &=\left(1-Y\right)P_{n-1,k}+Y^k\left(1-Y\right)\sum_{k'=0}^{\min(k,n-k-1)}P_{n-k-1,k'}\\ &\phantom{=~}{}+\sum_{r=1}^{\min(k-1,n-k-1)}Y^r\left(1-Y\right)P_{n-r-1,k}\\ &=\left(1-Y\right)\left( Y^k\sum_{k'=0}^{\min(k,n-k-1)}P_{n-k-1,k'} +\sum_{r=0}^{\min(k-1,n-k-1)}Y^rP_{n-r-1,k} \right) \end{align*} where in the last term rr is summed to min(k1,nk1)\min(k-1,n-k-1) instead of k1k-1 because of the different cases in Equation 4.

Finally, consider the edge cases where n=k0n=k\ge0 and nk=0n\ge k=0 (trivial), we have the complete resursive relation for Pn,kP_{n,k}: Pn,k={Yn,n=k0,(1Y)n,nk=0,(1Y)(Ykk=0min(k,nk1)Pnk1,k+r=0min(k1,nk1)YrPnr1,k),n>k>0.P_{n,k}=\begin{cases} Y^n,&n=k\ge0,\\ \left(1-Y\right)^n,&n\ge k=0,\\ \displaystyle{\begin{split} \left(1-Y\right)&\,\left( Y^k\sum_{k'=0}^{\min(k,n-k-1)}P_{n-k-1,k'} \right.\\&\left. +\sum_{r=0}^{\min(k-1,n-k-1)}Y^rP_{n-r-1,k} \right), \end{split}}&n>k>0. \end{cases}(7)\p{7}

Then, we can write the program to calculate Pn,kP_{n,k}:

1
2
3
4
5
6
7
8
9
10
## Returns an array of size m+1,
## with the k-th element being the probability P_{m,k}.
def combo m
	(1..m).each_with_object [[1]] do |n, dp|
		dp[n] = (1..n-1).each_with_object [(1-Y)**n] do |k, dpn|
			dpn[k] = (1-Y) * (Y**k * (0..[k, n-k-1].min).sum { dp[n-k-1][_1] } + (0..[k-1, n-k-1].min).sum { Y**_1 * dp[n-_1-1][k] })
		end
		dp[n][n] = Y**n
	end.last
end

This algorithm has the same (asymptotic) space and time complexity as the previous one.

Polynomial coefficients

We have wrote programmes to calculate probabilities Pn,k(Y)P_{n,k}(Y) based on given YY, which we assumed to be a float number. However, float numbers have limited precision, and the calculation may be inaccurate. Actually, the calculation can be done symbolically.

The probability Pn,kP_{n,k} is a polynomial of degree (at most) nn in YY, and the coefficients of the polynomial are integers. This can be easily proven by using mathematical induction and utilizing Equation 7. Therefore, we can calculate the coefficients of the polynomial Pn,k(Y)P_{n,k}(Y) instead of calculate the value directly so that we get a symbolic but accurate result.

Both the two DP algorithms above can be modified to calculate the coefficients of the polynomial. Actually, we can define Y to be a polynomial object that can do arithmetic operations with other polynomials or numbers, and then the programmes can run without any modification. Here, I will modify the second DP algorithm to calculate the coefficients of the polynomial.

We can also utilize Equation 6 to simplify the calculation. Considering the edge cases involved in min(k,nk1)\min(k,n-k-1) and min(k1,nk1)\min(k-1,n-k-1), there are three cases we need to consider:

  1. Case k>nk1k>n-k-1: Equation 6 can be applied, and rr is summed to nk1n-k-1.
  2. Case k=nk1k=n-k-1 (can only happen when nn is odd): Equation 6 can be applied, and rr is summed to k1k-1.
  3. Case k<nk1k<n-k-1: Equation 6 cannot be applied, and rr is summed to k1k-1.

Then, use arrays to store the coefficients of the polynomial Pn,k(Y)P_{n,k}(Y), and we can write the program to calculate the coefficients:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
## Returns a nested array of size m+1 times m+1,
## with the j-th element of the k-th element being the coefficient of Y^j in P_{m,k}(Y).
def combo_pc m
	(1..m).each_with_object [[[1]]] do |n, dp|
		dp[n] = Array.new(n+1) { Array.new n+1, 0 }

		# dp[n][0] = (1-Y)**n
		0.upto(n-1) { dp[n][0][_1] = dp[n-1][0][_1] } # will be multiplied by 1-Y later

		1.upto n/2-1 do |k|
			# dp[n][k] = (1-Y) * (Y**k * (0..k).sum { |j| dp[n-k-1][j] } + (0..k-1).sum { |r| Y**r * dp[n-r-1][k] })
			0.upto(k) { |j| 0.upto(n-k-1) { dp[n][k][_1+k] += dp[n-k-1][j][_1] } }
			0.upto(k-1) { |r| 0.upto(n-r-1) { dp[n][k][_1+r] += dp[n-r-1][k][_1] } }
		end

		if n % 2 == 1
			k = n/2
			# dp[n][k] = (1-Y) * (Y**k + (0..k-1).sum { |r| Y**r * dp[n-r-1][k] })
			dp[n][k][k] = 1
			0.upto(k-1) { |r| 0.upto(n-r-1) { dp[n][k][_1+r] += dp[n-r-1][k][_1] } }
		end

		((n+1)/2).upto n-1 do |k|
			# dp[n][k] = (1-Y) * (Y**k + (0..n-k-1).sum { |r| Y**r * dp[n-r-1][k] })
			dp[n][k][k] = 1
			0.upto(n-k-1) { |r| 0.upto(n-r-1) { dp[n][k][_1+r] += dp[n-r-1][k][_1] } }
		end

		0.upto(n-1) { |k| n.downto(1) { dp[n][k][_1] -= dp[n][k][_1-1] } } # multiply by 1-Y
		
		# dp[n][n] = Y**n
		dp[n][n][n] = 1
	end.last
end

Here I list first few polynomials Pn,k(Y)P_{n,k}(Y) calculated by the above program: k=0123n=0111YY212Y+Y22YY2Y2313Y+3Y2Y33Y5Y2+2Y32Y22Y3Y3\begin{array}{r|llllc} & k=0 & 1 & 2 & 3 & \cdots\\ \hline n=0 & 1\\ 1 & 1-Y & Y\\ 2 & 1-2Y+Y^2 & 2Y-Y^2 & Y^2\\ 3 & 1-3Y+3Y^2-Y^3 & 3Y-5Y^2+2Y^3 & 2Y^2-2Y^3 & Y^3\\ \vdots \end{array}

When evaluating the polynomials for large nn, the result is inaccurate for YY that is not close to 00 because of the limited precision of floating numbers. If YY is closer to 11, we can first find the coefficients of Pn,k(1X)P_{n,k}(1-X) and then substitute X1YX\coloneqq1-Y.

Plots of the probability distributions

Here are some plots of the probability distribution of max combo kk when n=50n=50:

Probability distribution of  when  for different

The plots are intuitive as they show that one has higher probability to get a higher max combo when they have a higher success rate.

There is a suspicious jump in Pn,k(Y)P_{n,k}(Y) near k=n/2k=n/2 when YY is close to 11. We can look at it closer:

Probability distribution of  when  for different

In the zoomed-in plot, we can also see a jump in first derivative (w.r.t. kk) of Pn,k(Y)P_{n,k}(Y) near k=n/3k=n/3. Actually, the jumps can be modeled in later sections when we talk about the case when nn\to\infty.

The case when nn\to\infty

A natural approach is to try substituting Equation 7 into Equation 1 to get a function w.r.t. the unknown function f(y,κ)f(y,\kappa). First, we can easily write the case when y=0y=0 because it means zero success rate, and the only possible max combo is zero: f(y=0,κ)=δ(κ).f(y=0,\kappa)=\delta(\kappa).(8)\p{8} Similarly, we can easily write the case when y=1y=1: f(y=1,κ)=δ(κ1).f(y=1,\kappa)=\delta(\kappa-1).(9)\p{9}

From now on, we only consider the case when 0<y<10<y<1. First, for the case κ=0\kappa=0, according to Equation 7, f(y,κ=0)=limn(n+1)(1y1n)n={0,0<y1,,y=0.\begin{align*} f(y,\kappa=0)&=\lim_{n\to\infty}\left(n+1\right)\left(1-y^{\frac1n}\right)^n\\ &=\begin{cases}0,&0<y\le1,\\\infty,&y=0.\end{cases} \end{align*} The \infty means that there is a Dirac δ\delta function (shown in Equation 8).

Then, for the case κ=1\kappa=1, according to Equation 7, f(y,κ=1)=limn(n+1)y=.f(y,\kappa=1)=\lim_{n\to\infty}\left(n+1\right)y=\infty. The \infty means that there is a Dirac δ\delta function. Actually, it is easy to see that there must be a yδ(κ1)y\delta(\kappa-1) term in the expression of f(y,κ)f(y,\kappa) because the probability of getting a max combo (κ=1\kappa=1) is yy.

Define h(y,κ)f(y,κ)yδ(κ1),h(y,\kappa)\coloneqq f(y,\kappa)-y\delta(\kappa-1),(10)\p{10} and then we can get rid of the infinity here.

From now on, we only consider the case when 0<y<10<y<1 and 0<κ<10<\kappa<1. According to Equation 7, = f ⁣(y(0,1),κ(0,1))=limn(n+1)(1y1n)(yκk=0min(κn,nκn1)Pnκn1,k ⁣(y1n)=limn(n+1)(1y1n)+r=0min(κn1,nκn1)yrnPnr1,κn ⁣(y1n))=limnn(1y1n)limn(yκt=0,Δt=1nmin(κ,1κ)P(1κ)n,tn ⁣(y1n)+t=0,Δt=1nmin(κ,1κ)ytP(1t)n,κn ⁣(y1n))=lnylimn(yκt=0,Δt=1nmin(κ,1κ)1(1κ)nf ⁣(y1κ,t1κ)=lnylimn+t=0,Δt=1nmin(κ,1κ)yt1(1t)nf ⁣(y1t,κ1t))=lnylimnt=0,Δt=1nmin(κ,1κ)(yκ1κf ⁣(y1κ,t1κ)+yt1tf ⁣(y1t,κ1t))Δt=lnyt=0min(κ,1κ)(yκ1κf ⁣(y1κ,t1κ)+yt1tf ⁣(y1t,κ1t))dt.\begin{align*} &\phantom{=~}f\!\left(y\in\left(0,1\right),\kappa\in\left(0,1\right)\right)\\ &=\lim_{n\to\infty}\left(n+1\right)\left(1-y^{\frac1n}\right)\left( y^\kappa\sum_{k'=0}^{\min(\kappa n,n-\kappa n-1)}P_{n-\kappa n-1,k'}\!\left(y^{\frac1n}\right) \right.\\&\phantom{=\lim_{n\to\infty}\left(n+1\right)\left(1-y^{\frac1n}\right)}\left. +\sum_{r=0}^{\min(\kappa n-1,n-\kappa n-1)}y^{\frac rn}P_{n-r-1,\kappa n}\!\left(y^{\frac1n}\right) \right)\\ &=\lim_{n\to\infty}n\left(1-y^{\frac1n}\right)\cdot\lim_{n\to\infty}\left( y^\kappa\sum_{t=0,\Delta t=\frac1n}^{\min(\kappa,1-\kappa)}P_{(1-\kappa)n,tn}\!\left(y^{\frac1n}\right) +\sum_{t=0,\Delta t=\frac1n}^{\min(\kappa,1-\kappa)}y^tP_{(1-t)n,\kappa n}\!\left(y^{\frac1n}\right) \right)\\ &=-\ln y\lim_{n\to\infty}\left( y^\kappa\sum_{t=0,\Delta t=\frac1n}^{\min(\kappa,1-\kappa)} \frac1{\left(1-\kappa\right)n}f\!\left(y^{1-\kappa},\frac t{1-\kappa}\right) \right.\\&\phantom{=-\ln y\lim_{n\to\infty}}\left. +\sum_{t=0,\Delta t=\frac1n}^{\min(\kappa,1-\kappa)}y^t \frac1{\left(1-t\right)n}f\!\left(y^{1-t},\frac{\kappa}{1-t}\right) \right)\\ &=-\ln y\lim_{n\to\infty}\sum_{t=0,\Delta t=\frac 1n}^{\min(\kappa,1-\kappa)}\left( \frac{y^\kappa}{1-\kappa}f\!\left(y^{1-\kappa},\frac t{1-\kappa}\right) +\frac{y^t}{1-t}f\!\left(y^{1-t},\frac\kappa{1-t}\right) \right)\Delta t\\ &=-\ln y\int_{t=0}^{\min(\kappa,1-\kappa)}\left( \frac{y^\kappa}{1-\kappa}f\!\left(y^{1-\kappa},\frac t{1-\kappa}\right) +\frac{y^t}{1-t}f\!\left(y^{1-t},\frac\kappa{1-t}\right) \right)\mathrm dt. \end{align*} Add back the delta function at κ=1\kappa=1, and we have the integral equation f ⁣(y(0,1),κ)=lnyt=0min(κ,1κ)(yκ1κf ⁣(y1κ,t1κ)+yt1tf ⁣(y1t,κ1t))dt+yδ(κ1).\begin{split} f\!\left(y\in\left(0,1\right),\kappa\right)=-\ln y\int_{t=0}^{\min(\kappa,1-\kappa)}&\,\left( \frac{y^\kappa}{1-\kappa}f\!\left(y^{1-\kappa},\frac t{1-\kappa}\right) \right.\\&\left. +\frac{y^t}{1-t}f\!\left(y^{1-t},\frac\kappa{1-t}\right) \right)\mathrm dt+y\delta(\kappa-1). \end{split}

There are two terms in the integral. Substitute ut1κu\coloneqq\frac t{1-\kappa} in the first term, and we have t=0min(κ,1κ)yκ1κf ⁣(y1κ,t1κ)dt=0min(κ1κ,1)yκf ⁣(y1κ,u)du=0min(κ1κ,1)(yκh ⁣(y1κ,u)+yδ(u1))du.\begin{align*} \int_{t=0}^{\min\left(\kappa,1-\kappa\right)}\frac{y^\kappa}{1-\kappa}f\!\left(y^{1-\kappa},\frac t{1-\kappa}\right)\mathrm dt &=\int_0^{\min(\frac\kappa{1-\kappa},1)}y^\kappa f\!\left(y^{1-\kappa},u\right)\mathrm du\\ &=\int_0^{\min(\frac\kappa{1-\kappa},1)}\left(y^\kappa h\!\left(y^{1-\kappa},u\right)+y\delta(u-1)\right)\mathrm du. \end{align*} Substitute vκ1tv\coloneqq\frac\kappa{1-t} in the second term, and we have t=0min(κ,1κ)yt1tf ⁣(y1t,κ1t)dt=κmin(κ1κ,1)y1κvf ⁣(yκv,v)dvv=κmin(κ1κ,1)(y1κvh ⁣(yκv,v)+yδ(v1))dvv.\begin{align*} \int_{t=0}^{\min(\kappa,1-\kappa)}\frac{y^t}{1-t}f\!\left(y^{1-t},\frac\kappa{1-t}\right)\mathrm dt &=\int_\kappa^{\min\left(\frac\kappa{1-\kappa},1\right)}y^{1-\frac\kappa v}f\!\left(y^{\frac\kappa v},v\right)\frac{\mathrm dv}v\\ &=\int_\kappa^{\min\left(\frac\kappa{1-\kappa},1\right)}\left(y^{1-\frac\kappa v}h\!\left(y^{\frac\kappa v},v\right)+y\delta(v-1)\right)\frac{\mathrm dv}v. \end{align*}

Further, let (we only consider y(0,1)y\in\left(0,1\right) from now on) g(y,κ)h(y,κ)y,g(y,\kappa)\coloneqq\frac{h(y,\kappa)}{y},(11)\p{11} then the integral equation becomes g(y,κ)=lny(0min(κ1κ,1)(g ⁣(y1κ,u)+δ(u1))du+κmin(κ1κ,1)(g ⁣(yκv,v)+δ(v1))dvv).\begin{split} g(y,\kappa)=-\ln y&\,\left( \int_0^{\min\left(\frac\kappa{1-\kappa},1\right)}\left(g\!\left(y^{1-\kappa},u\right)+\delta(u-1)\right)\mathrm du \right.\\&\left. +\int_\kappa^{\min\left(\frac\kappa{1-\kappa},1\right)}\left(g\!\left(y^{\frac\kappa v},v\right)+\delta(v-1)\right)\frac{\mathrm dv}v \right). \end{split}(12)\p{12}

There is another integral equation for gg. Because 01f ⁣(y,κ)dκ=1\int_0^1f\!\left(y,\kappa\right)\mathrm d\kappa=1, we have 01g ⁣(y,κ)dκ=1y1.\int_0^1g\!\left(y,\kappa\right)\mathrm d\kappa=\frac1y-1.(13)\p{13}

Equation 12 and 13 are the equations that we are going to utilize to get the expression for g(y,κ)g(y,\kappa).

The case κ(12,1)\kappa\in\left(\frac12,1\right)

In this case, we have min ⁣(κ1κ,1)=1,\min\!\left(\frac\kappa{1-\kappa},1\right)=1, so the Dirac delta functions in Equation 12 should be considered. In this case, it simplifies to g1(y,κ)g ⁣(y,κ(12,1))=lny(yκ1+κ1g ⁣(yκv,v)dvv+1),g_1(y,\kappa)\coloneqq g\!\left(y,\kappa\in\left(\frac12,1\right)\right)= -\ln y\left(y^{\kappa-1}+\int_\kappa^1g\!\left(y^{\frac\kappa v},v\right)\frac{\mathrm dv}v+1\right),(14)\p{14} where Equation 13 is utilized when finding the first term.

We can try to solve Equation 14 by using Adomian decomposition method (ADM). Suppose g1g_1 can be written in a series g1=g1(0)+g1(1)+,g_1=g_1^{(0)}+g_1^{(1)}+\cdots, and substitute it into Equation 14, and we have g1(0)(y,κ)+=lny(yκ1+1+κ1(g(0) ⁣(yκv,v)+)dvv).g_1^{(0)}(y,\kappa)+\cdots =-\ln y\left(y^{\kappa-1}+1+\int_\kappa^1\left( g^{(0)}\!\left(y^{\frac\kappa v},v\right)+\cdots \right)\frac{\mathrm dv}v\right). Assume we may interchange integration and summation (which is OK here because we can verify the solution after we find it using ADM). Then, = g1(0)(y,κ)+g1(1)(y,κ)+=lny(yκ1+1)lnyκ1g(0) ⁣(yκv,v)dvv.\begin{align*} &\phantom{=~}g_1^{(0)}(y,\kappa)+g_1^{(1)}(y,\kappa)+\cdots\\ &=-\ln y\left(y^{\kappa-1}+1\right) -\ln y\int_\kappa^1g^{(0)}\!\left(y^{\frac\kappa v},v\right)\frac{\mathrm dv}v-\cdots. \end{align*} If we let g1(0)(y,κ)lny(yκ1+1),g1(i+1)(y,κ)lnyκ1g(i) ⁣(yκv,v)dvv,iN,\begin{split} g_1^{(0)}(y,\kappa)&\coloneqq-\ln y\left(y^{\kappa-1}+1\right),\\ g_1^{(i+1)}(y,\kappa)&\coloneqq-\ln y\int_\kappa^1g^{(i)}\!\left(y^{\frac\kappa v},v\right)\frac{\mathrm dv}v,\quad i\in\mathbb N, \end{split}(15)\p{15} then we can equate each term in the two series. If the sum g1=i=0g1(i)g_1=\sum_{i=0}^\infty g_1^{(i)} converges, then this is a guess of the solution to Equation 14, which we can verify whether it is correct or not.

Using Equation 15, we can find first few terms in the series by directly integrating. The first few terms are g1(0)(y,κ)=lny(yκ1+1),g1(1)(y,κ)=lny(yκ11+lnyκ1),g1(2)(y,κ)=lny(yκ11lnyκ1+12(lnyκ1)2),g1(3)(y,κ)=lny(yκ11lnyκ112(lnyκ1)2+16(lnyκ1)3),\begin{split} g_1^{(0)}(y,\kappa)&=-\ln y\left(y^{\kappa-1}+1\right),\\ g_1^{(1)}(y,\kappa)&=-\ln y\left(y^{\kappa-1}-1+\ln y^{\kappa-1}\right),\\ g_1^{(2)}(y,\kappa)&=-\ln y\left(y^{\kappa-1}-1-\ln y^{\kappa-1}+\frac12\left(\ln y^{\kappa-1}\right)^2\right),\\ g_1^{(3)}(y,\kappa)&=-\ln y\left(y^{\kappa-1}-1-\ln y^{\kappa-1}-\frac12\left(\ln y^{\kappa-1}\right)^2+\frac16\left(\ln y^{\kappa-1}\right)^3\right),\\ \vdots& \end{split} We may then guess that the terms have general formula g1(i)(y,κ)=lny(yκ1+1i!(lnyκ1)ij=0i11j!(lnyκ1)j).g_1^{(i)}(y,\kappa)=-\ln y\left(y^{\kappa-1}+\frac1{i!}\left(\ln y^{\kappa-1}\right)^i -\sum_{j=0}^{i-1}\frac1{j!}\left(\ln y^{\kappa-1}\right)^j\right). Sum up the terms, and we have g1(y,κ)=i=0g1(i)(y,κ)=limqi=0qlny(yκ1+1i!(lnyκ1)ij=0i11j!(lnyκ1)j)=lny(explnyκ1+limq((q+1)yκ1j=0qi=j+1q1j!(lnyκ1)j))=lny(yκ1+limq((q+1)yκ1j=0qqjj!(lnyκ1)j))=lny(yκ1+limq(qyκ1qj=0q1j!(lnyκ1)j)=lnyjq+yκ1+lnyκ1explnyκ1)=lny(2+lnyκ1)yκ1.\begin{align*} g_1(y,\kappa)&=\sum_{i=0}^\infty g_1^{(i)}(y,\kappa)\\ &=\lim_{q\to\infty}\sum_{i=0}^q-\ln y\left( y^{\kappa-1}+\frac1{i!}\left(\ln y^{\kappa-1}\right)^i -\sum_{j=0}^{i-1}\frac1{j!}\left(\ln y^{\kappa-1}\right)^j \right)\\ &=-\ln y\left(\exp\ln y^{\kappa-1}+\lim_{q\to\infty}\left( \left(q+1\right)y^{\kappa-1} -\sum_{j=0}^q\sum_{i=j+1}^q\frac1{j!}\left(\ln y^{\kappa-1}\right)^j \right)\right)\\ &=-\ln y\left(y^{\kappa-1}+\lim_{q\to\infty}\left( \left(q+1\right)y^{\kappa-1} -\sum_{j=0}^q\frac{q-j}{j!}\left(\ln y^{\kappa-1}\right)^j \right)\right)\\ &=-\ln y\left( y^{\kappa-1}+\lim_{q\to\infty}\left( qy^{\kappa-1}-q\sum_{j=0}^q\frac1{j!}\left(\ln y^{\kappa-1}\right)^j \right) \right.\\&\phantom{=-\ln y}\left.\vphantom{\sum_j^q} +y^{\kappa-1} +\ln y^{\kappa-1}\exp\ln y^{\kappa-1} \right)\\ &=-\ln y\left(2+\ln y^{\kappa-1}\right)y^{\kappa-1}. \end{align*}

Therefore, we have the final guess of solution g1(y,κ)=lny(2+lnyκ1)yκ1.g_1(y,\kappa)=-\ln y\left(2+\ln y^{\kappa-1}\right)y^{\kappa-1}.(16)\p{16} We can substitute it into Equation 14 to verify that it is indeed the solution.

The case κ(13,12)\kappa\in\left(\frac13,\frac12\right)

In this case, we have min ⁣(κ1κ,1)=κ1κ(12,1).\min\!\left(\frac\kappa{1-\kappa},1\right)=\frac\kappa{1-\kappa}\in\left(\frac12,1\right). We can then use the same method as in the previous case to find the solution.

First, by Equation 14, g2(y,κ)g ⁣(y,κ(13,12))=lny(0κ1κg ⁣(y1κ,u)du+κκ1κg ⁣(yκv,v)dvv)=lny(01g ⁣(y1κ,u)duκ1κ1g1 ⁣(y1κ,u)du=lny+κ12g2 ⁣(yκv,v)dvv+12κ1κg1 ⁣(yκv,v)dvv).\begin{align*} g_2(y,\kappa)&\coloneqq g\!\left(y,\kappa\in\left(\frac13,\frac12\right)\right)\\ &=-\ln y\left( \int_0^{\frac\kappa{1-\kappa}}g\!\left(y^{1-\kappa},u\right)\mathrm du +\int_\kappa^{\frac\kappa{1-\kappa}}g\!\left(y^{\frac\kappa v},v\right)\frac{\mathrm dv}v \right)\\ &=-\ln y\left( \int_0^1g\!\left(y^{1-\kappa},u\right)\mathrm du -\int_{\frac\kappa{1-\kappa}}^1g_1\!\left(y^{1-\kappa},u\right)\mathrm du \right.\\&\phantom{=-\ln y}\left. +\int_\kappa^{\frac12}g_2\!\left(y^{\frac\kappa v},v\right)\frac{\mathrm dv}v +\int_{\frac12}^{\frac\kappa{1-\kappa}}g_1\!\left(y^{\frac\kappa v},v\right)\frac{\mathrm dv}v \right). \end{align*} Substitute Equation 13 and 16 into the above equation, and we have g2(y,κ)=lny(yκ1+yκ(1+lnyκ)2y2κ1(1+lny2κ1)κ12=lny+κ12g2 ⁣(yκv,v)dvv).\begin{split} g_2(y,\kappa)&=-\ln y\left( y^{\kappa-1} +y^{-\kappa}\left(1+\ln y^{-\kappa}\right) -2y^{2\kappa-1}\left(1+\ln y^{2\kappa-1}\right) \vphantom{\int_\kappa^{\frac12}}\right.\\&\phantom{=-\ln y}\left. +\int_\kappa^{\frac12}g_2\!\left(y^{\frac\kappa v},v\right)\frac{\mathrm dv}v \right). \end{split}(17)\p{17}

Equation 17 can again be solved by ADM though the calculation is much more complicated than the previous case. We may guess g2=i=0g2(i)g_2=\sum_{i=0}^\infty g_2^{(i)} is the solution if the series converges, where g2(0)(y,κ)lny(yκ1+yκ(1+lnyκ)2y2κ1(1+lny2κ1)),g1(i+1)(y,κ)lnyκ12g(i) ⁣(yκv,v)dvv,iN.\begin{split} g_2^{(0)}(y,\kappa)&\coloneqq-\ln y\left( y^{\kappa-1} +y^{-\kappa}\left(1+\ln y^{-\kappa}\right) -2y^{2\kappa-1}\left(1+\ln y^{2\kappa-1}\right) \right),\\ g_1^{(i+1)}(y,\kappa)&\coloneqq-\ln y\int_\kappa^{\frac12}g^{(i)}\!\left(y^{\frac\kappa v},v\right)\frac{\mathrm dv}v, \quad i\in\mathbb N. \end{split} The first few terms go too long to be written here before one may find the pattern, so they are omitted here. If you want to see them, use a mathematical software to help you, and you should be able to find the pattern after calculating first six (or so) terms. After looking at first few terms, the guessed general term is g2(i)=lny(yκ1+2y2κ1(i1lny2κ1)2j=0i1ij1j!(lny2κ1)jyκj=0i11j!(lny2κ1)j+1i!yκ(1+lnyκ)(lny2κ1)i).\begin{align*} g_2^{(i)}=-\ln y&\,\left( y^{\kappa-1}+2y^{2\kappa-1}\left(i-1-\ln y^{2\kappa-1}\right) -2\sum_{j=0}^{i-1}\frac{i-j-1}{j!}\left(\ln y^{2\kappa-1}\right)^j \right.\\&\left. {}-y^{-\kappa}\sum_{j=0}^{i-1}\frac1{j!}\left(\ln y^{2\kappa-1}\right)^j +\frac1{i!}y^{-\kappa}\left(1+\ln y^{-\kappa}\right)\left(\ln y^{2\kappa-1}\right)^i \right). \end{align*} Then we can sum it to get a guess of g2g_2.

After some tedious calculation, we have g2(y,κ)=lny((2+lnyκ1)yκ1(2+4lny2κ1+(lny2κ1)2)y2κ1).g_2(y,\kappa)=-\ln y\left( \left(2+\ln y^{\kappa-1}\right)y^{\kappa-1} -\left(2+4\ln y^{2\kappa-1}+\left(\ln y^{2\kappa-1}\right)^2\right)y^{2\kappa-1} \right).(18)\p{18} On may verify that this is indeed the solution by substituting it into Equation 17.

The case κ(14,13)\kappa\in\left(\frac14,\frac13\right)

By using very similar methods but after very tedious calculation, the solution is g3(y,κ)g ⁣(y,κ(14,13))=lny((2+lnyκ1)yκ1(2+4lny2κ1+(lny2κ1)2)y2κ112=lny+(3lny3κ1+3(lny3κ1)2+12(lny3κ1)3)y3κ1).\begin{split} g_3(y,\kappa)&\coloneqq g\!\left(y,\kappa\in\left(\frac14,\frac13\right)\right)\\ &=-\ln y\left( \left(2+\ln y^{\kappa-1}\right)y^{\kappa-1} -\left(2+4\ln y^{2\kappa-1}+\left(\ln y^{2\kappa-1}\right)^2\right)y^{2\kappa-1}\vphantom{\frac12} \right.\\&\phantom{=-\ln y}\left. {}+\left(3\ln y^{3\kappa-1}+3\left(\ln y^{3\kappa-1}\right)^2+\frac12\left(\ln y^{3\kappa-1}\right)^3\right)y^{3\kappa-1} \right). \end{split}(19)\p{19}

Other cases

After seeing Equation 16, 18, and 19, one may guess the form of solution for other cases.

Guess the form of solution for κ(1q+1,1q)\kappa\in\left(\frac1{q+1},\frac1q\right), where q1q\in1\ldots\infty, is gq(y,κ)g ⁣(y,κ(1q,1q+1))=s=1qΔgs(y,κ),g_q(y,\kappa)\coloneqq g\!\left(y,\kappa\in\left(\frac1q,\frac1{q+1}\right)\right)=\sum_{s=1}^q\Delta g_s(y,\kappa), where Δgs(y,κ)(1)sysκ1lnyj=0sAs,jj!(lnysκ1)j,\Delta g_s(y,\kappa)\coloneqq\left(-1\right)^sy^{s\kappa-1}\ln y\sum_{j=0}^s\frac{A_{s,j}}{j!}\left(\ln y^{s\kappa-1}\right)^j, where As,jA_{s,j} are coefficients to be determined.

Now, consider the cases q2q\in2\ldots\infty. Because κ(1q+1,1q)\kappa\in\left(\frac1{q+1},\frac1q\right), min ⁣(κ1κ,1)=κ1κ(1q,1q1).\min\!\left(\frac\kappa{1-\kappa},1\right)=\frac\kappa{1-\kappa}\in\left(\frac1q,\frac1{q-1}\right). Therefore, = 0min(κ1κ,1)(g ⁣(y1κ,u)+δ(u1))du=01g ⁣(y1κ,u)dup=1q21p+11pgp ⁣(y1κ,u)duκ1κ1q1gq1 ⁣(y1κ,u)du=yκ11p=1q21p+11ps=1pΔgs ⁣(y1κ,u)duκ1κ1q1s=1q1Δgs ⁣(y1κ,u)du=yκ11s=1q1(p=sq21p+11p+κ1κ1q1)Δgs ⁣(y1κ,u)du=yκ11s=1q1κ1κ1sΔgs ⁣(y1κ,u)du,\begin{align*} &\phantom{=~}\int_0^{\min\left(\frac\kappa{1-\kappa},1\right)}\left(g\!\left(y^{1-\kappa},u\right)+\delta(u-1)\right)\mathrm du\\ &=\int_0^1g\!\left(y^{1-\kappa},u\right)\mathrm du -\sum_{p=1}^{q-2}\int_{\frac1{p+1}}^{\frac1p}g_p\!\left(y^{1-\kappa},u\right)\mathrm du -\int_{\frac\kappa{1-\kappa}}^\frac1{q-1}g_{q-1}\!\left(y^{1-\kappa},u\right)\mathrm du\\ &=y^{\kappa-1}-1 -\sum_{p=1}^{q-2}\int_{\frac1{p+1}}^{\frac1p}\sum_{s=1}^p\Delta g_s\!\left(y^{1-\kappa},u\right)\mathrm du -\int_{\frac\kappa{1-\kappa}}^\frac1{q-1}\sum_{s=1}^{q-1}\Delta g_s\!\left(y^{1-\kappa},u\right)\mathrm du\\ &=y^{\kappa-1}-1 -\sum_{s=1}^{q-1}\left( \sum_{p=s}^{q-2}\int_{\frac1{p+1}}^{\frac1p}+\int_{\frac\kappa{1-\kappa}}^\frac1{q-1} \right)\Delta g_s\!\left(y^{1-\kappa},u\right)\mathrm du\\ &=y^{\kappa-1}-1 -\sum_{s=1}^{q-1}\int_{\frac\kappa{1-\kappa}}^{\frac1s}\Delta g_s\!\left(y^{1-\kappa},u\right)\mathrm du, \end{align*}