In this paper, we revisit the portfolio allocation problem with designated risk-budget [Qian, 2005]. We generalize the problem of arbitrary risk budgets with unequal correlations to one that includes return forecasts and transaction costs while keeping the no-shorting (long-only positions) constraint. We offer a convex second order cone formulation that scales well with the number of assets and explore solutions to the problem in different settings. In particular, the problem is solved on a few practical cases - on equity and bond asset allocation problems as well as formulating index constituents for the NASDAQ100 index, illustrating the benefits of this approach.

risk-parity portfolio-optimization risk-budgeting mean-variance tactical-asset-allocation portfolio-allocation

§ INTRODUCTION

In portfolio allocation problems, risk-budgeting and risk-parity are two important criteria that are closely related to each other. Although the investment management community is quite familiar with risk-parity as a concept, the term risk-budgeting has been less heard and talked about, both in academic and practitioner circles. In fact, it may come as a surprise that the term risk-budgeting, mentioned in [Arnott, 2002] actually predates the term risk-parity that was coined around the same time as [Qian, 2005], where the authors provided a clear definition of risk contributions to a portfolio. Specifically,
the problem of risk budgeting the portfolio was defined as the following -
given covariance information on a basket of assets, risk budgeting seeks to form a portfolio whose partial risks are weighted as per a pre-determined scheme.

Consider $n$ assets indexed by set $[n]=\{1,2,\ldots,n\}$. Let $b_i \in [0,1]$ to be the fractional risk budget of asset $i \in [n]$ and

$C \in  \R^n \times \R^n$ their covariance matrix. Let $x \in\R^n$ representing the portfolio's fractional composition. The partial risk of asset $i$ under a variance risk measure can be expressed as $x_i (C x)_i$. Then, the risk budgeting portfolio for a specific risk measure, namely the variance, satisfies :

\begin{equation}\label{eq:par-def}
x_i(Cx)_i=b_i \,x^\top Cx,\quad i \in [n].
\end{equation}

Additionally, since the portfolio is fully invested and fractional risk budgets must add to 1 we have

\begin{equation}\label{eq:summation}
\sum_{i=1}^n x_i = 1 \mbox{ and } \sum_{i=1}^n b_i = 1
\end{equation}

Summarizing the above observations, we note that the risk budget problem $(\mathbf{P})$ can be formulated as:

minimize      √(x^⊤Cx)

$(\mathbf{P})$     subject to     x_i(Cx)_i     =     b_i x^⊤Cx,     i ∈[n]

1^⊤x     =     1

x     ≥    0

It should be noted that the risk parity problem is a specific case of the risk budgeting problem where all fractional risk budgets are equal, i.e. $b_i = \frac{1}{n}$ $\forall\, i \in [n]$. In this work we re-formulate the generalized risk-budgeting problem with return forecasts and transaction costs as a min-risk budgeting problem (a second order cone program) and discuss the applications of this result to systematic asset allocation.

§ PRIOR WORK AND CONTRIBUTION

§.§ Prior Work

As the concept of risk-parity took hold in the investment community through the 2008 banking crisis, [Qian, 2011] made a compelling case for risk-parity as an allocation strategy by focusing on the large risk allocation that popular 60-40 portfolios gave to equity markets.
[Bruder and Roncalli, 2012] defined the risk budgeting problem as a general case of the risk parity problem and presented theoretical results on the variance of the resulting portfolio - that it is in between the minimum variance and the corresponding weight budgeting portfolio. The authors also analytically solved the problem for the two-asset case and presented existence and uniqueness results for the general case. The authors in [Roncalli and Weisang, 2016] were able to extend the risk budgeting approach to risk factors - as an illustration, they showed that this approach can be used to allocate risk to the Fama-French factors in a systematic way.
In a work that seeks to understand the fundamental workings of risk-parity, [Asness et al., 2012] proposed leverage aversion as a plausible reason as to why the average investor does not hold the risk parity
portfolio. The authors also pointed out that not all investors have access to leverage, however, some do. These more sophisticated investors can
indeed benefit from the superior risk adjusted returns of the levered risk parity portfolio.
Focusing more on work that makes computational advances towards calculating the weights in the risk-parity portfolio, [Mausser and Romankov, 2014] reviewed existing formulations of the risk-parity portfolio (ERC - equal risk contribution portfolio), compared the empirical efficiency of solving this problem using a variety of techniques and proposed an alternate formulation that relied upon converting a hyperbolic constraint to a second order cone constraint. Consequently, they showed that the ERC portfolio with non-homogeneous correlations across assets can be solved as a second order cone program.
[Cesarone and Tardella, 2017] showed that the ERB (Equal Risk Bounding) is a superior technique than ERC for portfolio selection. In the case where short selling is allowed, the ERB portfolio was shown to be the same as the ERC portfolio.
In [Mausser and Romanko, 2018], the 2014 ERC portfolio SOCP formulation was extended to equal CVaR contributions.
[Gambeta, 2020] presented a formulation of the ERC portfolio that was relaxed to deviate from the ERC allocations to incorporate asset forecasts.
In more recent work, [Anis and Kwon, 2022] solved the ERC portfolio with a cardinality constraint. The authors empirically demonstrate that these portfolios show good out of sample performance.

In this work we extend the results of [Mausser and Romankov, 2014] to formulate an arbitrary risk budget portfolio with unequal correlations, return forecasts, transaction costs, and potentially also position constraints (the most generic case in portfolio optimization). We present a second order cone reformulation of the proposed problem and provide a computational analysis to demonstrate the efficacy and efficiency of the reformulation for examples with a large ($\approx$ 100) number of assets.

§.§ Problem Setup And Contribution

We consider a set of $n$ assets. We further define by $C \in \R^{n \times n}$ and $r \in \R^n$, the

covariance matrix and the vector of expected returns for these assets, respectively. We denote by $s$ a vector of investment sizes (denominated in $) of a long-only portfolio and $x_k$ the corresponding fractional holdings in the $k^{th}$ asset:

\begin{equation}
x_k = \frac{1} { \Sigma_i s_i}  s_k
\end{equation}

As shown by [Roncalli, 2013] and [Spinu, 2013] in prior work, a

solution to the risk budget problem  $(\mathbf{P})$ can be computed by solving an alternate problem $(\mathbf{P^*})$ given as follows:

${\displaystyle \min_{x\in\R^n_+}}$      1/2x^⊤Cx - ∑_i=1^n b_i logx_i

As a brief explanation of why this works, observe that the first order optimality conditions for $(\mathbf{P^*})$ are

\begin{equation}
(Cx)_i - \frac{b_i}{x_i}=0, \quad i\in[n],  \label{eq:KKT}
\end{equation}

which are exactly the risk budgeting conditions in $(\mathbf{P})$ if we set the total variance of the portfolio in (<ref>), without loss of generality, to 1. Note that the final portfolio satisfying the summation constraint (<ref>) can be obtained by re-scaling the weights so they sum to 1. It is worth-while to note that this works as equation (<ref>) is scale-invariant - if a solution $x^*$ satisfies (<ref>), so does $kx^*$. Problem $(\mathbf{P^*})$ is usually solved using some variant of Newton's method or block coordinate descent [Spinu, 2013].

Further observe that any additions of more parameter(s) to the objective function in the original problem (adding asset return forecasts or accounting for transactions cost) or adding additional constraints will alter the first order optimality conditions (<ref>). Consequently, target risk budgets may not be achieved. In other words, the convex formulation above only works in a very specific (almost impractical) case - with no return estimates, no  position constraints, or transaction costs.
It is noteworthy that [Mausser and Romankov, 2014] use a different approach in formulating the ERC portfolio, a special case of the risk budgeting portfolio, as an SOCP program. Their approach could potentially handle the extra constraints that are proposed in this work, however the formulation is specifically for computing an ERC portfolio.

Our work extends the work of [Mausser and Romankov, 2014] to show the generalized second order cone program formulation for an arbitrary risk budgeting portfolio allocation with return forecasts and transaction costs. We solve arbitrary risk budgeting exactly and argue its merits as a portfolio allocation process. Further, we provide examples that show it's benefits on a few uses cases. Finally we explore variations of exact risk budgeting that relax the risk budgeting equality constraints to provide long-term economic value to the portfolio.

§.§ Generalized Risk Budgeting

As discussed earlier, the risk budgeting problem that can be solved by using the KKT conditions for the modified unconstrained problem is a starting point for the risk budgeting approach. However, two major disadvantages of the formulation are - (a) Asset managers are known to have return forecasts, even though the estimates may be error-prone. (b) Risk budgets are not exactly known, however, the minimum or maximum risk allocation for each asset class usually are known to a sophisticated asset manager.

In particular, we focus on a specific version of this problem where asset managers have strong opinions on the maximum risk budgets they would like to allocate for each asset (or strategy). Indeed, an effective asset allocation strategy could begin with a clear picture of a `max-risk-budget' that a manager would like to have in order to meet return expectations. These could be driven out of sector specific maximum risk allocations or other requirements from an allocation. For example, one can have a desirable maximum allocation to Environmental and Socially Responsible companies (ESG). In this context, we now consider the following mean variance with max-risk budgeting problem $(\mathbf{\bar{P}})$

minimize     - r^⊤x + λ √(x^⊤Cx)

$(\mathbf{\bar{P}})$     subject to     x_i(Cx)_i     ≤    b_i x^⊤Cx,     i∈[n]

l ≤    x     ≤u

1^⊤x     =     1

where $r_i$ is the return of asset $i$, $\lambda > 0$ controls the mean-variance trade-off, the scalar $b_i$ is the minimum risk budget for asset $i$ and the vectors $l,u\in\R^n_+$ are bounds on portfolio weights. Arguably, this problem does away with all of the limitations of the previous formulation. Return forecasts can be incorporated, upper limits on risk budgets can be set, and position limits are also incorporated. Transaction costs for a multi-period setting can be added with an extra term in the objective function, which we show later.

One observation about this formulation is the following: Suppose there is a feasible solution to $(\mathbf{\bar{P}})$ and the risk budgeting constraints (<ref>) do not hold with equality for all $i$, then, by definition $\exists\, m \in [n]$ such that

\begin{align}\label{eq:rba-sum_contra}
x_m(Cx)_m < b_m\,x^\top Cx
\end{align}

where the inequality is strict. Summing across all $i$,

\begin{align}
\sum_i x_i(Cx)_i < \sum_i b_i\,x^\top Cx
\end{align}

However this suggests that the sum of all marginal risk budgets, which must sum to the total risk, is strictly less than the total risk establishing a contradiction. A similar argument can be made if the strict inequality in (<ref>) is facing the other direction.

This implies that risk-budget constraints in $(\mathbf{\bar{P}})$ must hold with equality if the solution exists. We can thus reformulate $(\mathbf{\bar{P}})$ equivalently as a  min-risk constraint risk budgeting problem:

minimize     - r^⊤x + λ √(x^⊤Cx)

$(\mathbf{\bar{P}})$     subject to     x_i(Cx)_i     ≥    b_i x^⊤Cx,     i∈[n]

l ≤    x     ≤u

1^⊤x     =     1

§ A SECOND ORDER CONE PROGRAMMING FORMULATION

Assume that $x_i$ is non-zero, and satisfies

\begin{align}\label{eq:rba-prog2}
x_i(Cx)_i \geq  b_i\,x^\top Cx, \,\, i=1,\ldots,n
\end{align}

Let $Cx = y$ and $C = R^\top R$ be the Cholesky decomposition of $C$. Letting $s_i = \sqrt{b_i} Rx$ we have,

\begin{align}\label{eq:rba-prog3}
x_i y_i \geq s_i^\top s_i, \,\, i\in [n].
\end{align}

(<ref>) represents a rotated second order cone constraint. This can further be reformulated as a second order cone constraint, i.e., for all $i\in [n]$

\begin{align}\label{eq:rba-prog5}
\begin{Vmatrix} x_i - y_i \\ 2s_i \\ \end{Vmatrix} \ \le x_i + y_i
\end{align}

Alternatively, substituting for $y$ and $s$ we have:

\begin{align}\label{eq:rba-prog6}
\begin{Vmatrix} x_i - (C x)_i \\ 2 \sqrt{b_i} R x \\ \end{Vmatrix} \ \le x_i + (C x)_i.
\end{align}

Consequently, we can re-write the mean variance optimization problem under risk budgeting constraints in Eq. (<ref>) as a convex second order cone program:

minimize     -r^⊤x + λ  Rx+ μ  x-x_0_1

subject to
x_i - (C x)_i

2 √(b_i) R x
≤     x_i + (C x)_i

l ≤    x     ≤u

1^⊤x     =     1

The above formulation has obvious advantages when it comes to solving this problem at scale [Boyd et al., 2004]. Further more, in the limiting case when $b_i$ are set to $1/m$ where m is the number of assets, it yields the risk parity portfolio. We have included a term for transaction costs that scales as per the L1 norm of the difference between the target position and the previous position in the portfolio. This formulation compared with the previous one as in $(\mathbf{P^*})$ can be tweaked to suit individual portfolio managers requirements.

§ EMPIRICAL ANALYSIS

We evaluate the performance of our solution approach on four use cases in this section. Each use case has three flavors of risk budgeting style allocation. The first is a vanilla scenario where the outcome of the min-risk budgeting problem is used as is (MRB portfolio), the second where the output of the optimization problem is used to estimate portfolio expected returns and we liquidate the portfolio (abstain option) if the expected return is less than zero (MRBA portfolio), and the third is a combination of the abstain option with leverage (MRBAL portfolio). The leverage was calculated as the ratio between the ex-ante estimated standard deviation of the CRB portfolio and the MRB portfolio, and the MRBA portfolio was scaled with this ratio to obtain the weights for the MRBAL portfolio. For practical considerations, the permissible leverage for MRBAL was capped at 1.5x.

§.§ Two Assets

In this example, we show how min-risk budgeting can be combined with a simple momentum forecast to create portfolio value over the long term. We used a 40-10 allocation between the S&P500 (Ticker: SPY) and iShares Core U.S. Aggregate Bond (Ticker: AGG) ETFs, which involves setting a min-risk budget of 40% for equity and 10% for bond markets. Note that these don't have to add up to 100%; the only condition is that they have to sum to a number less than equal to 100%. No transaction costs were incorporated. The benchmark used is a equal weighted constant re-balance portfolio (CRB portfolio) that allocates half of the portfolio to the equity and the remaining half to the bond ETF. Both are re-balanced weekly and the weekly median price was used for entry and exit. The mean-variance trade-off parameter $\lambda$ was set at 1. Our estimates of the return in the upcoming week were always set to the returns for the previous week.

We retrospectively let the prices evolve over the 720 weeks (starting on and ending on July 24, 2022) and test the performance of the allocation algorithms over this period (backtest).

Results are shown in Figure 1. Return forecasts can be unreliable in general, but the results show that having clear ideas on the risk diversification ex-ante is useful, as the risk adjusted returns are higher for the MRB portfolio. The MRBA (min-risk budgeting with abstain option) shows a better return profile with smaller draw-downs. The MRBAL portfolio that stays out of markets when expected return is negative and uses leverage (upto 1.5X) out-performs the constant re-balance portfolio both in terms of return and draw-down profiles.

Backtest Results: Min Risk Allocation for two assets, SPY 40%, AGG 10%

Top five drawdowns (absolute value) with dates in focus for the constant re-balance portfolio are shown in Table 1. For all four strategies drawdowns are shown below in Table 2, where the top five drawdowns for each allocation strategy are displayed.

Periods of Drawdowns for CRB portfolio

From     To     Drawdown.CRB

1     2007-10-19     2010-10-08     $ 0.287$

2     2020-02-28     2020-07-17     $0.169$

3     2022-01-07     2022-07-24      $0.164$

4     2018-09-07     2019-03-15     $0.068$

5     2011-07-15     2012-01-06     $0.057$

Top five drawdowns for each portfolio

DD.CRB     DD.MRB     DD.MRBA     DD.MRBAL

1     0.29     0.15     0.04     0.05

2     0.17     0.12     0.04     0.05

3     0.16     0.08     0.04     0.05

4     0.07     0.05     0.04     0.05

5     0.06     0.03     0.03     0.04

The CRB portfolio has a staggering max drawdown of 29 % compared to the MRBA portfolio at 4 %.

§.§ Four Assets, including Gold and SPY Levered ETF

In this example, we repeat the experiment in <ref> with an expanded set of assets and we change the benchmark to a risk parity allocation. In particular, we include a commodity and a leveraged ETF to enhance leverage and diversity in the portfolio. The two additional ETFs chosen were SPXL (Direxion Daily S&P500 Bull 3X) and GLD (SPDR Gold Shares). As a result of limited history for SPXL, we have 3,451 days of data which translate to 720 weeks of data as of July 24 2022. The chosen risk budget allocations across SPY, AGG, SPXL, GLD were 35%, 5%, 35%, 5%. The risk parity portfolio has these set to 25% risk for each asset. Other parameters were kept the same as <ref>.

Backtest Results: Min Risk Allocation at SPY 35%, AGG 5%, SPXL 35%, GLD 5%

The results show that the Risk Parity strategy can be adjusted with a flexible parameter of a min-risk setting, and the allocation that comes from the framework enhances the return profile in case of both the leveraged (MRBAL) and unleveraged (MRB, MRBA) version of the backtest.

§.§ NASDAQ 100 Constituents

In this example we used a selection of 64 assets (listed cash equity) from the US stock market that are a subset of the NASDAQ 100 index constituents. Tickers that were part of the index as of July 24, 2022 and had availability of daily price time-series data for at least 5,423 (a sufficiently large number) trading days were chosen as the asset universe. The tickers were retrieved from the NASDAQ web page [3]

on the same date, 102 tickers were filtered using the above criteria to yield 64 tickers with at least the minimum threshold of price history. Daily price data was downloaded from EODHistoricalData's (a commercial service) end of day API [1]

. We down-sampled the daily price data to a weekly time-series and used the weekly median price as the entry and exit price (or vice versa) for the trading simulation. We used momentum return forecasts by setting forecast return to be the same as the previous week's return. The minimum risk budget for each asset is set as half of the cross-sectionally normalized cumulative return thus far for that asset. The ratio of half can be chosen arbitrarily, the key concept here is that we are choosing less than the desired allocation as a lower limit on the risk budget to allow trade offs between the return forecast and the risk budget. The covariance matrix is measured point in time including all of the returns thus far and if not already positive-definite, it was adjusted to obtain the nearest positive-definite matrix following the result in [Higham, 1988] that the nearest symmetric positive semi-definite matrix in the Frobenius norm to an arbitrary real matrix $C$ is $(B + H)/2$, where H is the symmetric polar factor of $B=(C + C')/2.$

The results are shown in Figure <ref>. We also introduce a new benchmark that sets dollar weighting of the asset to be the cross-sectionally normalized cumulative return thus far for that asset, in order to produce a benchmark that is closer to the MRB back tests. We denote this second benchmark as CRB.SMART and it is shown in comparison to the first benchmark CRB and the min risk budget backtests (MRB, MRBA and MRBL). Note that this backtest has an inherent look head bias in that it uses assets that survive the period between September 2000 and July 2022. Hence the asset universe comprises of higher quality assets than the NASDAQ at that point in time. Since we are comparing only the relative performance of the class of MRB* portfolios to the risk parity portfolio, this chart serves its purpose as a relative comparison and is not indicative of absolute performance.

Backtest Results: Allocation into NASDAQ 100 constituents

Drawdown tables are shown in Table <ref>.

Top five drawdowns for each portfolio - NASDAQ Constituents

CRB     CRB.SMART     MRB     MRBA     MRBAL

1     0.46     0.44     0.42     0.26     0.28

2     0.38     0.38     0.26     0.18     0.26

3     0.27     0.26     0.21     0.14     0.18

4     0.26     0.25     0.19     0.14     0.17

5     0.23     0.18     0.13     0.14     0.17

§.§ FTSE 100 Constituents

Here we use a European equity market selection of 72 assets (listed cash equity) from the stocks that are listed on the London Stock Exchange(LSE) and are part of the FTSE 100 as of July 24 2022. The criteria for selection was the same as in the previous example in <ref>. Tickers that were part of the FTSE index as of July 24, 2022 and had availability of daily price time-series data for 5,448 trading days were chosen as the asset universe.
The tickers were retrieved from the LSE web page [2]

on the same date, 102 tickers were filtered using the criteria mentioned above to yield 72 tickers. Trading simulation parameters are same in <ref>, in addition a 10 basis point transaction cost parameter was incorporated. The results are shown in Figure <ref>. The results confirm that setting minimum values of risk budget can be an important tool in an investment professional's arsenal.

Backtest Results: Allocation into FTSE 100 constituents

Drawdown tables are shown in Table <ref>.

Top five drawdowns for each portfolio - FTSE Constituents

CRB     SMART     MRB     MRBA     MRBAL

1     0.47     0.45     0.26     0.17     0.19

2     0.33     0.35     0.25     0.17     0.19

3     0.30     0.23     0.20     0.16     0.18

4     0.20     0.19     0.18     0.15     0.17

5     0.17     0.18     0.14     0.14     0.16

§ CONCLUSION

Portfolio optimization is an area where techniques from operations research can be used to create more stable portfolios, keeping other factors the same. We have shown a powerful technique for portfolio optimization where risk and return can be traded off systematically to create resilient portfolios. Due to the reliance of the allocation strategy on variance information only, these methods are applicable whenever price data is available, making these techniques very flexible. The technique described in this work can be useful for sophistical retail investors, traditional investment management companies and also to the more new-age robo-advisors.

[1]
Eod historical data.
Accessed: 2022-07-24.

[2]
FTSE100 constituents.
Accessed: 2022-07-24.

[3]
NASDAQ100 constituents.
Accessed: 2022-07-24.

[Anis and Kwon, 2022]
H. T. Anis and R. H. Kwon.
Cardinality-constrained risk parity portfolios.
European Journal of Operational Research, 2022.
ISSN 0377-2217.

[Arnott, 2002]
R. D. Arnott.
Risk budgeting and portable alpha.
The Journal of Investing, 110 (2):0 15–22,

[Asness et al., 2012]
C. S. Asness, A. Frazzini, and L. H. Pedersen.
Leverage aversion and risk parity.
Financial Analysts Journal, 680 (1):0 47–59,

[Boyd et al., 2004]
S. Boyd, S. P. Boyd, and L. Vandenberghe.
Convex optimization.
Cambridge university press, 2004.

[Bruder and Roncalli, 2012]
B. Bruder and T. Roncalli.
Managing risk exposures using the risk budgeting approach.
Available at SSRN 2009778, 2012.

[Cesarone and Tardella, 2017]
F. Cesarone and F. Tardella.
Equal risk bounding is better than risk parity for portfolio
Journal of Global Optimization, 680 (2):0
439–461, 2017.

[Gambeta, 2020]
V. E. Gambeta.
Risk Parity Return Trade-off in Relaxed Risk Parity Portfolio
PhD thesis, University of Toronto (Canada), 2020.

[Higham, 1988]
N. J. Higham.
Computing a nearest symmetric positive semidefinite matrix.
Linear algebra and its applications, 103:0 103–118,

[Mausser and Romanko, 2018]
H. Mausser and O. Romanko.
Long-only equal risk contribution portfolios for cvar under discrete
Quantitative Finance, 180 (11):0 1927–1945,

[Mausser and Romankov, 2014]
H. Mausser and O. Romankov.
Computing equal risk contribution portfolios.
IBM J. Res. & Dev., pages VOL. 58, NO. 4 PAPER 5, 2014.

[Qian, 2011]
E. Qian.
Risk parity and diversification.
The Journal of Investing, 200 (1):0 119–127,

[Qian, 2005]
E. E. Qian.
On the financial interpretation of risk contribution: Risk budgets do
add up.
Available at SSRN 684221, 2005.

[Roncalli, 2013]
T. Roncalli.
Introduction to risk parity and budgeting.
CRC Press, 2013.

[Roncalli and Weisang, 2016]
T. Roncalli and G. Weisang.
Risk parity portfolios with risk factors.
Quantitative Finance, 160 (3):0 377–388,

[Spinu, 2013]
F. Spinu.
An algorithm for computing risk parity weights.
Available at SSRN 2297383, 2013.


Skew Dyck paths having no peaks at level 1 (Sequence A128723)
Helmut Prodinger
Stellenbosch University
Department of Mathematical Sciences
7602 Stellenbosch
South Africa,
and
NITheCS
(National Institute for Theoretical and Computational Sciences)
South Africa
<EMAIL_ADDRESS>

###### Abstract

Skew Dyck paths are a variation of Dyck paths, where additionally to steps
$(1,1)$ and $(1,-1)$ a south-west step $(-1,-1)$ is also allowed, provided
that the path does not intersect itself. Replacing the south-west step by a
red south-east step, we end up with decorated Dyck paths. Sequence A128723 of
the Encyclopedia of Integer Sequences considers such paths where peaks at
level 1 are forbidden. We provide a thorough analysis of a more general
scenario, namely partial decorated Dyck paths, ending on a prescribed level
$j$, both from left-to-right and from right-to-left (decorated Dyck paths are
not symmetric). The approach is completely based on generating functions.

##  1 Introduction

Skew Dyck paths are a variation of Dyck paths, where additionally to steps
$(1,1)$ and $(1,-1)$ a south-west step $(-1,-1)$ is also allowed, provided
that the path does not intersect itself. Replacing the south-west step by a
red south-east step, we end up with decorated Dyck paths. Our earlier
publication [2] studied such paths using generating functions.

Figure 1: All 10 skew Dyck paths of length 6 (consisting of 6 steps).

Figure 2: The 10 paths redrawn, with red south-east edges instead of south-
west edges.

Sequence A128723 considers such paths where peaks at level 1 are forbidden.
These paths are the main objects of the present paper.

The Figures 1, 2, 3 describe such paths of length 6.

Figure 3: The 6 paths without peaks on level 1.

We catch the essence of a decorated Dyck path using a state-diagram (Fig. 4):

Figure 4: Three layers of states according to the type of steps leading to
them (up, down-black, down-red).

It has three types of states, with $j$ ranging from 0 to infinity; in the
drawing, only $j=0..8$ is shown. The first layer of states refers to an up-
step leading to a state, the second layer refers to a black down-step leading
to a state and the third layer refers to a red down-step leading to a state.

If the dashed edge is present, the graph models skew (decorated) Dyck paths.
Any path from the origin to a node on level $j$ represents such a decorated
Dyck path ending on level $j$. In particular, if $j=0$, the path comes back to
the $x$-axis. Note that the syntactic rules of forbidden patterns  and  can be
clearly seen from the picture.

However, if the dashed edge is _not_ present, it means that peaks at level 1
cannot be modeled by this graph, and that is what we want in the present
paper.

We will work out generating functions describing all paths leading to a
particular state. We will use the notations $f_{j},g_{j},h_{j}$ for the three
respective layers, from top to bottom. Although one could in principle compute
all these functions separately, we are mainly interested in
$s_{j}=f_{j}+g_{j}+h_{j}$, so we are interested in paths arriving on level $j$
but we do not care in which way this final level has been reached. It is also
clear that a path of length $n$ leading to a state at level $j$ must satisfy
$n\equiv j\bmod 2$.

In a last section, the right-to-left model is briefly described. Then, red
down-steps become blue up-steps.

##  2 Generating functions and the kernel method

The functions depend on the variable $z$ (marking the number of steps), but
mostly we just write $f_{j}$ instead of $f_{j}(z)$, etc.

The following recursions can be read off immediately from the diagram (Fig.
4):

$\displaystyle f_{0}=1,\quad f_{i+1}=zf_{i}+zg_{i},\quad i\geq 0,$
$\displaystyle g_{i}=zf_{i+1}+zg_{i+1}+zh_{i+1},\quad i\geq 1,$ $\displaystyle
g_{0}=zg_{i+1}+zh_{i+1},\quad i\geq 1,$ $\displaystyle
h_{i}=zh_{i+1}+zg_{i+1},\quad i\geq 0.$

We can make a few direct observations: $f_{0}=1$, $f_{1}=z+zg_{0}$,
$g_{0}=h_{0}$. The latter can be proved from combinatorial reasoning, since
switching the last step from black to red resp. from red to black constitutes
a bijection. This is a consequence of the fact that there are no peaks at
level 1, otherwise the syntactic restrictions might be violated.

Now it is time to introduce _bivariate_ generating functions:

$F(z,u)=\sum_{i\geq 0}f_{i}(z)u^{i},\quad G(z,u)=\sum_{i\geq
0}g_{i}(z)u^{i},\quad H(z,u)=\sum_{i\geq 0}h_{i}(z)u^{i}.$

Again, often we just write $F(u)$ instead of $F(z,u)$ and treat $z$ as a
‘silent’ variable. Summing the recursions leads to

$\displaystyle\sum_{i\geq 0}u^{i}f_{i+1}$ $\displaystyle=\sum_{i\geq
0}u^{i}zf_{i}+\sum_{i\geq 0}u^{i}zg_{i},$ $\displaystyle\sum_{i\geq
1}u^{i}g_{i}$ $\displaystyle=\sum_{i\geq 1}u^{i}zf_{i+1}+\sum_{i\geq
1}u^{i}zg_{i+1}+\sum_{i\geq 1}u^{i}zh_{i+1},$ $\displaystyle\sum_{i\geq
0}u^{i}h_{i}$ $\displaystyle=\sum_{i\geq 0}u^{i}zh_{i+1}+\sum_{i\geq
0}u^{i}zg_{i+1}.$

This can be rewritten as

$\displaystyle\frac{1}{u}(F(u)-1)$ $\displaystyle=zF(u)+zG(u),$
$\displaystyle\sum_{i\geq 1}u^{i}g_{i}+g_{0}$ $\displaystyle=\sum_{i\geq
1}u^{i}zf_{i+1}+\sum_{i\geq 1}u^{i}zg_{i+1}+zg_{1}+\sum_{i\geq
1}u^{i}zh_{i+1}+zh_{1},$ $\displaystyle\sum_{i\geq 0}u^{i}g_{i}$
$\displaystyle=\sum_{i\geq 1}u^{i}zf_{i+1}+\sum_{i\geq
0}u^{i}zg_{i+1}+\sum_{i\geq 0}u^{i}zh_{i+1},$ $\displaystyle G(u)$
$\displaystyle=\frac{z}{u}[F(u)-f_{0}-uf_{1}]+\frac{z}{u}[G(u)-g_{0}]+\frac{z}{u}[H(u)-h_{0}],$
$\displaystyle H(u)$
$\displaystyle=\frac{z}{u}(G(u)-G(0))+\frac{z}{u}(H(u)-H(0)).$

Instead of working with 3 functions, we can reduce the system to just one
equation (with the variable $G$):

$F=\frac{1+zuG}{1-zu},\quad H=\frac{z(G-g_{0}-h_{0})}{u-z}.$

Using this, we get

$G=\frac{-z^{3}u(u-z)+z(1-zu)(2+zu-z^{2})g_{0}}{z(u-r_{1})(u-r_{2})}$

with

$r_{1}=\frac{1+z^{2}+\sqrt{1-6z^{2}+5z^{4}}}{2z},\quad
r_{2}=\frac{1+z^{2}-\sqrt{1-6z^{2}+5z^{4}}}{2z}.$

Note that $r_{1}r_{2}=2-z^{2}$. Since the factor $u-r_{2}$ in the denominator
is “bad,” it must also cancel in the numerator. This is an essential step in
the kernel method, see for instance our own survey [1]. This leads to the new
version

$G=\frac{-z^{3}(u-z+r_{2})-z^{2}(-z^{2}+zu+1+zr_{2})g_{0}}{z(u-r_{1})}.$

Plugging in $u=0$ and solving the equation

$G(z,0)=g_{0}=\frac{-z^{3}(-z+r_{2})-z^{2}(-z^{2}+1+zr_{2})g_{0}}{z(-r_{1})}$

leads to

$g_{0}={\frac{1-2{z}^{4}-3{z}^{2}-\sqrt{1-6z^{2}+5z^{4}}}{2({z}^{2}+3){z}^{2}}}.$

Knowing this, we know $G$, and thus $F$ and $H$. As the first goal, we still
set $u=0$, thus considering paths coming back to the $x$-axis. Using Maple,

$s_{0}:=f_{0}+g_{0}+h_{0}={\frac{1-{z}^{4}-\sqrt{1-6z^{2}+5z^{4}}}{({z}^{2}+3){z}^{2}}}.$

### The conjecture

We write $z^{2}=x$, since skew paths, as discussed here, must have an even
number of steps. The function

$y(x)={\frac{1-{x}^{2}-\sqrt{1-6x+5x^{2}}}{x(x+3)}}$

is the generating function of the sequence A128723:

$1,0,2,6,22,84,334,1368,5734,24480,106086,465462,2063658,9231084,41610162,\dots$

Gfun, as described in [3], produces the algebraic equation that $y(x)$
satisfies:

$-(x-1)(x-2)+3x+2(1-x^{2})y-x(3+x)y^{2}=0$

and from this the differential equation

$-\left(9{x}^{2}+5{x}^{3}+3-17x\right)xy^{\prime}+\left(9{x}^{2}+7x-5{x}^{3}-3\right)y+3+9{x}^{2}-5{x}^{3}-7x$

and finally from the differential equation the recursion for the coefficients
$s_{n}=[x^{n}]y(x)$:

$3(n+4)s_{n+3}-(17n+41)s_{n+2}+9ns_{n+1}+5(n+1)s_{n}=0.$

An equivalent recursion was conjectured in the description of sequence A128723
[4].

### Partial paths

Another compution with Maple leads to

$S(z,u)=F(z,u)+G(z,u)+H(z,u)={\frac{-{z}^{4}-{z}^{4}g_{0}-{z}^{2}g_{0}+{z}^{2}-1}{z(u-r_{1})}}.$

Further

$\displaystyle s_{j}:=[u^{j}]S(z,u)$
$\displaystyle={\frac{{z}^{4}+{z}^{4}g_{0}+{z}^{2}g_{0}-{z}^{2}+1}{zr_{1}(1-u/r_{1})}}$
$\displaystyle={\frac{{z}^{4}+{z}^{4}g_{0}+{z}^{2}g_{0}-{z}^{2}+1}{zr_{1}^{j+1}}}.$

One sees the parity: $j$ even/odd iff exponents are even/odd. If it is
desired, $1/r_{1}$ may be expressed by $r_{2}$ (and a factor).

### Open-ended paths

We might allow _any_ level as end-level of the path. In terms of generating
functions, this means to consider $S(z,1)$, viz.

$S(z,1)=\frac{-2{z}^{5}-3{z}^{4}+{z}^{3}-5{z}^{2}-3z+4-(z^{2}+3z+4)\sqrt{1-6z^{2}+5z^{4}}}{2z(3+z^{2})(z^{2}+2z-1)}.$

The sequence of coefficients

$1,1,1,2,5,8,18,31,71,126,290,527,1218,2253,5223,9796,22763,43170,100502,192347,\dots$

is not in the encyclopedia [4].

##  3 Reading the decorated paths from right to left

Since decorated paths are not symmetric, it makes sense to consider this
scenario separately.

Figure 5: All 6 dual (=right-to-left) skew Dyck paths of length 6 (consisting
of 6 steps), having no peak at level 1.

We catch the essence of a decorated (dual skew) Dyck path using a state-
diagram:

Figure 6: Three layers of states according to the type of steps leading to
them (down, up-black, up-blue).

Note that the syntactic rules of forbidden patterns  and  can be clearly seen
from the picture.

As in the earlier section, if the dashed edge is removed it means that the
condition ‘no peak at level 1’ is modeled, which is what we need to do. Using
the letters $c_{j},a_{j},b_{j}$ (in that order) for the generating functions
to reach state $j$ in the particular layer, we find the following recursions
immediately from the diagram:

$\displaystyle a_{0}=1,\quad a_{i+1}=za_{i}+zb_{i}+zc_{i},\quad i\geq 0,$
$\displaystyle b_{0}=zb_{1},\quad b_{i}=za_{i+1}+zb_{i+1},\quad i\geq 1,$
$\displaystyle c_{i+1}=za_{i}+zc_{i},\quad i\geq 0.$

We introduce _bivariate_ generating functions:

$A(z,u)=\sum_{i\geq 0}a_{i}(z)u^{i},\quad B(z,u)=\sum_{i\geq
0}b_{i}(z)u^{i},\quad C(z,u)=\sum_{i\geq 0}c_{i}(z)u^{i}.$

Summing the recursions leads to

$\displaystyle A(u)$ $\displaystyle=\sum_{i\geq 0}u^{i}a_{i}=1+u\sum_{i\geq
0}u^{i}(za_{i}+zb_{i}+zc_{i})$ $\displaystyle=1+uzA(u)+uzB(u)+uzC(u),$
$\displaystyle\sum_{i\geq 0}u^{i}b_{i}$ $\displaystyle=\sum_{i\geq
1}u^{i}za_{i+1}+\sum_{i\geq 0}u^{i}zb_{i+1},$ $\displaystyle B(u)$
$\displaystyle=\frac{z}{u}\sum_{i\geq 2}u^{i}a_{i}+\frac{z}{u}\sum_{i\geq
1}u^{i}b_{i}$
$\displaystyle=\frac{z}{u}[A(u)-a_{0}-ua_{1}]+\frac{z}{u}[B(u)-b_{0}],$
$\displaystyle\sum_{i\geq 1}u^{i}c_{i}$ $\displaystyle=uz\sum_{i\geq
0}u^{i}a_{i}+uz\sum_{i\geq 0}u^{i}c_{i},$ $\displaystyle C(u)-c_{0}$
$\displaystyle=uzA(u)+uzC(u).$

We have $c_{0}=0$, $a_{0}=1$, and $a_{1}=z+zb_{0}$. We may write

$C(u)=\frac{uzA(u)}{1-uz},$
$A(u)=1+uzA(u)+uzB(u)+\frac{u^{2}z^{2}A(u)}{1-uz}=\frac{1+uzB(u)}{1-uz-\frac{u^{2}z^{2}}{1-uz}}=\frac{1-uz}{1-2uz}[1+uzB(u)],$
$C(u)=\frac{uz}{1-2uz}[1+uzB(u)].$

Solving for $B(u)$,

$B(u)=\frac{z\left(2{u}^{2}{z}^{2}+2{z}^{2}{u}^{2}b_{0}+b_{0}zu-
b_{0}\right)}{z(z^{2}-2)(u-r_{1}^{-1})(u-r_{2}^{-1})}.$

We cancel the bad factor $(u-r_{1}^{-1})$ out of the numerator:

$B(u)=\frac{z(2r_{1}uz+2r_{1}uzb_{0}+b_{0}r_{1}+2z+2zb_{0})r_{2}}{r_{1}({z}^{2}-2)(ur_{2}-1)}$

Plugging in $u=0$ results in the equation

$b_{0}=\frac{-z(b_{0}r_{1}+2z+2zb_{0})r_{2}}{r_{1}({z}^{2}-2)}$

and thus

$b_{0}=\frac{1-z^{4}-\sqrt{1-6z^{2}+5z^{4}}}{z^{2}(3+z^{2})}-1,$

as expected, since $1+b_{0}$ is the generating function of all skew Dyck paths
without peaks at level 1.

Expressions for $A(z,u)+B(z,u)+C(z,u)$ and $[u^{j}](A(z,u)+B(z,u)+C(z,u))$
could be explicitly written, which we leave to the reader.

The open paths in this model are enumerated via

$A(z,1)+B(z,1)+C(z,1),$

which is a long expression, with coefficients

$1,2,4,10,24,56,134,318,764,1824,4390,10520,25346,60878,146768,\dots$

which are again not in the OEIS [4].

Explicit formulæ for this model are a bit unpleasant, but easily regenerated
using Maple.

##  4 Conclusion

In order to keep this paper short (and not boring) we refrained from working
out many additional parameters. That might be a good project for graduate
students.

## References

  * [1] Helmut Prodinger.  The Kernel Method: A Collection of Examples,  Séminaire Lotharingien de Combinatoire, B50f (2004), 19 pp.
  * [2] H. Prodinger, Partial skew Dyck paths—a kernel method approach, arXiv:2108.09785 (2021).
  * [3] B. Salvy and P. Zimmermann.  Gfun: A Maple package for the manipulation of generating and holonomic functions in one variable.  ACM Trans. Math. Softw., 20(2): 163–177 1994.
  * [4] Neil J. A. Sloane and The OEIS Foundation Inc.  The on-line encyclopedia of integer sequences, 2022.

2010 Mathematics Subject Classification: Primary 05A15; Secondary 05A19.

_Keywords: Skew Dyck path, peak, forbidden pattern, generating function,
kernel-method._

(Concerned with sequence A128723.)

Return to Journal of Integer Sequences home
pagehttps://cs.uwaterloo.ca/journals/JIS/.