Category: 机器学习与统计学

问题背景 本问题来源于实际问题，社交平台设计上为了保证回复帖的并发一致性，需要在回复帖前获取楼层的分布式锁，获取分布式锁的可以有资格修改存在Redis中的楼层数。目前逻辑是，如果竞争分布式锁失败，那么会直接报错，用户感知发帖失败。现在怀疑该设计会使得错误率随着QPS的提升有显著提升。本文从该问题出发，使用泊松分布与指数分布作为基本模型，探讨系统性能随容量变化的趋势。 问题描述与模型建立 问题描述如下。现有一社交平台，用户会有以下操作： 1. 发主题帖 2. 回复主题帖 存在如下碰撞可能，某一主题帖如果没有任何回复内容，在时间\( t_q\)内被至少一个用户回复，会发生碰撞。现已知每日主题帖的数量为\( Pst\)，每日回复主题帖的数量为\( Rpst\)，求每日发生碰撞次数的分布，并且探讨随着平台的使用量增大，碰撞概率发生变化的趋势。 用户在社交平台上针对某一主题帖进行回帖，可以看作服从泊松分布。有关泊松分布，可以参考本站先前的博客统计模拟(二)——泊松分布与二项分布模拟与统计模拟(六)——保险模型有关泊松分布的叙述。 用通俗的语言解释泊松分布，如现在已知每家海底捞在高峰时段平均每小时招待150名客人，求高峰时期招待用户数量的分布。 \[ P(X(t)=k)=e^{-\lambda t}\dfrac{(\lambda t)^i}{k!} \] 其中 \( \lambda\) 为单位时间内的事件发生概率，为了求2.5小时内招待350-400名客人的概率，可以将代入参数： \[ \sum_{k=350}^{400} P(X(k)) =\sum_{k=400}^{500} \dfrac{(150 \times 2.5)^k e^{(-150 \times 2.5)}}{k!} \approx 0.8122 \] 泊松分布与指数分布有着密不可分的关系，从当前时刻开始计算，时间 t 内事件发生的概率服从指数分布。（等价于时间 t 内事件发生次数不为0） \[ P(X < t) = 1 – e^{-\lambda t} \] 在本问题中，每个主题帖每秒钟平均的回复数为\( \lambda = Rpst/86400/Pst\)。假设当前存在一个主题帖，在24h内无人回复会沉帖。那么该主题帖的状态的转移状态为： … Continue reading “再谈泊松分布与指数分布”

Redis 支持基于 HyperLogLog 的基数计数统计，其算法思想和前两篇提到的 Linear Counting 和 LogLog Counting 的算法类似，本篇主要分析其源码——github:antirez/redis/src/hyperloglog.c 中的代码 Header Header 总共有 16 个字节，分别为 HYLL E N/U Cardin 如下图所示： HYLL 是 4 个魔法字节，为”HYLL” E 为 1 个字节表示Dense/Sparse N/U 为未来留下的空字节，共 3 个字节 Cardin 为缓存区，8 个字节 代码实现如下： struct hllhdr { char magic[4]; /* “HYLL” */ uint8_t encoding; /* HLL_DENSE or HLL_SPARSE. */ uint8_t notused[3]; /* … Continue reading “HyperLogLog 算法（三）—— Redis 中的 HyperLogLog”

    本文为第一系列的原创文章之七, 目的在于总结“Simulation” -Sheldon M.Ross一书中出现的模拟随机变量的方法.   Random Walk Model   在股票市场中, 有一种非常经典的模型模拟股票的变动, 称为随机漫步模型 (Random Walk Model), 认为一定时间内股票价格的变化量是服从正态分布的. 随机漫步模型基于的理论是有效市场理论, 即对所有交易者而言, 所有的信息都是公开可获得的, 当前的价格已经充分消化了市场所有信息, 同时价格会对新信息快速做出反应. 这就是有效市场假说.   关于有效市场假说或者随机漫步模型的正确与否, 此处不做过多的讨论. 在本模型中, 给出对数级别的股价的随机漫步模型的公式:   \(S_n\) 表示第 \(n\) 天收盘时的股价 \[ S_n = S_0\ e^{X_1+…+X_n} \] 其中, \(X_1\) , \(X_2\) , … , \(X_n\) 是服从均值为 \(\mu\) , 方差为 \(\sigma^2\) 的正态分布序列. 这个模型假设股价每天都以固定的比例上涨或者下跌. … Continue reading “统计模拟(七)——股票期权模型”

    本文为第一系列的原创文章之六, 目的在于总结“Simulation” -Sheldon M.Ross一书中出现的模拟随机变量的方法.      在介绍了诸多的随机变量与模拟方法之后, 接下来介绍一个实际问题的数学模型: 保险模型, 并对这个模型尝试进行模拟.   Poisson Distribution and Poisson Process   在介绍保险模型前, 首先需要介绍的是泊松过程.    在本系列文章之二 泊松分布与二项分布模拟 中介绍了泊松分布, 其表达式为: \[p_i = P(x=i)=e^{-\lambda}\dfrac{\lambda^i}{i!}, \quad i=0,1,2,…\]   泊松分布中并没有与时间相关的参数, 事实上, 离散或者连续的随机变量都与时间没有直接的关系, 事件可以在任何时候发生 (而考察的概率可以认为是从宇宙大爆炸到宇宙热寂这段时间的概率).     泊松分布中, 唯一需要确定的参数只有 \(\lambda\) . 在 泊松分布与二项分布模拟 中提到, 二项分布 \(\lambda\) 当 \(n\) 趋近于无穷大时, 二项分布近似为泊松分布, 而 \(\lambda = … Continue reading “统计模拟(六)——保险模型”

本文为第一系列的原创文章之五, 目的在于总结“Simulation” -Sheldon M.Ross一书中出现的模拟随机变量的方法. Copula 有关 Copula 的内容, 本书中介绍的不多. 在这里, 也仅仅只是对Copula以及其数学内容, 进行比较简单介绍. 类似于回归等方法, 当我们仅仅知道多个随机变量的边缘分布以及他们的相关系数时, 我们可以利用一个合适的 Copula 算子去模拟其联合分布. 这种模拟是不精确的, 是一种猜的过程, 但是会有其能发挥的作用. 以二维的 Copula 为例, 上述语言用数学语言描述就是: 已知 \(X\) 和 \(Y\) 的边缘分布 \(F\) 和 \(G\) : \begin{align*}P(X\leq x)&=F(x)\\\ P(Y\leq y)&=G(y)\end{align*} 根据已知的 \(X\) 和 \(Y\) 的相关知识, 找到合适的 \(C(x,\ y)\) , 使得 \[H(x,\ y) = C(F(x),\ G(y))\] 而 \(C(x,\ y)\) … Continue reading “统计模拟(五)——耦合算子”

本文为第一系列的原创文章之四, 目的在于总结“Simulation” -Sheldon M.Ross一书中出现的模拟随机变量的方法. Multivariate Normal Distribution 在上一篇文章中, Box-Muller 生成了一个二维的正态分布 \(X\) 与 \(Y\) , 二者相互独立, 但如果想要生成有相关性的多维(二维以及以上)变量, Box-Muller变换就有些捉襟见肘了. 在数学中, 假设向量 \(\overrightarrow{Z}=(Z_1,Z_2,Z_3,…,Z_m)^T\) 独立同分布于标准正态分布, 如果对于矩阵 \(A_{i\times j},\quad i=1,2,3,…,n,\quad j=1,2,3,…m\)与向量 \(\overrightarrow{\mu}=(\mu_1,\mu_2,\mu_3,…,\mu_n)^T\) 有: \[ \overrightarrow{X}=A\overrightarrow{Z}+\overrightarrow{\mu} \] 那么我们认为向量 \(\overrightarrow{X}=(X_1,X_2,X_3,…,X_n)^T\) 服从多维正态分布. 很明显易得: 向量 \(\overrightarrow{X}\) 的均值为 \(\overrightarrow{\mu}\) , 其协方差为 \begin{align*} Cov(X_i,\ X_j)&=Cov(\sum_{k=1}^{m} a_{ik}Z_k,\ \sum_{r=1}^{m} a_{jr}Z_r)\\\\ &=\sum_{k=1}^{m} \sum_{r=1}^{m} Cov(a_{ik}Z_k,\ a_{jr}Z_r))\\\ &=\sum_{k=1}^{m} \sum_{r=1}^{m} a_{ik} a_{jr} … Continue reading “统计模拟(四)——多维正态分布与乔列斯基分解”