概率难题-求分布列问题

pizza49

对于整数N，取值0,1,...,N-1的随机变量X和Y独立且同分布，令Z≡X+Y（mod N）,若Z与X同分布，求X所有可能得分布列？

mathe

比较有意思，我们假设这个分布取得k的概率为$a_k$
于是要求\(a_k=\sum_{i+j=k \pmod N} a_ia_j\)
定义\(f(x)=\sum_{k=0}^{N-1}a_kx^k\)
于是得到\(f(x)^2 \equiv f(x) \pmod {x^N-1}\)
也就是\(x^N-1 | f(x)(f(x)-1)\)
由于\(gcd(f(x),f(x)-1)=1\)

如果我们把\(x^N-1\)表示成两个互素子表达式乘积，也就是\(x^N-1=a(x)b(x), (a(x),b(x))=1\)
那么我们知道存在\(u(x),v(x)\)使得\(u(x)a(x)-v(x)b(x)=1\)
如果这时选择f(x)=u(x)a(x),那么f(x)-1=v(x)b(x),于是必然有\(x^N-1|f(x)(f(x)-1))=u(x)v(x)(x^N-1)\)
我们还有一个额外条件要求时f(x)的次数不超过N-1,f(1)=1,而且f(x)所有系数非负。对应a(1)!=0,b(1)=0,也就是x-1在b(x)
对于每个具体的N,通过因式分解\(x^N-1\)就可以找到所有的解了。
对于N为素数情况会比较简单，只有唯一解，也就是均匀分布。对于N不是素数，显然均匀分布或在N某个因子的倍数上均匀分布都是可行的解，就不知道是否还有其它解。

mathe

引理1：如果\(a_h\gt 0\),那么对于任何\(m\), \(a_{mh\pmod N}\gt 0\)
这里引理很简单，归纳假设即可。
然后记\(h\)为使得\(a_k\gt 0\)而且\(k\gt 0\)最小的\(k\), 显然必须\(h|N\).
设\(m\)为使得\(h|k\)而且\(a_k\)最小的k, 也就是数列\(a_k\)中最小的非零项，那么显然\(a_m \le  \frac{h}{N}\)
然后根据定义\(a_m=\sum_{i+j =m "or" i+j=m+N} a_ia_j \ge \frac{N}{h} (\frac{h}{N})^2 = \frac{h}{N}\)
所以只能\(a_m= \frac{h}{N}\)
也就是只能时准均匀情况一种

pizza49

mathe 发表于 2024-10-12 11:37
比较有意思，我们假设这个分布取得k的概率为$a_k$
于是要求\(a_k=\sum_{i+j=k \pmod N} a_ia_j\)
定义\(f(x ...

选择f(x)=u(x)a(x)这步感觉有问题

pizza49

准确说任意N都有a_0=1,a_1=...=a_(N-1)=0这种特殊情况

pizza49

mathe 发表于 2024-10-12 11:37
比较有意思，我们假设这个分布取得k的概率为$a_k$
于是要求\(a_k=\sum_{i+j=k \pmod N} a_ia_j\)
定义\(f(x ...

情况总数应为$\mathbb{Z} _{N}$的子群个数包含$\mathbb{Z} _{N}$在内，即N的所有因子总个数。$f(x)=\frac{x^N-1}{x^d-1}$是符合要求的，其中d是N的某个因子 。

yigo

根据\(a(x),b(x),u(x)a(x)-v(x)b(x)=1\)，怎么求解\(u(x),v(x)\)。