# Category Archives: Theory

# bin and ball

### Lemma

Comment: conpon analysis + chernoff bound

### Lemma

### Lemma

## Reference

[1] Co-Location-Resistant Clouds, by Yossi Azar et al. in CCSW 2014

# Online Hiring Problem

## Problem

If there are n candidates, and we do not want to interview all candidates to find the best one. We also do not wish to hire and fire as we find better and better candidates.

Instead, we are willing to settle for a candidate who is close to the best, in exchange of hiring exactly once.

For each interview we must either immediately offer the position to the applicant or immediately reject the applicant.

What is the trade-off between minimizing the amount of interviewing and maximizing the quality of the candidate hired?

## Code

## Analysis

We analysis in the following to determine the best value of k that maximize the probability we hire the best candidate. In the analysis, we assume the index starts with 1 (rather than 0 as shown in the code).

Let be the event that the best candidate is the -th candidate.

Let be the event that none of the candidate in position to is chosen.

Let be the event that we hire the best candidate when the best candidate is in the -th position.

We have since and are independent events.

Setting this derivative equal to 0, we see that we maximize the probability, i.e., when , we have the probability at least .

Reference

[1] Introduction to Algorithms, CLSR

# 随机过程 总结

参开资料：

http://www.zhihu.com/question/23527615

随机过程一般理论

– 概率论、随机过程的测度论基础：probability space、convergence theory、limit theory、martingale theory

– Markov process

– stochastic integral

– stochastic differential equations

– semimartingale theory

数学金融：

– stochastic integrals

– stochastic differential equations (SDE)

– semimartingale

– Ito process

– **Levy process： 解决ruin问题**

– Brownian motion

# Average Age of Renewal Process

## 1. Definition

- Let be the n-th renewal
- Then = time of the last renewal (prior to time t)
- Let
- is called the age of the renewal process
- Interpretation: A(t) is the time since last renewal

## 2. Average Age of Renewal Process

# Renewal-Reward Process

## 1. Definition

- let be a renewal process
- Let = reward earned at -th renewal
- Assume are i.i.d, but can depend on (length of the -th cycle)

## 2. Renewal Reward Theorem

__Proposition 7.3__# Reversible Markov Chain

## 1. Definition

Let be a Markov chain with transition probabilities .

E.g. A sample realization is 1, 2, 3, 4, 5

Let be the same sequence in reverse, i.e.

Let be the transition probabilities of the reversed process. That is

=

=

=

## 2. Conclusion

In the steady state, assuming the limiting probabilities exist, we have

or

The above equation is saying that the rate of transmissions from i to j in the reversed chain is equal to the rate of transitions from j to i in the forward chain.

A DTMC is time reversible if

# Markov Chain — Birth-Death Processes

# Markov Chain — Branching Process

– Stochastic Course Notes

## 1. Definition

Consider a population

- Each individual produces j new offspring each period with probability . Key assumption: This distribution is constant over time.
- Assume that for all j (i.e., the problem is not deterministic)
- Let be the size of the population at period n

## 2. Number of Population in the n-th Generation

## 3. Probability of Die Out

__Analysis__

__Example__## 4. Example: Family Genetics

**Problem:**

__Solution:__