找回密码
 欢迎注册
查看: 1623|回复: 2

[原创] 随机递推数列的行为

[复制链接]
发表于 2024-5-20 16:07:53 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
如果数列{a(n)}的前两项是a(1)=0、a(2)=1,从第3项开始就不确定了,当n>2时,a(n)有p的概率是a(n-1)+a(n-2),还有(1-p)的概率是abs(a(n-1)-a(n-2))。我想知道当p小于多少时,a(n)会无限多次回到0;当p大于多少时,a(n)有限多次回到0之后,就再也回不到0了?

#####

这个问题AI已经帮我解决了大部分了,对话内容如下:

问:如果数列{a(n)}的前两项是a(1)=0、a(2)=1,从第3项开始就不确定了,当n>2时,a(n)有50%的概率是a(n-1)+a(n-2),还有50%的概率是abs(a(n-1)-a(n-2))。我想知道当n很大的时候,a(n)更有可能是一个很小的数(如log(n)),还是更有可能是一个很大的数(如1.1^n)?

答:这个问题涉及到随机递归数列的行为,特别是当递归关系有两种可能时(加法或绝对值差)。为了分析这个问题,我们可以从几个不同的角度入手。
首先,我们注意到数列的初始两项是 a(1)=0 和 a(2)=1。从第三项开始,数列的每一项都有50%的概率是前两项的和,也有50%的概率是前两项之差的绝对值。
要判断当 n 很大时,a(n) 更可能是一个很小的数(如 log(n))还是一个很大的数(如 1.1^n),我们需要考虑数列的增长趋势和可能的波动。
增长趋势:
如果数列经常选择加法(a(n)=a(n−1)+a(n−2) ),那么数列可能会快速增长,因为这是一个斐波那契数列的变种,其增长是指数级的。
如果数列经常选择绝对值差(a(n)=∣a(n−1)−a(n−2)∣),那么数列的增长可能会受到抑制,因为差值可能会很小,甚至在某些情况下导致数列值减小。
波动性分析:
由于每一步都有50%的不确定性,数列的波动会非常大。即使数列在某个阶段快速增长,也可能在下一阶段因为连续选择绝对值差而迅速减小。
这种波动使得预测数列的长期行为变得非常困难。
log(n) 和 1.1^n 的比较:
log(n) 是一个增长非常缓慢的函数,当 n 很大时,它的值相对于 n 来说非常小。
1.1^n 是一个增长较快的函数,即使基数只比1大一点点,但由于是指数增长,当 n 很大时,它的值会非常大。
由于数列的波动性和不确定性,很难直接将其与这两个函数进行比较。但是,考虑到数列有50%的概率选择加法(可能导致快速增长),我们可以推测,在长期内,数列的值更有可能接近或超过 1.1^n,而不是 log(n)。
综上所述,当 n 很大时,数列 a(n) 更有可能是一个很大的数(如 1.1^n),而不是一个很小的数(如 log(n))。但是,由于数列的随机性和波动性,这种判断并不是绝对的,只是一种基于概率和增长趋势的推测

追问:我想通过编写程序的方法去看看n很大时(如n=10000)a(n)的分布,这个程序该怎么编写呢?

答:要编写一个程序来模拟并观察当 n 很大时(如 n=10000)数列 a(n) 的分布,你可以使用随机性来模拟每一步的选择(加法或绝对值差)。以下是一个简单的 Python 程序示例,它模拟了数列的生成并记录了 a(n) 的值:
  1. import random  
  2.   
  3. def simulate_sequence(n):  
  4.     # 初始化数列的前两项  
  5.     sequence = [0, 1]  
  6.       
  7.     # 模拟后续的数列项  
  8.     for i in range(2, n):  
  9.         # 以50%的概率选择加法或绝对值差  
  10.         if random.random() < 0.5:  
  11.             sequence.append(sequence[i-1] + sequence[i-2])  
  12.         else:  
  13.             sequence.append(abs(sequence[i-1] - sequence[i-2]))  
  14.       
  15.     # 返回数列  
  16.     return sequence  
  17.   
  18. # 设定n的值  
  19. n = 10000  
  20.   
  21. # 模拟数列  
  22. sequence = simulate_sequence(n)  
  23.   
  24. # 打印数列的最后几个值来观察趋势(或者你可以选择其他方式来分析数据)  
  25. print(sequence[-10:])  # 打印最后10个值  
  26.   
  27. # 如果你想分析整个数列的分布,可以将其存储到文件中或进行统计分析  
  28. # 例如,统计不同数值范围的出现次数  
  29. distribution = {}  
  30. for value in sequence:  
  31.     if value < 10:  
  32.         key = '0-9'  
  33.     elif value < 100:  
  34.         key = '10-99'  
  35.     elif value < 1000:  
  36.         key = '100-999'  
  37.     # ... 你可以继续添加更多范围  
  38.     else:  
  39.         key = '1000+'  
  40.     distribution[key] = distribution.get(key, 0) + 1  
  41.   
  42. # 打印分布  
  43. for key, count in distribution.items():  
  44.     print(f"Values in range {key}: {count}")  
  45.   
  46. # 注意:由于随机性,每次运行程序得到的分布可能都会不同
复制代码
这个程序定义了一个 simulate_sequence 函数,它使用随机性来模拟数列的生成。然后,它调用这个函数来生成一个包含 n 个元素的数列,并打印出最后几个值来观察趋势。最后,它还计算了一个简单的分布,将数列中的值分组到不同的范围,并打印出每个范围中的值出现的次数。
请注意,由于随机性,每次运行程序时得到的数列和分布可能都会不同。为了获得更可靠的结果,你可能需要多次运行程序并平均结果,或者运行程序并使用更复杂的统计分析方法。

追问:我加了一些范围,运行结果如下:
Values in range 0-9: 19
Values in range 10-99: 18
Values in range 100-999: 38
Values in range 1000-9999: 33
Values in range 10000-99999: 12
Values in range 100000-999999: 12
Values in range 1000000+: 9868
这个结果是什么意思呢?这个结果和你最初的判断一致吗?

答:这个结果给出了数列 a(n) 在不同数值范围内的出现频率。根据你给出的数据,我们可以看到数列中大部分值(9868次)出现在 1000000+ 这个范围内,这意味着当 n 较大时(在你的例子中 n=10000),数列的值更有可能是一个很大的数。
这个结果与我最初的判断是一致的,即由于数列有一半的概率选择加法(这可能导致指数级增长),数列在长期内更有可能接近或超过快速增长的函数(如 1.1^n),而不是增长缓慢的函数(如 log(n))。
然而,需要注意的是,由于这是基于随机模拟的结果,每次运行程序都可能会得到不同的分布。但是,如果多次运行并平均结果,或者运行足够多次以确保统计上的稳定性,你应该会发现类似的趋势,即数列的值倾向于在较大的数值范围内。
此外,你的结果还显示了数列中存在一些较小的值,但这可能是由于数列中的随机性导致的短期波动或周期性行为。在长期内,这些较小的值不太可能是数列的典型行为,因为数列有一半的概率通过加法来增加其值。
综上所述,你的模拟结果支持了我最初的判断,即当 n 很大时,数列 a(n) 更有可能是一个很大的数。

追问:如果选择减法的概率大一些,这个数列可能就是另一种行为了(n很大时趋近于log(n))。有没有可能编写程序,求出选择减法的概率达到多少时,这个数列在n很大时趋近于log(n)?

答:要确定选择减法的概率达到多少时,数列在 n 很大时趋近于 log(n),是一个相当复杂的问题,因为它涉及到随机过程的长时间行为,通常没有简单的解析解。然而,你可以通过模拟和统计分析来尝试找到这个概率的大致范围。
首先,你需要明确“趋近于 log(n)”的定义。这通常意味着数列的增长率应该与 log(n) 相当,或者数列的值在长时间内应该紧密围绕某个与 log(n) 成比例的函数。
以下是一个可能的策略来估计这个概率:
编写模拟程序:编写一个程序,该程序接受一个参数 p(选择减法的概率),并模拟数列的生成,直到 n 变得很大(比如 n=100000 或更大)。
收集数据:在每次模拟中,收集数列的最后几个值(比如最后100个值),并计算这些值的对数(如果值很小,可以直接使用;如果值很大,可能需要对数变换后分析)。
统计分析:分析收集到的数据,看它们是否趋近于 log(n)。你可以通过计算数列的对数值与 log(n) 的相关性、计算均方误差(MSE)或其他统计指标来评估趋近程度。
迭代和调整:通过迭代不同的 p 值,并重复上述步骤,你可以找到使数列趋近于 log(n) 的 p 值范围。
注意随机性:由于这是随机过程,每次模拟的结果可能会有所不同。因此,你可能需要多次运行模拟(对于每个 p 值),并取平均值或中位数来得到更可靠的结果。
理论支持(可选):如果可能的话,你也可以尝试找到这个问题的理论解或近似解。这可能需要深入的数学知识和分析技巧。
请注意,即使你找到了一个使数列趋近于 log(n) 的 p 值范围,这并不意味着数列在任何时候都会严格遵循 log(n) 的增长。它只是表明在长时间内,数列的增长率与 log(n) 相当。此外,由于随机性的影响,即使 p 值在这个范围内,数列的行为也可能会有所不同。

#####

想要拿到更准确的回答,AI是不指望了,还得问人才行。不知道坛友们能否求出更准确的p的阈值?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2024-5-23 19:08:26 来自手机 | 显示全部楼层
可以试着计算如果当前a(n-1)=i,a(n)=j时,那么➕经过有限步会出现0的概率E(i,j)。
显然这个概率和n无关,于是E(i,j)=p*E(j,i+j)+(1-p)*E(j,|i-j|).
可以开始将E(i,0)初始化为1,其余为0,然后顺序迭代计算多轮看看收敛性
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2024-5-24 19:34:35 | 显示全部楼层
令选择加法的概率为0.01、0.02、0.03、……、0.50,各模拟10000次

然后统计10000次模拟里面,【a(10000)=0】这个事件发生了多少次(记为s次)

然后用s除以10000,就是【a(10000)=0】这个随机事件发生的概率,记为Pr(a(10000)=0)

统计结果如下图所示:

f.png

图中显示,当选择加法的概率大于1/3时,Pr(a(10000)=0)就降至0了

Pr(a(∞)=0)的结果应该是类似的:

当选择加法的概率大于1/3时,我们有 Pr(a(∞)=0)=0,也就是a(n)有限多次回到0之后,就再也回不到0了

当选择加法的概率小于1/3时,我们有 Pr(a(∞)=0)>0,也就是a(n)可以无限多次回到0

不知道当选择加法的概率恰好是临界点1/3的时候,会发生什么事情呢?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-12-22 11:24 , Processed in 0.027832 second(s), 19 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表