Monday, January 15, 2018

算法回顾: Subsets 问题

问题概述:
DFS(深度优先搜索)要解决的问题之一为搜索所有的可能的解(all possible solutions). 
一般来说,当涉及到“所有”的时候, 有两种问题:
1. 枚举所有的子集 ( enumerate all subsets)
时间复杂度
有组合[1, 2, 3], 那么他的子集数目为 空集 ([ ])+ 其他所有子集。 其他所有子集为是否选取元素i: True or False. 那么 如果有N个元素, 则时间复杂度为2^N.
则具体的个数为2^N+1个组合。 
那么具体到时间复杂度则为给出每一个解得时间复杂度 X 总的解得个数: N2^N
具体的例题
Subsets
Given a set of distinct integers, return all possible subsets.
 Notice
Elements in a subset must be innon-descendingorder.
The solution set must not contain duplicate subsets.
Example
If S = [1,2,3], a solution is:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]
分析:
当给定一个空集来生成所有的子集时:
                                                          【】
                                   【1】              【2】                【3】  
                          【1,2】 【1,3】      【2,3】
                     【1,2,3】
搜索生成 1-》 1,2-》 1,2,3 达成终止条件, 1, 3 达成终止条件,返回, 2, 2,3 终止, 3
class Solution {
  public:
    vector < vector < int >> subsets(vector < int > & nums) {
      // write your code here
      vector < vector < int >> results;
      vector < int > solution;
      //确保是升序
      sort(nums.begin(), nums.end());
      helper(results, solution, nums, 0);
      return results;
    }
  void helper(vector < vector < int >> & results, vector < int > & solution, vector < int > & nums, int ind) {
    // add one solution
  // 如果是所有子集,先加入collection 再判断终止
    results.push_back(solution);
    // stop searching
    if (ind >= nums.size())
      return;
    // continue to search
    for (int i = ind; i < nums.size(); i++) {
      solution.push_back(nums[i]);
      // 更新solution并向下搜索
      helper(results, solution, nums, i + 1);
     // 返回到之前状态,向下一个状态搜索
      solution.pop_back();
    }
  }
};
那么对于深搜所有子集问题
1 push 当前解
2 判断是否应该终止搜索
3. 对于从当前层数(位置)开始往后的其他所有状态
a) 判断是否更新当前解
b) 向下搜索
c) 恢复更新
Subsets II
Given a list of numbers that may has duplicate numbers, return all possible subsets
 Notice
Each element in a subset must be innon-descendingorder.
The ordering between two subsets is free.
The solution set must not contain duplicate subsets.
分析:
此题与上题的区别为有重复元素出现, 所以过程中需要剪枝。 
例如 【1, 2, 2】 
第一次 为【1】 【2】 【2x】 (我们不需要两个2)
第二次为【1】 -》 【1, 2】【1,2 X】 (不需要两个【1,2】)
那么我们知道当元素出现重复的时候只需要取一个,关键是取第一个2还是第二个2?
需要一个例子 【1, 2, 2】 是有效的子集,那么如果取了第二个2,则不会出现
所以, a[i] == a[i-1]; continue;  为这里的剪枝部分
具体实现如下:
class Solution {
  public:
    /*
    * @param nums: A set of numbers.
    * @return: A list of lists. All valid subsets.
    */
    vector < vector < int >> subsetsWithDup(vector < int > & nums) {
      // write your code here
      vector < vector < int >> results;
      vector < int > solution;
      sort(nums.begin(), nums.end());
      helper(results, solution, nums, 0);
      return results;
    }
  void helper(vector < vector < int >> & results, vector < int > & solution,
    const vector < int > & nums, int ind) {
    results.push_back(solution);
    if (ind >= nums.size())
      return;
    for (int i = ind; i < nums.size(); i++) {
      if (i != ind && nums[i] == nums[i - 1])
        continue;
      solution.push_back(nums[i]);
      helper(results, solution, nums, i + 1);
      solution.pop_back();
    }
  }
};
2. 枚举所有的组合 ( enumerate all combinations)
时间复杂度
有组合[1, 2, 3], 那么他的所有的permutation, 为 
[1,2,3]
[ 2,1,3]
[2,1,3]
[2, 3, 1]
[3, 2, 1]
[3, 1, 2]
那么如何求得所有的permutation呢?
1, 2, 3 
1, 2, 3 -> 1, 2, 3 | 1, 3, 2
2, 1, 3  -> 2, 1, 3 | 2, 3, 1
3, 2, 1 -> 3 , 2, 1 | 3, 1, 2
可以看出 a0 与 [a0....an] swap后,继续向下搜索即可,算是一个完美的递归问题
具体的例题
Given a list of numbers, return all possible permutations.
Example
For nums = [1,2,3], the permutations are:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]
如上面分析, 每一个给定初始子集给与后,需要把a0 与[a0.... an]互换后向下搜索, 所以DFS条件就完美形成了。 注意的是向下搜索的时候不是搜索当前遍历的元素,而是搜索下一个index应该填入什么。 这个和全子集问题不同,全子集问题搜索的是选取不选取遍历的元素, 所以一个是更新了当前选取的元素并下下一个元素搜索, 一个是更新了当前状态,并向下一个状态搜索。
class Solution {
  public:
    /*
    * @param nums: A list of integers.
    * @return: A list of permutations.
    */
    vector < vector < int >> permute(vector < int > & nums) {
      // write your code here
      vector < vector < int >> results;
      helper(results, nums, 0);
      return results;
    }
  void helper(vector < vector < int >> & results, vector < int > & nums, int ind) {
    if (ind >= nums.size()) {
      results.push_back(nums);
      return;
    }
    for (int i = ind; i < nums.size(); i++) {
      swap(nums[i], nums[ind]);
      helper(results, nums, ind + 1);
      swap(nums[i], nums[ind]);
    }
  }
};
Permutation II
Given a list of numbers with duplicate number in it. Find allunique permutations.
Example
For numbers [1,2,2] the unique permutations are:
[
  [1,2,2],
  [2,1,2],
  [2,2,1]
]
分析:
第一次互换:
1,2,2 -》 1 -- 2,2  | 2 --1,2  | 2 --1,2
我们发现1 与 2互换了两次, 那么我们应该如何剪枝?
剪第一个2还是第二个2?
如果减掉第二个2, 则 2--1,2 向下发展 2 -- 1 ---2,  2-- 2---1
如果减掉第二个2, 结果是一样的
所以就这个问题而言, 1, 只需要和同样的数字互换一次即可。 但是具体操作如何实现?
因为中间过程中我们用了多次互换, 很难再用a[i] == a[i-1]这种小技巧了。 那么最优的办法是只和最后一次出现的数字换。 为什么不和最先一次的数字互换? 如果写完题目会发现从当前位置向前查找非常昂贵, 而向下查找非常便宜。 
class Solution {
  public:
    /*
    * @param :  A list of integers
    * @return: A list of unique permutations
    */
    vector < vector < int >> permuteUnique(vector < int > & nums) {
      // write your code here
      vector < vector < int >> results;
      permute(results, nums, 0);
      return results;
    }
  void permute(vector < vector < int >> & results, vector < int > & nums, int ind) {
    if (ind >= nums.size()) {
      results.push_back(nums);
      return;
    }
    for (int i = ind; i < nums.size(); i++) {
      bool found = false;
      for (int j = i + 1; j < nums.size(); j++) {
        if (nums[j] == nums[i]) {
          found = true;
          break;
        }
      }
      if (found)
        continue;
      swap(nums[i], nums[ind]);
      permute(results, nums, ind + 1);
      swap(nums[i], nums[ind]);
    }
  }
};

总结

1. All possible solutions 问题着重于解决2^n, n!的问题, 对于2^n的问题,是解决的各个元素选取与不选取的问题,中间过程的解均为全解的一部分。 而n!的问题为解决解得第i个元素应该对应给定的原第j个元素对其并向下搜索问题, 每次搜索触底后才算一个最终解。 所以我们会发现2^n问题是每次都会把初始子集加入解,判断终止, 并向下搜索, 而n!为判断终止后加入解。
results.push_back(solution); if stop ; vs if stop result.push_back(solution) 
2. 对于剪枝的问题,或者去掉重复问题,具体问题具体分析, 有可能是用第一个,有可能用最后一个,这个要在纸上画清楚
3. 回溯法的模板
(全子集, 加入解)
判断是否停止
    (最终解, 加入解)
向下搜索
遍历条件:
    判断是否需要剪枝,忽略
    改变状态
     向下搜索
     改回状态,方便下一个遍历

Tuesday, April 18, 2017

ERM

ERM: Enterprise Risk management
Centralized risk management
To:
Meet business obj, minimize unexpected earning volatility and maximize firm value

CRO may report to board or CEO/cfo, BUT A DOTTED relation should be between CEO/CRO to avoid conflicts.

Risk management should be transparent to outside

Monday, April 17, 2017

Corporate Governance And Risk Management

    Best  practices:

    • Independent board member
    • Take care of stakeholder and debt holder
    • CEO not the head and introduce CRO
    • Agency risk
    • Focus on economic performance instead of accounting performance
    • Compensation based on risk adjusted return
Board of directors oversee:
  • Policies, reports, strategy, control , audit, practics
Risk appetite -> tolerance/willingness a firm can take risk.

Transmitted by risk director and audit committee

Audit main role: make sure financial statement and regulatory report correct. Also oversee risk and so on

Hedging Risk Exposure


Hedging Risk Exposure:


Disadvantage: 

In theory:

  1. assume no tax and has same transaction cost, then the value dos not change…..Too fake
  2.  CPAM suggests focusing on  systematic risk (common for player) while non-systematic ones can be diversified (no perfect market)
  3. Derivative fully reflect underlying. Of course no, partial correlation, even no related derivative available

They do not consider bankruptcy.

In practice:

  1.  lose focus on making money
  2. Lack of knowledge
  3. Reduce volatility of value may result in reduce of earning cash flow

Advantage:


  1. Stable earning make fund raising easy
  2. Achieve board of director's goal
  3. Stable operation cost (put on consuming materials)
  4. Chance to get low tax


Hedging  Decision

 

Hedging  Decisions


The role of board of director
Decide firm's risk appetite with
  1. Decision on appetite  (accounting or economic, eg. Fx, short or long term heding eg. Put maturity, hard limit on quantities )
  2. With Quantative
  3. And qualitive method

Map risks

Analyze top 10 risk exposures according to market risk, credit risk, operation, business and so on. Give it dollar value. Ready for next step, hedge

Hedging risks


Pricing risk: fwd or call

FX: FX fwd, swap

Interest rate:  irs

Static vs Dynamic
Static, once decided, does not change
Dynamic, changing  but more transaction cost

Others:

  1. Time horizon goad matches
  2. If hedging position matches the goad
  3. Tax

Hedging instrument

OTC: difficult to price, less info, credit risk and so on…but I think it is cheaper most of time and designed for purchaser.
Exchange Traded : standard, clear price, enough info 

Sunday, April 16, 2017

Risk Management: A Helicopter View

  1.     Concept of Risk
    Risk  -> volatility of uncertain risk and uncertain gains -> risk take, profit gain. 
            -> 1. expected, can be well expected 2. unexpected (focus)
    Risk Management :
    A) manage expected risk
    B) manage unexpected risk

    Ultimately, determine the risk taking (take risk to gain)

     2.   Risk Management steps:

    Identify-> evaluate exposure->propose method->develop strat -> reevaluate/readjust
    Not perfect:
    A)  fail to identify risk B) no proper method
    1. Quantative measure:
    VaR95 -> %95 confidence level of min loss or 95% significance level of max loss
    Economic reserve:  ER =  ED*EP*ER , expected default rate* exposure*expected loss rate
    To keep liquidity and avoid from bankruptcy

    1. Qualitative measure:
    Scenario analysis: eg. Worst case scenario analysis looking at macroeconomic scenarios on entity
    Stress testing: stress on entity (shock factors etc)

     5.   ERM

    Look at risk overall firm, apply quant and quality analysis, board of director decide risk appetite, review, audit and so on

    1. Expected Loss vs Unexpected Loss
    EL: normal course, single factor with statistics collected from history and can be mitigated with increasing charge, spread over
    UL: unormal course, multi correlated factors, can be studied with hist data to gain some certainty

    1. Risk And Reward
    The more risk taken the more reward have, but reward has volatility.

     8.  Risks

      Market Risk:  market price/rate changes

      Interest rate risk, bond, unhedged, basis risk ( hedge not favorable)
      Equity Price risk , all market, secpecific ( diversify)
      FX Risk,  international interest rate
      commodity risk, sudden jump, black box
     

    Credit Risk:  counterparty cannot settle

     Default risk: fail to pay, bond
    Bankruptcy risk
     Downgrade risk downgraded ->default
    Settlement Risk:  in derivative (eg swap) losing party fail to pay

    To mitigate:
    Rate consider the risk taken, avoid concentration, avoid maturity concentration.

    Liquidity risk

    Funding risk: no money to pay, repurchase and etc
    Liquidity risk: cannot buy/sell with lack of counterparty

    Operation risk:
    Internal process and unexpected and unavoidable external factors.

    Legal and Regulatory Risk

    Tax, orders laws and etc

    Business Risk

    Things with specific product ( eg, production-consumption relation

     

    Strategic Risk

    Stupid board/management made stupid decision

    Reputation Risk


    Eg. Sanlu milk powder